# Quasar: Translating high-level If-Then-Else conditional statements into a sequence of controlled gates

https://github.com/beittech/Quasar

## Motivation

# 18 CCX, 12 X, 1 CZ
x q[1]; x q[2]; x q[3]; x q[4]; x q[5]; ccx q[1], q[2], q[11]; ccx q[3], q[4], q[12];
ccx q[5], q[11], q[13]; ccx q[12], q[13], q[14]; x q[14]; ccx q[6], q[14], q[15];
ccx q[7], q[8], q[16]; ccx q[9], q[10], q[17]; ccx q[15], q[16], q[18];
ccx q[17], q[18], q[19]; cz q[19], q[0]; ccx q[17], q[18], q[19];
ccx q[15], q[16], q[18]; ccx q[9], q[10], q[17]; ccx q[7], q[8], q[16];
ccx q[6], q[14], q[15]; x q[14]; ccx q[12], q[13], q[14]; ccx q[5], q[11], q[13];
ccx q[3], q[4], q[12]; ccx q[1], q[2], q[11]; x q[5]; x q[4]; x q[3]; x q[2]; x q[1];

If( Any( [q1, q2, q3, q4, q5] ) ).Then(
If( All( [q6, q7, q8, q9, q10] ) ).Then(
Z(q0)
)
)


## Examples

### Examples / Grover

def Grover(qubits: List[Qubit], predicate: ASTNode) -> Program:
prgm = Program()
#########################################################
for qubit in qubits:                      # Uniform
prgm += H(qubit)                      # Superposition
#########################################################
for _ in range(int(sqrt(2 ** len(qubits)))):
#####################################################
prgm += If(predicate).Flip()          # Oracle
#####################################################
for qubit in qubits:
prgm += H(qubit)
# Grover
prgm += If(Zero(qubits)).Flip()       # Diffusion
# Operator
for qubit in qubits:
prgm += H(qubit)
#####################################################
prgm += Flip(qubits)

return prgm

prgm = Program()
qubits = prgm.Qubits([0, 0, 0])
prgm += Grover(qubits, predicate=Match(qubits, mask=[0, 1, 0]))
print(Quasar().to_qasm_str(prgm))


### Examples / Fourier

def Fourier(qubits: List[Qubit]) -> Program:
prgm = Program()
length = len(qubits)

for i in range(length):
prgm += H(qubits[i])

for j in range(2, length + 1 - i):
prgm += If(All(qubits[i + j - 1])).Then(
Phase(qubits[i], 2 * pi / (2 ** j))
)

for i in range(length // 2):
prgm += Swap(qubits[i], qubits[length - i - 1])

return prgm

prgm = Program()
qubits = prgm.Qubits([0, 1])
prgm += Fourier(qubits)
print(Quasar().to_qasm_str(prgm))


## Algorithm

### Algorithm / Translation / U

                                     ancilla = cond(c1, ...)
If( cond(c1, ...) ).Then( U t )  ->  CU ancilla t
ancilla = uncompute( cond(c1, ,...) )


### Algorithm / Translation / CU

                                         a = cond(c1, ...) & cn
If( cond(c1, ...) ).Then( CU cn t )  ->  CU a t
a = uncompute( cond(c1, ...) & cn )


### Algorithm / Translation / CCU

                                             a = cond(c1, ...) & cn
If( cond(c1, ...) ).Then( CCU cn cm t )  ->  CCU a cm t
a = uncompute( cond(c1, ...) & cn )


### Algorithm / Translation / Flip

                                a = cond(c1, ...)
If( cond(c1, ...) ).Flip()  ->  Z a
a = uncompute( cond(c1, ...) )


### Algorithm / Example / 1

High Level Code                Abstract Syntax Notation      Low level code

If( All([c1, c2]) ).Then(      CCX c1 c2 a1                  CCX c1 c2 a1
X(t1)                        If( a1).Then(X t1)          CX a1 t1
Y(t2)                        If( a1).Then(Y t2)          CY a1 t2
).Else(                    ->                            ->  X a1
Z(t3)                        If(!a1).Then(Z t3)          CZ a1 t3
H(t4)                        If(!a1).Then(H t4)          CH a1 t4
)                              CCX c1 c2 a1                  X a1
CCX c1 c2 a1


### Algorithm / Example / 2

High Level Code                  Abstract Syntax Notation       Low level code

If( All([c1, c2]) ).Then(        CCX c1 c2 a1                   CCX c1 c2 a1
If( All([c3, c4]) ).Then(        CCX c3 c4 a2                 CCX c3 c4 a2
X(t1)                            If(a1 a2).Then(X t1)       CCX a1 a2 t1
).Else(                                                       X a2
Y(t2)                    ->      If(a1 !a2).Then(Y t2)  ->  CCY a1 a2 t2
)                                                             X a2
).Else(                            CCX c3 c4 a2                 CCX c3 c4 a2
Z(t3)                            If(!a).Then(Z t3)            X a1
)                                CCX c1 c2 anc                  CZ a1 t3
X a1
CCX c1 c2 a1


## Conditions

### Conditions / All

If( All( qubits ) ).Then(      a = CCC...X qubits
code                   ->  If( a ).Then( code )
)                              a = CCC...X qubits

CCC...X = Multi Controlled X = Multi Controlled Toffoli


### Conditions / Zero

                                for q in qubits:
X q

If( Zero( qubits ) ).Then(      a = CCC...X qubits
code                    ->  If( a ).Then( code )
)                               a = CCC...X qubits

for q in qubits:
X q


### Conditions / Any = Not ( Zero )

                               for q in qubits:
X q

If( Any( qubits ) ).Then(      a = CCC...X qubits
code                   ->  If( !a ).Then( code )
)                              a = CCC...X qubits

for q in qubits:
X q


### Conditions / Match

                                       for (q, m) in zip( qubits, mask ):
If( not m ):
X q

If( Match( qubits, mask ) ).Then(      a = CCC...X qubits
code                           ->  If( a ).Then( code )
)                                      a = CCC...X qubits

for (q, m) in zip( qubits, mask )[::-1]:
If( not m ):
X q

If( Match( [q0, q1, q2, q3, q4], [1, 0, 1, 0, 1] ) ).Then( code ... )
If( Match( [q0, q1, q2, q3, q4], [1, 1, 1, 1, 1] ) ).Then( code ... )   # All
If( Match( [q0, q1, q2, q3, q4], [0, 0, 0, 0, 0] ) ).Then( code ... )   # Zero


### Conditions / Not

If( Not( All( qubits ) ) ).Then(      a = CCC...X qubits
code                          ->  If( !a ).Then( code )
)                                     a = CCC...X qubits


## Uncompute

           Compute      |    Uncompute
┌───────┐     |    ┌───────┐
q_1 : ────┤X/Y/Z/H├─────|────┤X/Y/Z/H├─────
└───────┘     |    └───────┘
┌───────┐     |    ┌───────┐
q_2 : ────┤  S/T  ├─────|────┤ S*/T* ├─────
└───────┘     |    └───────┘
┌──────────────┐ | ┌──────────────┐        uncompute( program ):
q_3 : ─┤Rx/Ry/Rz( arg)├─|─┤Rx/Ry/Rz(-arg)├─   ->    return [
└──────────────┘ | └──────────────┘            transpose(conjugate(gate))
┌───┐ ┌───┐ ┌───┐ |  ┌───┐ ┌───┐ ┌───┐          for gate in reverse(gates)
q_4 : ┤U1 ├─┤U2 ├─┤U3 ├─|──┤U3*├─┤U2*├─┤U1*├        ]
└───┘ └───┘ └───┘ |  └───┘ └───┘ └───┘
q_5 : ────────■─────────|────────■─────────
┌───┴───┐     |    ┌───┴───┐
q_6 : ────┤   U   ├─────|────┤   U*  ├─────
└───────┘     |    └───────┘


## Compute CCC...U

### Compute CCC...U / V-chain using ancillas

q_0 : ──■───────────────────■──      q_0 : ──■─────────■──
│                   │                │         │               CCU
q_1 : ──■───────────────────■──      q_1 : ──■─────────■──      [1 0 0 0 │ 0 0 0 0 ]
┌─┴─┐               ┌─┴─┐            ┌─┴─┐     ┌─┴─┐      [0 1 0 0 │ 0 0 0 0 ]
anc1: ┤ X ├──■─────────■──┤ X ├      anc1: ┤ X ├──■──┤ X ├      [0 0 1 0 │ 0 0 0 0 ]
└───┘  │         │  └───┘            └───┘  │  └───┘      [0 0 0 1 │ 0 0 0 0 ]
q_2 : ───────■─────────■───────  ->  q_2 : ──■────┼────■──  ->  ─────────┼──────────
┌─┴─┐     ┌─┴─┐                   │    │    │        [0 0 0 0 │         ]
anc2: ─────┤ X ├──■──┤ X ├─────      q_3 : ──■────┼────■──      [0 0 0 0 │   U     ]
└───┘  │  └───┘                 ┌─┴─┐  │  ┌─┴─┐      [0 0 0 0 │         ]
q_3 : ────────────■────────────      anc2: ┤ X ├──■──┤ X ├      [0 0 0 0 │         ]
┌─┴─┐                      └───┘┌─┴─┐└───┘
q_4 : ──────────┤ U ├──────────      a_4 : ─────┤ U ├─────
└───┘                           └───┘


### Compute CCC...U / Recursion with no ancillas

         V²=U     if(c0){+V} │ if(c1){+V} │ if(c0≠c1){-V}

c_n  : ──■──    ───────────┼──────■─────┼───■─────────■──
│                 |      │     |   │         │       x │ y │x^y│ x+y-x^y
...     ...                |     ...    |  ...       ...
│                 |      │     |   │         │      ───┼───┼───┼──────────
c1   : ──■── -> ───────────┼──────■─────┼───■─────────■── ->  0 │ 0 │ 0 │ 0+0-0V=0
│                 |      │     | ┌─┴─┐     ┌─┴─┐     0 │ 1 │ 1 │ 0+V-1V=0
c0   : ──■──    ─────■─────┼──────┼─────┼─┤ X ├──■──┤ X ├     1 │ 0 │ 1 │ V+0-1V=0
┌─┴─┐       ┌─┴─┐   |    ┌─┴─┐   | └───┘┌─┴─┐└───┘     1 │ 1 │ 0 │ V+V-0V=U
t    : ┤ U ├    ───┤ V ├───┼────┤ V ├───┼──────┤ V*├─────
└───┘       └───┘   |    └───┘   |      └───┘


where $$\hat{} = \oplus = \text{xor}$$.

## Optimizations

### Optimizations / Trivial cases / 1

                           ACTUAL          EXPECTED

If( All([c]) ).Then(       CX c a
X t                ->  CX a t      ->  CX c t
)                          CX c a

If( All([c1]) ).Then(      CX q1 a
CX c2 t            ->  CCX a c2 t  ->  CCX c1 c2 t
)                          CX q1 a


### Optimizations / Trivial cases / 2

     CX q0 q1                                CCX q0 q1 q2

q0 : ─┼──■─────────■──     ──■──        q0 : ─┼──■─────────■──     ──■──
│┌─┴─┐     ┌─┴─┐       │                │┌─┴─┐     ┌─┴─┐       │
anc: ─┼┤ X ├──■──┤ X ├     ──┼──        anc: ─┼┤ X ├──■──┤ X ├     ──┼──
│└───┘┌─┴─┐└───┘  =  ┌─┴─┐              │└───┘  │  └───┘  =    │
q1 : ─┼─────┤ X ├─────     ┤ X ├        q1 : ─┼───────■───────     ──■──
│     └───┘          └───┘              │     ┌─┴─┐          ┌─┴─┐
q2 : ─┼───────────────     ─────        q2 : ─┼─────┤ X ├─────     ┤ X ├
│                                       │     └───┘          └───┘
t₀                                      t₀


Only when $$\text{anc}_{t_{0}} = \left|0\right>$$ because $$x \oplus 0 = x$$ and $$x \oplus 1 \ne x$$.

### Optimizations / Back-to-back gates

q_0 : ──■─────────■─────────■─────────■──     ──■───────────────────■──
│         │         │         │         │                   │
q_1 : ──■─────────■─────────■─────────■──     ──■───────────────────■──
┌─┴─┐     ┌─┴─┐     ┌─┴─┐     ┌─┴─┐     ┌─┴─┐               ┌─┴─┐
anc1: ┤ U ├──■──┤ U ├─────┤ U ├──■──┤ U ├     ┤ U ├──■─────────■──┤ U ├
└───┘  │  └───┘     └───┘  │  └───┘  =  └───┘  │         │  └───┘
q_2 : ───────■───────────────────■───────     ───────■─────────■───────
┌─┴─┐               ┌─┴─┐               ┌─┴─┐     ┌─┴─┐
anc2: ─────┤ U ├───────■───────┤ U ├─────     ─────┤ U ├──■──┤ U ├─────
└───┘     ┌─┴─┐     └───┘               └───┘┌─┴─┐└───┘
q_3 : ───────────────┤ U ├───────────────     ──────────┤ U ├──────────
└───┘                              └───┘


Only when $$\text{CCU} \cdot \text{CCU} = \mathbb{1}$$ and in general $$\text{U} \cdot \text{V} = \mathbb{1}$$.