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-U'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) and prove Λ(eiαI)=P(α)⊗I: controlled global phases are physical.
Prove the ABC theorem and assemble Λ(U) from two CNOTs, three single-qubit gates and one phase gate.
Prove, with an entanglement argument, that Λ(U) needs zero, one or two CNOTs according to the eigenphase gap of U.
Build Λ2(U) from singly controlled V with V2=U, and state the gate-count scaling of Λk(U) with and without ancillas.
Controlled gates and the reappearing phase
DerivationControlled phases are physical
Λ(eiαV)=∣0⟩⟨0∣⊗I+eiα∣1⟩⟨1∣⊗V=Λ(eiαI)Λ(V)
Factor the phase out of the ∣1⟩ block.
Λ(eiαI)=diag(1,1,eiα,eiα)=P(α)⊗I
A controlled global phase is a phase gate on the control.
Λ(T)=(P(8π)⊗I)Λ(Rz(4π)),Λ(Rz(2π))=Λ(−I)=Z⊗I
Gates that are identical in isolation (T≃Rz(π/4), Rz(2π)≃I) differ once controlled. A compiler that drops global phases must restore them before adding controls.
Check your understanding
What is Λ(Rx(2π))?
I⊗I
Z⊗I
I⊗X
−I⊗I
Show the answer
B.Z⊗I
Rx(2π)=cosπI−isinπX=−I, so Λ(Rx(2π))=Λ(−I)=P(π)⊗I=Z⊗I.
Merge adjacent rotations; XRy(θ)X=Ry(−θ) and XRz(θ)X=Rz(−θ) flip the angles inside B. (Details in Euler Decompositions.)
control ∣0⟩:ABC=I,control ∣1⟩:eiαAXBXC=U
In the circuit, C acts first, then a CNOT, B, a CNOT and A. The phase gate P(α) on the control commutes with everything else, because every other gate is block-diagonal in the control's basis. ∎
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
CP(φ)=(P(2φ)⊗I)CNOT(I⊗P(−2φ))CNOT(I⊗P(2φ))
The claim; the rightmost factor acts first.
∣a,b⟩↦ei2φ(b−(a⊕b)+a)∣a,b⟩
Track the phases: P(2φ) sees the bit b, then P(−2φ) sees the XOR a⊕b, and P(2φ) on the control sees a. The second CNOT restores b.
a+b−(a⊕b)=2ab⟹∣a,b⟩↦eiφab∣a,b⟩
The bit identity a⊕b=a+b−2ab finishes the proof. This is the simplest phase polynomial; the seven-T Toffoli uses the same trick in three variables.
Check your understanding
What is the minimum number of CNOTs needed for Λ(S)?
0
1
2
3
Show the answer
C. 2
S=diag(1,i) has eigenphase gap λ=π/2≡0,π, so Λ(S)=CP(π/2) needs exactly two. Its best concurrence from a product input is sin4π≈0.71, short of the value 1 that any one-CNOT circuit reaches.
Many controls
Recursing on the lemma builds Λk(U) from two-qubit gates. Without ancillas this takes O(k2) 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) down to O(k). With k−2 clean ancillas, the textbook ladder uses 2k−3 Toffolis.
Key takeaways
Λ(eiαV)=(P(α)⊗I)Λ(V): the global phase of a controlled gate becomes a phase gate on the control.
ABC theorem: U=eiαAXBXC with ABC=I, so every Λ(U) needs at most two CNOTs.
Λ(U) is locally equivalent to CP(λ2−λ1): one CNOT iff the eigenphase gap is π, otherwise two (zero if U∝I).
Λ2(U) follows from controlled V with V2=U; recursion gives O(k2) gates for Λk(U) without ancillas and O(k) for Λ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⟩?
ABC, which equals I
A only
AXBXC
XBX
Show the answer
A.ABC, which equals I
With the control in ∣0⟩ the CNOTs do nothing, so the target sees C, then B, then A, i.e. the product ABC=I. The constraint ABC=I is exactly what makes the gate controlled.
Question 2
How do Λ(T) and Λ(Rz(π/4)) differ?
They are equal, since T≃Rz(π/4)
By Z on the control
By P(π/4) on the target
By P(π/8) on the control
Show the answer
D. By P(π/8) on the control
T=eiπ/8Rz(π/4), and a controlled phase eiπ/8 is P(π/8) on the control: Λ(T)=(P(8π)⊗I)Λ(Rz(4π)).
Question 3
For which U can Λ(U) be built from exactly one CNOT plus single-qubit gates?
Any U with detU=1
Any U whose two eigenvalues differ by a factor −1, such as X, Y, Z or H
Only U=X
Any diagonal U
Show the answer
B. Any U whose two eigenvalues differ by a factor −1, such as X, Y, Z or H
Λ(U) is locally equivalent to CP(λ) with λ the eigenphase gap, and one CNOT suffices exactly when λ≡π. That holds for every U∝n^⋅σ.
Question 4
In Barenco's construction of Λ2(U) from singly controlled gates, what must V satisfy?
V=U
V†=U
V2=U
V3=U
Show the answer
C.V2=U
For control bits (a,b) the target receives VbV−(a⊕b)Va=V2ab, which must equal Uab, so V2=U. For the Toffoli, V=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. A52, 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. A63, 062309 (2001).
V. V. Shende, I. L. Markov & S. S. Bullock, "Minimal universal two-qubit controlled-NOT-based circuits", Phys. Rev. A69, 062321 (2004).
C. Gidney, "Halving the cost of quantum addition", Quantum2, 74 (2018).