Simple Algorithm
Quantum Computing · Rydberg State · 28 min

Building Controlled-U: the ABC Construction

Controlled gates from CNOTs and single-qubit rotations.

Hardware gives you one kind of entangling gate, typically a CNOT or CZ, yet algorithms are full of controlled-UU's of every description. The ABC construction (Barenco et al., 1995) builds any controlled single-qubit gate from two CNOTs, and it explains why a "harmless" global phase suddenly matters once a gate is controlled. You will prove it, decide exactly when one CNOT suffices, and scale up to many controls.

What you’ll learn

  • Define Λ(U)\Lambda(U) and prove Λ(eiαI)=P(α)⊗I\Lambda(e^{i\alpha}\id)=P(\alpha)\otimes\id: controlled global phases are physical.
  • Prove the ABC theorem and assemble Λ(U)\Lambda(U) from two CNOTs, three single-qubit gates and one phase gate.
  • Prove, with an entanglement argument, that Λ(U)\Lambda(U) needs zero, one or two CNOTs according to the eigenphase gap of UU.
  • Build Λ2(U)\Lambda_2(U) from singly controlled VV with V2=UV^2=U, and state the gate-count scaling of Λk(U)\Lambda_k(U) with and without ancillas.

Controlled gates and the reappearing phase

DerivationControlled phases are physical
  1. Λ(eiαV)=∣0⟩ ⁣⟨0∣⊗I+eiα∣1⟩ ⁣⟨1∣⊗V=Λ(eiαI) Λ(V)\Lambda(e^{i\alpha}V)=\dyad0\otimes\id+e^{i\alpha}\dyad1\otimes V=\Lambda(e^{i\alpha}\id)\,\Lambda(V)

    Factor the phase out of the ∣1⟩\ket1 block.

  2. Λ(eiαI)=diag⁡(1,1,eiα,eiα)=P(α)⊗I\Lambda(e^{i\alpha}\id)=\diag(1,1,e^{i\alpha},e^{i\alpha})=P(\alpha)\otimes\id

    A controlled global phase is a phase gate on the control.

  3. Λ(T)=(P(π8)⊗I) Λ(Rz(π4)),Λ(Rz(2π))=Λ(−I)=Z⊗I\Lambda(T)=\big(P(\tfrac\pi8)\otimes\id\big)\,\Lambda\big(R_z(\tfrac\pi4)\big),\qquad\Lambda\big(R_z(2\pi)\big)=\Lambda(-\id)=Z\otimes\id

    Gates that are identical in isolation (T≃Rz(π/4)T\simeq R_z(\pi/4), Rz(2π)≃IR_z(2\pi)\simeq\id) differ once controlled. A compiler that drops global phases must restore them before adding controls.

Check your understanding

What is Λ(Rx(2π))\Lambda\big(R_x(2\pi)\big)?

  1. I⊗I\id\otimes\id
  2. Z⊗IZ\otimes\id
  3. I⊗X\id\otimes X
  4. −I⊗I-\id\otimes\id
Show the answer

B. Z⊗IZ\otimes\id

Rx(2π)=cos⁡π I−isin⁡π X=−IR_x(2\pi)=\cos\pi\,\id-i\sin\pi\,X=-\id, so Λ(Rx(2π))=Λ(−I)=P(π)⊗I=Z⊗I\Lambda(R_x(2\pi))=\Lambda(-\id)=P(\pi)\otimes\id=Z\otimes\id.

The ABC theorem

DerivationProof
  1. U=eiαRz(β)Ry(γ)Rz(δ)U=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)

    Start from the Z–Y–Z Euler decomposition.

  2. A=Rz(β)Ry(γ2),B=Ry(−γ2)Rz(−δ+β2),C=Rz(δ−β2)A=R_z(\beta)R_y(\tfrac\gamma2),\qquad B=R_y(-\tfrac\gamma2)R_z(-\tfrac{\delta+\beta}{2}),\qquad C=R_z(\tfrac{\delta-\beta}{2})

    Choose three SU(2)SU(2) factors.

  3. ABC=I,AXBXC=Rz(β)Ry(γ)Rz(δ)ABC=\id,\qquad AXBXC=R_z(\beta)R_y(\gamma)R_z(\delta)

    Merge adjacent rotations; XRy(θ)X=Ry(−θ)XR_y(\theta)X=R_y(-\theta) and XRz(θ)X=Rz(−θ)XR_z(\theta)X=R_z(-\theta) flip the angles inside BB. (Details in Euler Decompositions.)

  4. control ∣0⟩:  ABC=I,control ∣1⟩:  eiαAXBXC=U\text{control }\ket0:\ \ ABC=\id,\qquad\text{control }\ket1:\ \ e^{i\alpha}AXBXC=U

    In the circuit, CC acts first, then a CNOT, BB, a CNOT and AA. The phase gate P(α)P(\alpha) on the control commutes with everything else, because every other gate is block-diagonal in the control's basis. ∎

qasm
OPENQASM 3.0;
include "stdgates.inc";

// Controlled-U for U = e^{i alpha} Rz(beta) Ry(gamma) Rz(delta)
input float[64] alpha;
input float[64] beta;
input float[64] gamma;
input float[64] delta;
qubit[2] q;                      // q[0] = control, q[1] = target

rz((delta - beta) / 2) q[1];     // C
cx q[0], q[1];
rz(-(delta + beta) / 2) q[1];    // B = Ry(-gamma/2) Rz(-(delta+beta)/2)
ry(-gamma / 2) q[1];
cx q[0], q[1];
ry(gamma / 2) q[1];              // A = Rz(beta) Ry(gamma/2)
rz(beta) q[1];
p(alpha) q[0];                   // the controlled global phase

The ABC circuit in OpenQASM 3. Statements appear in time order, the reverse of the operator product.

Now test it. Below, two Bell pairs connect reference qubits 0 and 1 to the system qubits 2 (control) and 3 (target), so matching the output state verifies your circuit as an operator on all inputs: it is the Choi state of the system gate.

When is one CNOT enough?

DerivationA controlled phase from two CNOTs
  1. CP(φ)=(P(φ2)⊗I) CNOT (I⊗P(−φ2)) CNOT (I⊗P(φ2))CP(\varphi)=\big(P(\tfrac\varphi2)\otimes\id\big)\,\mathrm{CNOT}\,\big(\id\otimes P(-\tfrac\varphi2)\big)\,\mathrm{CNOT}\,\big(\id\otimes P(\tfrac\varphi2)\big)

    The claim; the rightmost factor acts first.

  2. ∣a,b⟩↦eiφ2 (b−(a⊕b)+a)∣a,b⟩\ket{a,b}\mapsto e^{i\frac\varphi2\,\left(b-(a\oplus b)+a\right)}\ket{a,b}

    Track the phases: P(φ2)P(\tfrac\varphi2) sees the bit bb, then P(−φ2)P(-\tfrac\varphi2) sees the XOR a⊕ba\oplus b, and P(φ2)P(\tfrac\varphi2) on the control sees aa. The second CNOT restores bb.

  3. a+b−(a⊕b)=2ab⟹∣a,b⟩↦eiφab∣a,b⟩a+b-(a\oplus b)=2ab\quad\Longrightarrow\quad\ket{a,b}\mapsto e^{i\varphi ab}\ket{a,b}

    The bit identity a⊕b=a+b−2aba\oplus b=a+b-2ab finishes the proof. This is the simplest phase polynomial; the seven-TT Toffoli uses the same trick in three variables.

Check your understanding

What is the minimum number of CNOTs needed for Λ(S)\Lambda(S)?

  1. 0
  2. 1
  3. 2
  4. 3
Show the answer

C. 2

S=diag⁡(1,i)S=\diag(1,i) has eigenphase gap λ=π/2≢0,π\lambda=\pi/2\not\equiv0,\pi, so Λ(S)=CP(π/2)\Lambda(S)=CP(\pi/2) needs exactly two. Its best concurrence from a product input is sin⁡π4≈0.71\sin\tfrac\pi4\approx0.71, short of the value 1 that any one-CNOT circuit reaches.

Many controls

Recursing on the lemma builds Λk(U)\Lambda_k(U) from two-qubit gates. Without ancillas this takes O(k2)\order{k^2} elementary gates (Barenco et al. 1995). A single extra qubit, even one in an unknown state that must merely be returned unchanged (a borrowed or "dirty" ancilla), brings Λk(X)\Lambda_k(X) down to O(k)\order{k}. With k−2k-2 clean ancillas, the textbook ladder uses 2k−32k-3 Toffolis.

Key takeaways

  • Λ(eiαV)=(P(α)⊗I) Λ(V)\Lambda(e^{i\alpha}V)=(P(\alpha)\otimes\id)\,\Lambda(V): the global phase of a controlled gate becomes a phase gate on the control.
  • ABC theorem: U=eiαAXBXCU=e^{i\alpha}AXBXC with ABC=IABC=\id, so every Λ(U)\Lambda(U) needs at most two CNOTs.
  • Λ(U)\Lambda(U) is locally equivalent to CP(λ2−λ1)CP(\lambda_2-\lambda_1): one CNOT iff the eigenphase gap is π\pi, otherwise two (zero if U∝IU\propto\id).
  • Λ2(U)\Lambda_2(U) follows from controlled VV with V2=UV^2=U; recursion gives O(k2)\order{k^2} gates for Λk(U)\Lambda_k(U) without ancillas and O(k)\order{k} for Λk(X)\Lambda_k(X) with one borrowed ancilla.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

In the ABC circuit, what acts on the target when the control is ∣0⟩\ket0?

  1. ABCABC, which equals I\id
  2. AA only
  3. AXBXCAXBXC
  4. XBXXBX
Show the answer

A. ABCABC, which equals I\id

With the control in ∣0⟩\ket0 the CNOTs do nothing, so the target sees CC, then BB, then AA, i.e. the product ABC=IABC=\id. The constraint ABC=IABC=\id is exactly what makes the gate controlled.

Question 2

How do Λ(T)\Lambda(T) and Λ(Rz(π/4))\Lambda(R_z(\pi/4)) differ?

  1. They are equal, since T≃Rz(π/4)T\simeq R_z(\pi/4)
  2. By ZZ on the control
  3. By P(π/4)P(\pi/4) on the target
  4. By P(π/8)P(\pi/8) on the control
Show the answer

D. By P(π/8)P(\pi/8) on the control

T=eiπ/8Rz(π/4)T=e^{i\pi/8}R_z(\pi/4), and a controlled phase eiπ/8e^{i\pi/8} is P(π/8)P(\pi/8) on the control: Λ(T)=(P(π8)⊗I) Λ(Rz(π4))\Lambda(T)=(P(\tfrac\pi8)\otimes\id)\,\Lambda(R_z(\tfrac\pi4)).

Question 3

For which UU can Λ(U)\Lambda(U) be built from exactly one CNOT plus single-qubit gates?

  1. Any UU with det⁡U=1\det U=1
  2. Any UU whose two eigenvalues differ by a factor −1-1, such as XX, YY, ZZ or HH
  3. Only U=XU=X
  4. Any diagonal UU
Show the answer

B. Any UU whose two eigenvalues differ by a factor −1-1, such as XX, YY, ZZ or HH

Λ(U)\Lambda(U) is locally equivalent to CP(λ)CP(\lambda) with λ\lambda the eigenphase gap, and one CNOT suffices exactly when λ≡π\lambda\equiv\pi. That holds for every U∝n^⋅σ⃗U\propto\hat n\cdot\vec\sigma.

Question 4

In Barenco's construction of Λ2(U)\Lambda_2(U) from singly controlled gates, what must VV satisfy?

  1. V=UV=U
  2. V†=UV^\dagger=U
  3. V2=UV^2=U
  4. V3=UV^3=U
Show the answer

C. V2=UV^2=U

For control bits (a,b)(a,b) the target receives Vb V−(a⊕b) Va=V2abV^{b}\,V^{-(a\oplus b)}\,V^{a}=V^{2ab}, which must equal UabU^{ab}, so V2=UV^2=U. For the Toffoli, V=XV=\sqrt X.

Further reading

  • A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin & H. Weinfurter, "Elementary gates for quantum computation", Phys. Rev. A 52, 3457 (1995).
  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §4.3 (Cambridge, 10th anniv. ed., 2010).
  • B. Kraus & J. I. Cirac, "Optimal creation of entanglement using a two-qubit gate", Phys. Rev. A 63, 062309 (2001).
  • V. V. Shende, I. L. Markov & S. S. Bullock, "Minimal universal two-qubit controlled-NOT-based circuits", Phys. Rev. A 69, 062321 (2004).
  • C. Gidney, "Halving the cost of quantum addition", Quantum 2, 74 (2018).