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}\).