Exact two-qubit synthesis from single-qubit gates and CNOT
A self-contained, phase-exact proof that every two-qubit unitary is a finite product of arbitrary single-qubit U(2) gates and CNOT gates, with no ancillas. The proof proceeds by two-level elimination, Hamming-path relabeling, controlled-phase and controlled-U(2) constructions, and diagonal synthesis, and ends with an error analysis for finite gate sets.
§9.2Estimated reading time: 60 min
Introduction
A universal gate set is a small collection of elementary operations from which every quantum computation can be built, either exactly or to any desired accuracy. This note is a self-contained treatment of one foundational piece of that topic.
The companion single-qubit note proves that the gates H and T generate a dense set of single-qubit operations, and it states the Solovay–Kitaev theorem without proving it. It leaves open a different and more basic question: can single-qubit gates together with one entangling gate produce every operation on two qubits, exactly?
This note answers that question for two qubits. We prove the following.
Every 4×4 unitary matrix U equals a finite product of single-qubit unitary gates (arbitrary elements of U(2) acting on either qubit) and CNOT gates. The equality holds exactly, including the global phase, and uses no ancilla qubits. The construction uses at most 18 CNOT gates and at most 39 single-qubit gates.
The counts are what this particular construction guarantees. We do not claim they are optimal. Sharper constructions exist in the literature, but we neither use nor derive them here.
The proof has five steps, and each is a separate statement with its own proof.
Elimination. Any U∈U(4) can be reduced to a diagonal unitary by multiplying on the left by at most six two-level unitaries. This is the unitary analogue of QR factorization.
Relabeling. Any two-level unitary on the four computational basis vectors is a controlled single-qubit gate, possibly conjugated by one CNOT.
Controlled phase. The gate diag(1,1,1,eiφ) costs two CNOTs and three phase gates.
Controlled U(2). Any singly controlled U∈U(2) costs two CNOTs and four single-qubit gates. This requires a correctly chosen phase gate on the control qubit.
Diagonals. Any diagonal two-qubit unitary, global phase included, costs two CNOTs and three single-qubit gates.
After assembling these, we explain what changes when the arbitrary-angle single-qubit gates are replaced by the finite set {H,T}. Finally, we state, without proof, the n-qubit generalization from the primary literature.
Conventions
Every formula in this note depends on the following conventions. Most errors in gate synthesis come from silently switching one of them.
Basis and tensor order
There are two qubits, called qubit 1 and qubit 2. A computational basis state is written
∣ab⟩=∣a⟩⊗∣b⟩,a,b∈{0,1},
where a is the value of qubit 1 (the left tensor factor) and b is the value of qubit 2. The basis is ordered as
e0=∣00⟩,e1=∣01⟩,e2=∣10⟩,e3=∣11⟩,
so ∣ab⟩ is basis vector number 2a+b. All 4×4 matrices below are written in this ordered basis. For single-qubit matrices A and B, the operator A⊗B applies A to qubit 1 and B to qubit 2. Its matrix is the Kronecker block matrix (aijB)i,j.
We abbreviate W1=W⊗I and W2=I⊗W for a single-qubit gate W acting on qubit 1 or qubit 2.
Circuit order versus product order
A circuit applies its gates in time order g1,g2,…,gm. The first gate acts on the state first, so the circuit implements the operator
gmgm−1⋯g2g1.
Operator products are therefore read right to left. When a construction is given as a product, we also list its time order explicitly whenever confusion is possible.
Single-qubit gates
The single-qubit gate set is all of U(2), acting on either qubit. Some named elements:
The scalar gate eiχI∈U(2) is a legitimate single-qubit gate. Applying it to either qubit multiplies the whole two-qubit operator by eiχ. This is why exact synthesis including global phase is possible at all within this gate set.
CNOT and controlled gates
Definition 9.2.1
(Controlled single-qubit gate)
For a single-qubit W, a control qubit s, a target qubit t=s, and a control value c∈{0,1}, define Λcs→t(W) as the gate that
applies W to qubit t when qubit s is in state ∣c⟩, and
does nothing when qubit s is in state ∣1−c⟩.
A positive control is c=1. A negative control is c=0. With qubit 1 as control,
The negatively controlled versions X1CNOT1→2X1 and X2CNOT2→1X2 exchange 00↔01 and 00↔10, respectively.
Every CNOT, positively or negatively controlled, is its own inverse.
We allow CNOT in both orientations. An exercise below shows that CNOT2→1=(H⊗H)CNOT1→2(H⊗H). So a single orientation suffices at the cost of extra Hadamard gates, and the CNOT count is unchanged.
Two-level unitaries
Definition 9.2.2
(Two-level unitary)
Let x=y be two basis labels, taken as an ordered pair, and let
M=(m11m21m12m22)∈U(2).
The two-level unitaryTx,y(M) is the linear map defined by
with every other basis vector left fixed. In other words, Tx,y(M) acts as M on span(∣x⟩,∣y⟩) with ∣x⟩ playing the role of the first coordinate, and as the identity on the orthogonal complement. It is unitary because it is a direct sum of unitaries. Two facts follow directly from the definition:
Tx,y(M)†=Tx,y(M†),Ty,x(M)=Tx,y(XMX).
For the second identity, listing the pair in the order (y,x) instead of (x,y) permutes both the rows and the columns of the 2×2 block, and that permutation is exactly conjugation by X. The order of the pair matters whenever M is not invariant under this swap.
What "exact" means
Definition 9.2.3
(Exact implementation)
A circuit exactly implementsU if the product of its gate matrices equals U as a 4×4 matrix. Equality up to a global phaseeiχ is a strictly weaker notion. We will see why the stronger notion matters as soon as gates are controlled.
Zero pivots. The formula needs no special treatment when the would-be pivot a is zero. If a=0 and b=0, then r=∣b∣ and
M=(0−b/∣b∣bˉ/∣b∣0),
a "phased swap" that moves the nonzero entry into the pivot position. The only case that needs separate treatment is b=0, where the entry is already zero and nothing should be done. In particular, there is never a division by zero, and no case requires row exchanges outside the two-level framework.
The elimination theorem
Index rows and columns of a 4×4 matrix by 0,1,2,3. Fix the elimination schedule of six ordered pairs:
(0,1),(0,2),(0,3),(1,2),(1,3),(2,3).
In the step for the pair (k,j) with k<j, row k is the pivot row, and we annihilate the entry in row j, column k.
Theorem 9.2.5
(two-level elimination)
Let U∈U(4). There exist two-level unitaries G1,…,G6, where Gi=Tki,ji(Mi) for the i-th pair (ki,ji) of the schedule, and a diagonal unitary D=diag(d0,d1,d2,d3) with ∣dℓ∣=1, such that
G6G5G4G3G2G1U=D.
Some of the Gi may be the identity. These are exactly the steps in which the targeted entry is already zero.
Proof
(Zero by zero, then unitarity forces a diagonal)
Put U(0)=U and U(i)=GiU(i−1). At step i with pair (k,j)=(ki,ji), let a=Uk,k(i−1) and b=Uj,k(i−1). Choose Mi by the zeroing lemma for (a,b), and set Gi=Tk,j(Mi).
Left multiplication by Tk,j(M) changes only rows k and j:
new row k=m11(row k)+m12(row j),new row j=m21(row k)+m22(row j).
In column k, the pair of entries (a,b) becomes Mi(a,b)T, whose second entry is 0 by the zeroing lemma. So step i creates the zero at position (j,k).
We must also check that earlier zeros survive. Every zero created earlier sits at a position (j′,k′) with either
k′<k and j′>k′, or
k′=k and k<j′<j.
In the first case, consider column k′<k. Rows k and j both exceed k′, and column k′ was fully processed earlier, so both entries of column k′ in rows k and j are already 0. Any linear combination of them is again 0. In the second case, row j′ is neither k nor j, so it is untouched.
Hence, after all six steps, every entry strictly below the diagonal of W:=U(6) is zero, and W is upper triangular. As a product of unitaries, W is unitary. The triangular-unitary lemma below shows that an upper triangular unitary is diagonal with unimodular diagonal entries. Put D=W. ■
Lemma 9.2.6
(an upper triangular unitary is diagonal)
If W∈U(N) is upper triangular, then W is diagonal and ∣wℓℓ∣=1 for every ℓ.
Proof
(Induction on the column index)
We prove by induction on ℓ that column ℓ of W equals wℓℓeℓ, that ∣wℓℓ∣=1, and that row ℓ of W equals wℓℓeℓT.
Suppose this holds for all indices less than ℓ. Column ℓ has zeros below the diagonal because W is upper triangular. It also has zeros above the diagonal, because each row ℓ′<ℓ is wℓ′ℓ′eℓ′T, so wℓ′ℓ=0. Thus column ℓ is wℓℓeℓ. Columns of a unitary have norm 1, so ∣wℓℓ∣=1.
For m>ℓ, orthogonality of columns ℓ and m gives
0=⟨wℓℓeℓ,colm⟩=wℓℓwℓm.
Since wℓℓ=0, we get wℓm=0, so row ℓ is wℓℓeℓT. The base case ℓ=0 is the same argument with no previous rows. ■
The diagonal entries of D are unimodular but not necessarily 1. For example, if U is already diagonal, every step of the schedule is trivial and D=U. We therefore keep D as a general diagonal unitary and synthesize it separately in the diagonal-unitary section.
Reconstruction: the inverse order
From G6⋯G1U=D, multiply on the left by G6†, then G5†, and so on. This gives
U=G1†G2†G3†G4†G5†G6†D.
Each Gi†=Tki,ji(Mi†) is again a two-level unitary on the same pair. Read as a circuit, from right to left, the time order is
D,G6†,G5†,G4†,G3†,G2†,G1†.
The last elimination step is undone first, and the first elimination step is undone last.
The order cannot be rearranged. Two-level unitaries on overlapping pairs generally do not commute. For instance, T0,1(X) and T1,2(X) are the transpositions (01) and (12) of basis vectors. Their products in the two orders are the two different 3-cycles. Writing U=G6†⋯G1†D would therefore be wrong in general.
Worked example 9.2.7
(Eliminating a column of equal entries)
Suppose the first column of U∈U(4) is 21(1,1,1,1)T. The three elimination steps for column 0 are as follows, with each Mi and the column after each step.
Pair (0,1). Here a=b=21, so r=21 and
M1=21(1−111).
The column becomes (21,0,21,21)T.
Pair (0,2). Here a=21, b=21, so r=21+41=23 and
M2=(2/3−1/31/32/3).
The column becomes (23,0,0,21)T.
Pair (0,3). Here a=23, b=21, so r=1 and
M3=(3/2−1/21/23/2).
The column becomes (1,0,0,0)T.
Each Mi has orthonormal rows, which confirms it is unitary. The final pivot equals 1, as it must, since the column is a unit vector and each step preserves its norm.
Worked example 9.2.8
(Eliminating SWAP, with a zero pivot)
Let SWAP∣ab⟩=∣ba⟩. Its matrix has columns e0,e2,e1,e3:
SWAP=1000001001000001.
Column 0. The column is e0, so the entries in rows 1,2,3 are already zero. Steps (0,1), (0,2) and (0,3) all have b=0, so G1=G2=G3=I.
Column 1, pair (1,2). Here a=SWAP1,1=0 and b=SWAP2,1=1. This is a zero pivot. The zeroing lemma gives r=1 and
M4=(0−110).
Left multiplication by G4=T1,2(M4) replaces row 1 by row 2, which is (0,1,0,0), and replaces row 2 by −(row 1), which is (0,0,−1,0). The result is
G4SWAP=diag(1,1,−1,1).
Remaining steps. Pairs (1,3) and (2,3) now have b=0, so G5=G6=I and D=diag(1,1,−1,1).
Reconstruction. We get SWAP=G4†D with G4†=T1,2((01−10)). To check, apply D first:
e0↦e0, e1↦e1, e2↦−e2, e3↦e3.
Then apply G4†:
e1↦e2 (first column of the block),
−e2↦−(−e1)=e1 (second column of the block).
Altogether e0↦e0, e1↦e2, e2↦e1, e3↦e3, which is SWAP. The sign in D is essential. Without it the reconstruction would produce e2↦−e1.
Two-level unitaries as controlled gates
Adjacent pairs
View the four labels 00,01,10,11 as the vertices of a square. Two labels are joined by an edge when they differ in exactly one bit, that is, when their Hamming distance is 1. The square is the 4-cycle
00−01−11−10−00.
Any two distinct labels are either adjacent (distance 1) or antipodal (distance 2). An antipodal pair has exactly two shortest paths through the square, each passing through one intermediate vertex.
Lemma 9.2.9
(adjacent two-level unitaries are singly controlled gates)
Let x and y differ exactly in qubit t, and let s be the other qubit, with common value c on both labels.
If x has qubit t equal to 0 (and therefore y has it equal to 1), then Tx,y(M)=Λcs→t(M).
If x has qubit t equal to 1, then Tx,y(M)=Λcs→t(XMX).
Proof
(Matching the ordered basis)
The basis vectors with qubit s equal to 1−c are fixed by both sides. The basis vectors with qubit s equal to c are exactly ∣x⟩ and ∣y⟩. On them, Λcs→t(W) applies W to qubit t in the ordered basis (∣0⟩,∣1⟩). If x carries target value 0, this ordered basis matches the ordered pair (x,y), so W=M. Otherwise the order is reversed, and Tx,y(M)=Ty,x(XMX)=Λcs→t(XMX). ■
Antipodal pairs: relabeling by a permutation
Lemma 9.2.10
(conjugating a two-level unitary by a permutation)
Let Q be a permutation matrix on basis vectors, and write Q∣x⟩=∣Qx⟩. Then for every M∈U(2),
QTx,y(M)Q−1=TQx,Qy(M).
Proof
(Evaluating on each basis vector)
We evaluate both sides on each basis vector.
At ∣Qx⟩: QTx,y(M)Q−1∣Qx⟩=QTx,y(M)∣x⟩=Q(m11∣x⟩+m21∣y⟩)=m11∣Qx⟩+m21∣Qy⟩, which matches the right-hand side.
At ∣Qy⟩: the same computation applies.
At any other ∣w⟩: the label Q−1w lies outside {x,y}, because Q−1 maps {Qx,Qy} bijectively onto {x,y} and hence maps the complement into the complement. So Tx,y(M) fixes ∣Q−1w⟩, and the left-hand side returns ∣w⟩. ■
Which endpoint is moved, and in which direction. To realize Tx,y(M) for an antipodal pair, choose one endpoint to move, say y, and an intermediate label z adjacent to both x and y. Then find a permutation Q with
Qx=xandQz=y.
Here Q sends the auxiliary label z to the original endpoint y. The conjugation lemma then gives
Tx,y(M)=QTx,z(M)Q−1.
In time order, apply Q−1 first, then the adjacent gate Tx,z(M), then Q.
The opposite conjugation Q−1Tx,z(M)Q equals TQ−1x,Q−1z(M). That is the right gate only if Q−1z=y. When Q is a single CNOT, Q=Q−1 and the two conventions coincide. They genuinely differ for composite permutations; the counterexample in the section on conjugation direction makes this concrete.
Moving an endpoint also changes which label comes first in the ordered pair, and therefore whether the adjacent-pair lemma needs M or XMX. In the pair (x,z) above, x is still first, so the block is still M. The adjacent-pair lemma must then be applied to (x,z) with attention to which of x and z has target bit 0.
The schedule realized as circuits
For the six pairs of the elimination schedule, write the labels in bits: 0=00, 1=01, 2=10, 3=11. Apply the adjacent-pair lemma directly to adjacent pairs, and the conjugation lemma with a single positively controlled CNOT to the two antipodal pairs.
Pair
Labels
Distance
Realization of Tx,y(M)
CNOTs
(0,1)
00,01
1
Λ01→2(M)
2
(0,2)
00,10
1
Λ02→1(M)
2
(0,3)
00,11
2
CNOT2→1Λ01→2(M)CNOT2→1
4
(1,2)
01,10
2
CNOT1→2Λ12→1(M)CNOT1→2
4
(1,3)
01,11
1
Λ12→1(M)
2
(2,3)
10,11
1
Λ11→2(M)
2
The CNOT column already includes the two CNOTs needed to implement each controlled-U(2) gate, which is proved in the section on the exact singly controlled U(2) gate.
The two antipodal rows work as follows.
Pair (0,3). Move y=11 to z=01 using Q=CNOT2→1. This Q fixes 00 and sends 01↦11. The adjacent gate is T00,01(M), which is Λ01→2(M) by the adjacent-pair lemma, since 00 has qubit 2 equal to 0.
Pair (1,2). Move y=10 to z=11 using Q=CNOT1→2. This Q fixes 01 and sends 11↦10. The adjacent gate is T01,11(M), which is Λ12→1(M), since 01 has qubit 1 equal to 0.
In every row the first label carries target bit 0, so the block is M itself, never XMX. This is a property of this particular schedule and these particular choices. It is not a general fact, as the exercise on antipodal pairs below illustrates.
The inverse factors Gi† use the same circuits with M replaced by M†.
Worked example 9.2.11
(A two-level rotation on |00⟩ and |11⟩)
Let
R=21(11−11).
This block is deliberately not swap-symmetric: XRX=21(1−111)=R. We want T00,11(R), whose defining action is
∣00⟩↦21(∣00⟩+∣11⟩),∣11⟩↦21(−∣00⟩+∣11⟩),
with ∣01⟩ and ∣10⟩ fixed. Its matrix is
T00,11(R)=21002101000010−210021.
Circuit. Take Q=CNOT2→1, which swaps 01↔11 and fixes 00 and 10. Then
T00,11(R)=QΛ01→2(R)Q,
with time order Q, then Λ01→2(R), then Q. The middle gate applies R to qubit 2 exactly when qubit 1 is 0. Concretely,
∣00⟩↦21(∣00⟩+∣01⟩),∣01⟩↦21(−∣00⟩+∣01⟩),
and it fixes ∣10⟩ and ∣11⟩.
All four basis inputs, traced through the circuit:
∣00⟩Q∣00⟩Λ21(∣00⟩+∣01⟩)Q21(∣00⟩+∣11⟩). ✓
∣01⟩Q∣11⟩Λ∣11⟩Q∣01⟩. ✓
∣10⟩Q∣10⟩Λ∣10⟩Q∣10⟩. ✓
∣11⟩Q∣01⟩Λ21(−∣00⟩+∣01⟩)Q21(−∣00⟩+∣11⟩). ✓
The output columns are (21,0,0,21)T, e1, e2 and (−21,0,0,21)T. These are exactly the columns of the matrix above.
Checking the block order. Suppose we had used Λ01→2(XRX) in the middle by mistake. Then ∣00⟩ would map to 21(∣00⟩−∣11⟩), which is a different gate. The block order is not cosmetic.
Remaining work. The negative control is Λ01→2(R)=X1Λ11→2(R)X1. The exact singly controlled construction then supplies Λ11→2(R) from two CNOTs and single-qubit gates, so the whole two-level gate uses four CNOTs.
The controlled phase gate
Define the controlled phase
CP(φ)=diag(1,1,1,eiφ),so thatCP(φ)∣ab⟩=eiφab∣ab⟩.
It is symmetric in the two qubits: CP(φ)=Λ11→2(P(φ))=Λ12→1(P(φ)).
Proposition 9.2.12
(controlled phase from two CNOTs)
For every real φ,
CP(φ)=(P(2φ)⊗P(2φ))CNOT1→2(I⊗P(−2φ))CNOT1→2.
This is an exact equality, with no global phase discrepancy.
Proof
(Splitting the phase of a product of bits)
For bits a,b, the integer identity a+b=(a⊕b)+2ab gives
The gate P(−φ/2) on qubit 2 multiplies by e−iφ(a⊕b)/2.
The second CNOT restores ∣a,b⟩.
Finally, P(φ/2)⊗P(φ/2) multiplies by eiφa/2eiφb/2.
The total factor is eiφab. Explicitly, on ∣00⟩,∣01⟩,∣10⟩,∣11⟩ the factors are
1,eiφ/2e−iφ/2=1,eiφ/2e−iφ/2=1,eiφe0=eiφ.■
The three single-qubit gates in this formula are P(φ/2) on qubit 1, P(φ/2) on qubit 2, and P(−φ/2) on qubit 2.
A singly controlled U(2) gate, exactly
Let U∈U(2). Since U is normal, the spectral theorem gives a unitary V∈U(2) and real numbers α,β with
U=Vdiag(eiα,eiβ)V†.
Neither V nor the representatives α,β are unique. Any choice works, but the same real numbers α,β must be used everywhere below. Reducing one occurrence modulo 2π but not another can change a half-angle by an odd multiple of π and thereby break the identity.
So Λ11→2(U)=(I⊗V)Λ11→2(Δ)(I⊗V†). Next, Λ11→2(Δ) is diagonal, and it splits into a phase on the control and a controlled phase:
Λ11→2(Δ)=diag(1,1,eiα,eiβ)=(P(α)⊗I)CP(β−α).
To check this, the right-hand side is diag(1,1,eiα,eiα)⋅diag(1,1,1,ei(β−α)).
Now insert the controlled-phase proposition with φ=β−α. The factors P(α)⊗I and P(φ/2)⊗P(φ/2) merge with the leftmost I⊗V into
P(α+2φ)⊗VP(2φ),
because a gate on qubit 1 commutes with a gate on qubit 2. Since α+2φ=2α+β and 2φ=2β−α, this is the claimed formula. ■
Proof X-ray
Where the half-angles and the scalar come from
The derivation has three moving parts, and each can be audited separately. Diagonalizing U=VΔV† is used once, to move all non-diagonal structure onto the target: the control only decides whether the target operator is applied, so conjugating the target by V conjugates the controlled gate. The key move is the splitting diag(1,1,eiα,eiβ)=(P(α)⊗I)CP(β−α), which leaves a controlled phase as the only genuinely two-qubit factor.
The scalar is the subtle point. On the control-1 branch both CNOTs act as X on the target, and XP(θ)X=diag(eiθ,1)=eiθP(−θ). A scalar on the target is invisible on its own, but here it appears on one control branch only, so it is a relative phase. With θ=(α−β)/2 it contributes ei(α−β)/2, and the gate P(2α+β) on qubit 1 contributes ei(α+β)/2. Together they give exactly eiα.
The two branches then close. On control 0 the CNOTs are inactive and the target sees VP(2β−α)P(2α−β)V†=I. On control 1 it sees
eiαVdiag(1,ei(β−α))V†=U.
Dropping the control-qubit gate, or using different representatives of α,β in different factors, can change the control-1 branch to eiχU with χ≡0, as the counterexample below shows.
Variants
Control on qubit 2, target qubit 1. Swap the roles of the two qubits throughout and use CNOT2→1. The proof is identical.
Negative control. Use Λ0s→t(U)=XsΛ1s→t(U)Xs. This adds two single-qubit gates on the control and no CNOTs.
Arbitrary two-level blocks. By the adjacent-pair lemma the controlled gate may be Λ(M) or Λ(XMX). Both M and XMX are elements of U(2), so the controlled-U theorem applies to either controlled gate.
Counterexample mode
Dropping the conditional global phase
A tempting shortcut is: "Single-qubit gates only matter up to global phase, so to control U it suffices to control any W with W=eiχU." This is false.
Take U=−I=eiπI. A careless synthesis notes that U is "the identity up to phase" and implements Λ11→2(I)=I⊗I, that is, no gate at all. The true controlled gate is
Λ11→2(−I)=diag(1,1,−1,−1)=Z⊗I.
On the input ∣+⟩∣0⟩, where ∣+⟩=21(∣0⟩+∣1⟩):
the careless circuit outputs ∣+⟩∣0⟩;
the correct gate outputs ∣−⟩∣0⟩, where ∣−⟩=21(∣0⟩−∣1⟩).
These two states are orthogonal. A measurement of qubit 1 in the ∣±⟩ basis distinguishes them with certainty. The "global" phase of U has become a relative phase between the two branches of the control.
The same failure appears inside the controlled-U theorem. Replace the control gate P(2α+β) by P(2β−α), which amounts to forgetting the factor P(α)⊗I in the derivation. Then the control-1 branch receives e−iαU instead of U, and the circuit implements Λ11→2(e−iαU). That is exact only when eiα=1.
Diagonal two-qubit unitaries
Let D=diag(eiθ0,eiθ1,eiθ2,eiθ3) with real θℓ. Factor out the first entry and write
D=eiθ0diag(1,eiβ1,eiβ2,eiβ3),βℓ=θℓ−θ0.
Proposition 9.2.14
(diagonal synthesis)
With γ=β3−β1−β2,
D=(eiθ0P(β2)⊗P(β1))CP(γ).
Using the controlled-phase proposition and merging commuting factors, this becomes
The circuit uses two CNOTs and three single-qubit gates, and the equality holds exactly, global phase included.
Proof
(Comparing diagonal entries)
Compare diagonal entries. The factor P(β2)⊗P(β1) contributes ei(aβ2+bβ1) on ∣ab⟩, and CP(γ) contributes eiγab. The resulting entries are:
∣00⟩: eiθ0;
∣01⟩: eiθ0eiβ1=eiθ1;
∣10⟩: eiθ0eiβ2=eiθ2;
∣11⟩: eiθ0ei(β1+β2+γ)=eiθ0eiβ3=eiθ3.
The scalar eiθ0 is absorbed into the single-qubit gate on qubit 1, which remains an element of U(2). ■
The same idea explains the structure of every diagonal two-qubit unitary. The phase angle on ∣ab⟩ is a function of two bits, so it can be written as
θ0+β2a+β1b+γab.
The constant, linear and product terms are supplied, respectively, by a global phase, by single-qubit phase gates, and by one controlled phase.
Assembly: the main theorem
Theorem 9.2.15
(exact two-qubit universality)
Every U∈U(4) is exactly equal, including global phase, to a product of at most 18 CNOT gates and at most 39 single-qubit gates from U(2), acting on the two given qubits only.
Proof
(Counting gates in the assembled factorization)
By the elimination theorem and the reconstruction formula,
U=G1†G2†G3†G4†G5†G6†D.
The diagonal factor. Synthesize D by the diagonal-synthesis proposition, using 2 CNOTs and 3 single-qubit gates.
The two-level factors. Each Gi†=Tki,ji(Mi†) is realized as in the schedule table, with the controlled-U theorem supplying the controlled gates.
Each positively controlled Λ1(⋅) costs 2 CNOTs and 4 single-qubit gates.
Each negatively controlled Λ0(⋅) costs 2 CNOTs and at most 6 single-qubit gates.
The antipodal pairs add 2 positively controlled CNOTs and no single-qubit gates.
So each two-level factor costs at most 6 single-qubit gates. Its CNOT cost is 2 for the four adjacent pairs and 4 for the two antipodal pairs.
Every equality used along the way is exact, so the product equals U exactly. Any Gi that equals the identity can be omitted, which only lowers the counts. ■
Remarks on the counts.
The bounds hold for everyU. They are what this construction guarantees, not lower bounds, and certainly not optimal values.
Adjacent CNOTs and single-qubit gates in the assembled circuit can often be merged or canceled. We do not pursue such simplifications, so we claim nothing beyond the stated bounds.
If only CNOT1→2 is available, each CNOT2→1 can be replaced by (H⊗H)CNOT1→2(H⊗H) (see the exercise below on conjugating CNOT by Hadamard gates). The CNOT bound stays 18, and each replaced CNOT adds at most 4 Hadamard gates to the single-qubit count.
Conjugation direction for composite permutations
For two qubits, a single CNOT always suffices for the relabeling in the section on two-level unitaries, and a single CNOT is an involution. On larger registers, the permutation that moves an endpoint along a longer Hamming path is a product of CNOT-type gates, and such products are generally not involutions. The following two-qubit example shows how much the choice between QGQ−1 and Q−1GQ then matters.
Counterexample mode
P G P⁻¹ versus P⁻¹ G P
Let Q=CNOT1→2CNOT2→1. In time order, CNOT2→1 acts first and then CNOT1→2. On labels:
00↦00,01↦11↦10,10↦10↦11,11↦01↦01.
So Q fixes 00 and acts on the other three labels as the 3-cycle 01→10→11→01, and Q−1 is the reverse cycle. Let G=T00,01(M). By the conjugation lemma,
These two conjugates act on different pairs of basis vectors. To realize the two-level gate on (00,11) from G with this Q, one must use Q−1GQ. With the time order made explicit, that means applying Q first, then G, then Q−1=CNOT2→1CNOT1→2.
The safe rule is the conjugation lemma itself. Conjugate by whichever permutation sends the auxiliary label to the original endpoint, and place that permutation on the left of G, with its inverse on the right.
From arbitrary angles to a finite gate set
The universality theorem uses arbitrary elements of U(2): arbitrary real angles, specified exactly. That is a mathematical idealization. A fault-tolerant or compiled setting typically offers a finite set such as {H,T,CNOT}, and that changes what can be claimed.
Exactness is lost
Only countably many finite circuits can be formed from a finite gate set, while U(4) is uncountable. Even after identifying unitaries that differ by a global phase, uncountably many classes remain. So all but countably many two-qubit unitaries cannot be realized exactly by H, T and CNOT. For a finite gate set, the right goal is approximation.
The density input
From the companion note we use density in the following form. For every W∈U(2) and every δ>0, there is a finite word w in H and T and a real χ with
∥w−eiχW∥≤δ.
Here ∥⋅∥ denotes the operator norm. The phase eiχ appears because density is a statement modulo global phase. CNOT needs no approximation.
Errors add, at worst, linearly
Lemma 9.2.16
(telescoping bound)
Let V1,…,Vm and V~1,…,V~m be unitaries on the same space, and suppose ∥V~j−Vj∥≤εj for each j. Then
To see this, note that consecutive terms cancel. The j-th term equals Aj−Aj−1, where Aj=Vm⋯Vj+1V~j⋯V~1, with Am the fully approximate product and A0 the exact product. Multiplying an operator by unitaries on either side does not change its operator norm. So the j-th term has norm at most εj, and the triangle inequality finishes the proof. ■
Two remarks.
A single-qubit gate embedded in the two-qubit space satisfies ∥(W~−W)⊗I∥=∥W~−W∥. So single-qubit errors transfer unchanged to the two-qubit setting.
If ∥V~j−eiχjVj∥≤εj, apply the telescoping lemma to the unitaries eiχjVj. The conclusion becomes ∥U~−eiχU∥≤j∑εj with χ=j∑χj.
Consequence for the universality theorem. Fix ε>0. Replace each of the at most 39 single-qubit gates by an {H,T}-word within δ=ε/39 of it, up to phase, and keep the CNOTs exact. The resulting circuit U~ satisfies
∥U~−eiχU∥≤ε
for some real χ.
Effect on measurement statistics. Let Π be an orthogonal projector and let u=eiχUψ and v=U~ψ for a unit vector ψ. Then ∥u−v∥≤ε. Since ∥Πu∥,∥Πv∥≤1 and the reverse triangle inequality gives ∥Πu∥−∥Πv∥≤∥Π(u−v)∥≤ε, we get
∥Πu∥2−∥Πv∥2=∥Πu∥−∥Πv∥⋅(∥Πu∥+∥Πv∥)≤2ε.
So every outcome probability differs by at most 2ε. The global phase eiχ does not affect these probabilities.
Two caveats
The lost phase can come back. The approximation is only up to the global phase eiχ. That is harmless for a stand-alone circuit. If the approximated circuit is later used as the target of a control, however, the counterexample in the section on the exact singly controlled gate shows that eiχ becomes a relative phase. In that situation, one must either track and correct the phase or approximate the controlled operation directly.
Density gives no length bound. The density statement guarantees that suitable words exist, but says nothing about how long they are. The companion note states, without proof, the Solovay–Kitaev theorem, which asserts that word lengths can be kept polylogarithmic in 1/δ. Nothing in this note depends on that theorem.
Beyond two qubits (stated, not proved)
The argument of the elimination theorem works verbatim for U∈U(N). With N=2n, it yields at most N(N−1)/2 two-level factors followed by a diagonal unitary. The triangular-unitary lemma also holds in every dimension.
What does not carry over from this note is the implementation of a two-level unitary on n>2 qubits. That step requires gates with several controls and Gray-code relabelings by multiply controlled NOTs, and building those from CNOT and single-qubit gates without ancillas requires further constructions that we have not proved here.
Known theorem (Barenco et al., 1995; stated without proof). For every n≥1, every unitary on n qubits can be written exactly as a finite product of CNOT gates and single-qubit unitary gates.
Existence says nothing about efficiency. In particular, it does not imply that a generic n-qubit unitary has a circuit of size polynomial in n. Already the number of two-level factors produced by elimination grows like 4n. Universality is a statement about what can be built, not about what can be built cheaply.
Common mistakes and subtle points
Common mistake
(Reversing the order of products)
A circuit with gates g1 then g2 implements g2g1, not g1g2. The same care applies to the reconstruction: the correct formula is U=G1†⋯G6†D, because two-level factors on overlapping pairs need not commute. Also, the diagonal factor D left by elimination is a general unimodular diagonal matrix, not I, and must be synthesized.
Common mistake
(Using the wrong block or the wrong conjugation)
In general Tx,y(M)=Ty,x(M): when the first label carries target bit 1, the adjacent-pair lemma needs XMX. Likewise the rule is QTx,zQ−1=TQx,Qz, and for a non-involutive Q the two conjugation orders give different gates.
Common mistake
(Controlling a gate only up to phase)
Controlling eiχU instead of U changes the gate by P(χ) on the control. The half-angles in the controlled-U theorem and the controlled-phase proposition must also use the same real α,β,φ throughout, since reducing one occurrence modulo 2π but not another breaks the identity.
Exercises
Exercise 9.2.17
(Prove that CNOT2→1=(H⊗H)CNOT1→2(H⊗H).)
CoreProof
Solution(3)
1
Conjugate the projector form of CNOT
Write
CNOT1→2=∣0⟩⟨0∣⊗I+∣1⟩⟨1∣⊗X.
Use H∣0⟩⟨0∣H=∣+⟩⟨+∣, H∣1⟩⟨1∣H=∣−⟩⟨−∣, HIH=I and HXH=Z. Conjugation by H⊗H gives
∣+⟩⟨+∣⊗I+∣−⟩⟨−∣⊗Z.
2
Collect terms by the qubit-2 projector
Expand I=∣0⟩⟨0∣+∣1⟩⟨1∣ and Z=∣0⟩⟨0∣−∣1⟩⟨1∣, and collect terms by the qubit-2 projector:
(Use the controlled-phase proposition to write CZ=diag(1,1,1,−1) with two CNOTs, and verify it on all four basis states.)
Foundation
Solution(2)
1
Specialize the controlled-phase formula to φ=π
Take φ=π. Then
CZ=(S⊗S)CNOT1→2(I⊗S†)CNOT1→2.
2
Check the four basis states
The factor on ∣ab⟩ is iaib(−i)a⊕b:
∣00⟩: 1;
∣01⟩: i⋅(−i)=1;
∣10⟩: i⋅(−i)=1;
∣11⟩: i⋅i⋅1=−1.
Exercise 9.2.19
(Realize T01,10(M) for an arbitrary M∈U(2) using one relabeling CNOT and one controlled gate, and verify all four basis outputs. Then explain what changes for T10,01(M).)
Synthesis
Solution(3)
1
Move the endpoint with one CNOT
Move y=10 to z=11 using Q=CNOT1→2. This Q fixes 01 and sends 11↦10. By the conjugation lemma,
T01,10(M)=QT01,11(M)Q.
2
Trace the four basis inputs
The labels 01 and 11 differ in qubit 1, with qubit 2 equal to 1, and 01 has qubit 1 equal to 0. So the adjacent-pair lemma gives T01,11(M)=Λ12→1(M). Tracing each basis input:
∣01⟩Q∣01⟩Λm11∣01⟩+m21∣11⟩Qm11∣01⟩+m21∣10⟩;
∣10⟩Q∣11⟩Λm12∣01⟩+m22∣11⟩Qm12∣01⟩+m22∣10⟩;
∣00⟩Q∣00⟩Λ∣00⟩Q∣00⟩, because qubit 2 is 0;
∣11⟩Q∣10⟩Λ∣10⟩Q∣11⟩.
These match the definition of T01,10(M).
3
Reverse the order of the pair
For T10,01(M)=T01,10(XMX), the same circuit works with Λ12→1(XMX) in the middle. Equivalently, one can move the endpoint 10 to 11 and treat 11 as the first label of the pair (11,01). Then the adjacent-pair lemma again requires XMX, because 11 carries target bit 1.
Exercise 9.2.20
(Compute Λ11→2(eiχI). For which χ does it equal I⊗I?)
Foundation
Solution(2)
1
Compute the controlled scalar
Λ11→2(eiχI)=diag(1,1,eiχ,eiχ)=P(χ)⊗I.
2
Read off when it is the identity
This equals I⊗I exactly when eiχ=1. For any other χ, a scalar on the target becomes a nontrivial phase gate on the control. In the controlled-U theorem this is precisely the role of the control-qubit gate.
Exercise 9.2.21
(Using the controlled-U theorem, synthesize Λ11→2(X), a CNOT, from two CNOTs. Confirm that the formula is consistent even in this deliberately roundabout case.)
Core
Solution(3)
1
Choose V, α and β
We have X=Hdiag(1,−1)H†, so we may take V=H, α=0, β=π. The controlled-U theorem gives
Λ11→2(X)=(S⊗HS)CNOT1→2(I⊗S†)CNOT1→2(I⊗H).
2
Check the control-0 branch
Control 0. Qubit 2 receives HSS†H=I.
3
Check the control-1 branch
Control 1. The phase gate on qubit 1 contributes eiπ/2=i, and qubit 2 receives HSXS†XH. Since XS†X=diag(−i,1)=−iS, this is
HS(−iS)H=−iHZH=−iX.
The total on the control-1 branch is i⋅(−iX)=X. So the formula is exact. It is also wasteful, which illustrates that the construction makes no claim to optimality.
Exercise 9.2.22
(A circuit from the universality theorem has 39 single-qubit gates. Each is replaced by an {H,T}-word within 10−4 of it, up to phase, in operator norm. Bound the error of the resulting circuit and the change in any outcome probability.)
Foundation
Solution(2)
1
Bound the circuit error by telescoping
By the telescoping lemma, together with the remark on phases,
∥U~−eiχU∥≤39⋅10−4=3.9×10−3.
2
Bound the outcome probabilities
By the measurement bound, every outcome probability changes by at most 2⋅3.9×10−3=7.8×10−3. No bound on the lengths of the words follows from density alone.
Related notes and prerequisites
Single-qubit gates and density of {H,T} (companion note). This note uses its density result and its statement, not proof, of Solovay–Kitaev.
Prerequisites. Linear algebra: unitary matrices, the spectral theorem for normal matrices, the operator norm, and tensor products.
Reference
A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, "Elementary gates for quantum computation," Physical Review A52, 3457 (1995). arXiv:quant-ph/9503016. Cited for historical context and for the n-qubit theorem stated above.