Universality of CNOT with Single-Qubit Gates

Derivation

Universality of CNOT with Single-Qubit Gates

D-409 Home PU-404 Threads symmetry Depends on spectral-theorem-hermitian-operators, unitary-time-evolution

Statement

The gate set consisting of the two-qubit controlled-NOT together with the full continuous group of single-qubit unitaries is exactly universal: for every \( n \) and every \( U \in U(2^n) \) there is a finite circuit of CNOTs and single-qubit gates whose overall action equals \( U \) exactly (not merely to within \( \varepsilon \)). Equivalently, the group generated by CNOT on any qubit pair and by \( U(2) \) on every qubit is all of \( U(2^n) \).

Why it matters

This is the structural foundation of gate-model quantum computation. It tells us that an arbitrarily complicated coherent transformation of an \( n \)-qubit register can be broken into a sequence of operations from a tiny, physically realisable menu: one fixed entangling gate plus arbitrary local rotations. Every compiler that turns an abstract algorithm into hardware pulses relies on this reduction.

It also sharpens what "power" means. Universality is a statement about reachability, not cost: the same theorem that guarantees any \( U \) can be built also forces us to confront that a generic \( U \) demands exponentially many gates, which is why quantum advantage lives only in the structured unitaries that compile short.

Assumptions

Every element of \( U(2) \) is available on each qubit (a continuous gate set).If single-qubit gates are restricted to a finite set, exact universality is lost; the best possible statement becomes approximate universality via Solovay-Kitaev, and if the finite set is Clifford the circuit class is even efficiently classically simulable.

CNOT can be applied to any ordered pair of qubits.With limited connectivity the set stays universal but incurs SWAP overhead; if the connectivity graph is disconnected the two parts can never be entangled and universality fails on the joint register.

The evolution to be realised is a unitary on the closed \( 2^n \)-dimensional Hilbert space.Dropping unitarity (open-system, measurement-assisted, or dissipative dynamics) puts the target outside \( U(2^n) \); such channels need ancillas, measurement and reset, not covered by this theorem.

Circuits may be of any finite length, with no cost ceiling.If a polynomial depth bound is imposed, generic unitaries become unreachable, since almost all of \( U(2^n) \) requires \( \Omega(4^n/n) \) two-qubit gates.

Derivation

The proof is a three-stage descent: an arbitrary \( U \) becomes a product of two-level unitaries; each two-level unitary becomes a fully-controlled single-qubit gate; each controlled single-qubit gate becomes CNOTs and local rotations.

\[ U \in U(2^n),\qquad d \equiv 2^n \]

Fix the target as a \( d\times d \) unitary matrix in the computational basis \( \{|0\dots0\rangle,\dots,|1\dots1\rangle\} \). By the spectral theorem \( U \) is unitarily diagonalisable, but here we instead factorise it constructively. A

\[ U \;=\; U_{1}\,U_{2}\cdots U_{N},\qquad N \le \tfrac{d(d-1)}{2}=2^{\,n-1}\!\left(2^{n}-1\right) \]

Every \( d\times d \) unitary is a product of two-level unitaries — unitaries that act as the identity outside a two-dimensional coordinate subspace \( \mathrm{span}\{|s\rangle,|t\rangle\} \). Construct them by a unitary Gaussian elimination: for column \( 1 \), left-multiply \( U \) by two-level rotations that successively zero the entries \( U_{21},U_{31},\dots \), driving the first column to \( \hat e_1 \); unitarity then forces the first row to \( \hat e_1^{\dagger} \). Repeat on the remaining \( (d-1)\times(d-1) \) block. The accumulated factors invert to give \( U \). C

\[ |s\rangle \xrightarrow{\text{Gray code}} |t\rangle,\qquad s=g_0,g_1,\dots,g_m=t,\quad d_H(g_{k},g_{k+1})=1 \]

A two-level unitary couples basis states \( |s\rangle,|t\rangle \) that may differ in several bits. Choose a Gray-code path \( g_0,\dots,g_m \) of computational-basis strings in which consecutive strings differ in exactly one bit. CNOTs conditioned on the shared bits permute \( |s\rangle\leftrightarrow|g_{m-1}\rangle \) so that the nontrivial \( 2\times2 \) action lands on two states differing in a single qubit \( q \), controlled on the other \( n-1 \) qubits. Uncompute the permutation afterwards. C

\[ \text{two-level }U_j \;\longrightarrow\; C^{\,n-1}\!\big(\tilde U\big),\qquad \tilde U\in U(2)\ \text{on qubit }q \]

After Step 3 the two-level unitary is a single-qubit gate \( \tilde U \) on qubit \( q \), executed only when the remaining \( n-1 \) qubits are all \( |1\rangle \): a multiply-controlled single-qubit gate \( C^{n-1}(\tilde U) \). It remains to build this from CNOT and \( U(2) \). B

\[ \tilde U \;=\; e^{i\alpha}\,R_z(\beta)\,R_y(\gamma)\,R_z(\delta),\qquad R_z(\theta)=e^{-i\theta Z/2},\ R_y(\theta)=e^{-i\theta Y/2} \]

The \( ZYZ \) Euler decomposition: any \( \tilde U\in U(2) \) factors into a global phase and three axis rotations, because \( \{R_y,R_z\} \) generate \( SU(2) \) and \( e^{i\alpha} \) supplies the determinant phase. This is exact for continuous single-qubit gates. B

\[ A=R_z(\beta)R_y(\tfrac{\gamma}{2}),\quad B=R_y(-\tfrac{\gamma}{2})R_z(-\tfrac{\delta+\beta}{2}),\quad C=R_z(\tfrac{\delta-\beta}{2}) \]

Barenco's construction. These three \( SU(2) \) elements satisfy \( ABC=I \): the \( R_y \) factors cancel and the \( R_z \) phases sum to zero, \( \beta-\tfrac{\delta+\beta}{2}+\tfrac{\delta-\beta}{2}=0 \). They are chosen so the \( X \)-conjugated product rebuilds \( \tilde U \). C

\[ X\,R_y(\theta)\,X=R_y(-\theta),\quad X\,R_z(\theta)\,X=R_z(-\theta)\ \Rightarrow\ A\,X\,B\,X\,C=R_z(\beta)R_y(\gamma)R_z(\delta) \]

Conjugating a \( y \)- or \( z \)-rotation by \( X \) flips its angle (\( XYX=-Y,\ XZX=-Z \)). Hence \( XBX=R_y(\tfrac{\gamma}{2})R_z(\tfrac{\delta+\beta}{2}) \), and \( A(XBX)C \) telescopes to the \( SU(2) \) part of \( \tilde U \). The \( X \)s are exactly the target-flips a CNOT applies when its control is \( |1\rangle \). C

\[ C^1(\tilde U)=\big(\,|1\rangle\!\langle1|\otimes A\,X\,B\,X\,C+|0\rangle\!\langle0|\otimes ABC\,\big)\cdot\big(P(\alpha)\otimes I\big),\quad P(\alpha)=\begin{pmatrix}1&0\\0&e^{i\alpha}\end{pmatrix} \]

Read off the singly-controlled gate: put \( C \), then CNOT, then \( B \), then CNOT, then \( A \) on the target, and the phase gate \( P(\alpha) \) on the control. When the control is \( |0\rangle \) the target sees \( ABC=I \); when it is \( |1\rangle \) it sees \( AXBXC=\tilde U \) up to \( e^{i\alpha} \), which \( P(\alpha) \) supplies. Only CNOT and single-qubit gates appear. C

\[ C^{\,n-1}(\tilde U)\ \text{built recursively via }C^2(V)\ \text{blocks with }V^2\ \text{a controlled root} \]

Extend from one control to \( n-1 \) controls. Using \( C^1(V) \) with \( V^2=\tilde U \), the identity \( C^2(\tilde U)=C^1(V)\,\mathrm{CNOT}\,C^1(V^{\dagger})\,\mathrm{CNOT}\,C^1(V) \) reduces two controls to one; iterating (optionally with a few ancilla qubits reset to \( |0\rangle \)) reduces \( n-1 \) controls to singly-controlled gates, all of which are CNOT + \( U(2) \) by Step 8. The recursion terminates in finitely many gates. C

\[ U=\prod_j U_j \;=\; \prod_j \big(\text{CNOTs}+U(2)\ \text{circuit for }U_j\big) \]

Concatenate the circuits for all \( N \) two-level factors from Step 2. The result implements \( U \) exactly using only CNOT and single-qubit gates, completing the descent. A

Result

\[ \boxed{\ \forall\,U\in U(2^n)\quad U=\prod_{k=1}^{M} G_k,\qquad G_k\in\{\mathrm{CNOT}\}\cup U(2),\quad M<\infty\ } \]

Reading. Any coherent \( n \)-qubit operation, however entangling, is an exact finite word in the two-letter alphabet {CNOT, arbitrary single-qubit gate}. CNOT is the sole source of entanglement; the local rotations supply all the continuous freedom. The word length is finite but for a generic \( U \) grows like \( 4^n \).

Units check. Gates are dimensionless unitary operators; rotation angles \( \beta,\gamma,\delta,\alpha \) are in radians (dimensionless). Both sides of the boxed identity are elements of \( U(2^n) \), so \( \det \) has modulus one and \( G^{\dagger}G=I \) throughout — the factorisation preserves norm, as required of a physical evolution.

Limiting cases

\( n=1 \): any target is a single-qubit gate already in the set; zero CNOTs needed.
\( U=U_1\otimes\cdots\otimes U_n \) a product of local gates: no CNOT required, one layer of single-qubit gates.
\( U \) diagonal in the computational basis: reduces to controlled-phase gates, i.e. CNOTs plus \( R_z \) rotations only.
\( U \) a permutation (classical reversible) unitary: collapses to a Toffoli/CNOT network with no continuous parameters.
\( n=2 \): the KAK (Cartan) decomposition gives every \( U\in SU(4) \) in at most three CNOTs.

Breaks when

The single-qubit set is finite. Exact universality is impossible because a finite gate set generates only a countable subgroup, while \( U(2^n) \) is uncountable; one can then only approximate (Solovay-Kitaev), and if the set is Clifford the Gottesman-Knill theorem makes the circuits efficiently classically simulable.
The entangling gate is removed. Single-qubit gates alone generate \( SU(2)^{\otimes n} \) up to phase — only product unitaries. No such circuit can create entanglement, so the reachable set has dimension \( 3n \) versus \( 4^n-1 \): exponentially deficient.
Connectivity is disconnected. If the qubits split into groups with no CNOT bridging them, cross-group entanglement is unreachable and the joint unitary group is not covered.
The target is non-unitary. Measurement-induced, dissipative or lossy maps are CPTP channels outside \( U(2^n) \); they require ancilla, measurement and reset, which this gate set alone does not provide.

Failure modes

Conflating exact universality (continuous \( U(2) \)) with approximate universality (a discrete dense set plus Solovay-Kitaev) — they are different theorems with different gate sets.
Equating universality with efficiency: believing "any \( U \) is reachable" implies "reachable with few gates". Generic unitaries need \( \Omega(4^n/n) \) CNOTs.
Dropping the control-phase gate \( P(\alpha) \) in the controlled-\( \tilde U \) construction: \( ABC=I \) fixes only the \( SU(2) \) part, so the global phase \( e^{i\alpha} \) is silently lost, yielding the wrong controlled gate.
Claiming CNOT alone is universal: with product-basis inputs it only realises classical reversible logic; it cannot make superpositions.
Convention slip \( R_z(\theta)=e^{i\theta Z} \) instead of \( e^{-i\theta Z/2} \): a factor-of-two and sign error that makes the Euler angles and the \( ABC \) identity fail to close.
Assuming a two-level unitary touches only one qubit: it acts on two basis strings that generally differ in several qubits, which is why the Gray-code step is needed.

Discussion

The physical content is that entanglement is the one non-local resource, and a single fixed entangler suffices to unlock all of it. CNOT plus local gates is not special to CNOT: any entangling two-qubit gate together with all single-qubit gates is universal. What the proof exposes is a clean separation of duties — the continuous, uncountable part of \( U(2^n) \) is carried entirely by the local \( U(2) \) rotations, while the discrete, combinatorial job of coupling qubits is done by copies of one entangling gate.

There is a complementary discrete story. Replacing continuous single-qubit gates by the finite set \( \{H,T\} \) (with CNOT) sacrifices exactness but keeps approximate universality: \( \{H,T\} \) is dense in \( SU(2) \), and the Solovay-Kitaev theorem compiles any single-qubit target to accuracy \( \varepsilon \) in \( O(\log^{c}(1/\varepsilon)) \) gates. Exact universality (this page) and efficient approximate universality are thus two faces of the same reachability question.

The deepest framing is Lie-algebraic controllability, which connects directly to unitary time evolution. If the available Hamiltonians are the single-qubit generators \( \{X_i,Y_i,Z_i\} \) and one two-body coupling \( H_{\mathrm{int}} \) that generates CNOT-type dynamics, the set of reachable unitaries is \( \exp \) of the dynamical Lie algebra — the smallest subalgebra of \( \mathfrak{su}(2^n) \) closed under commutation and containing those generators. Local generators alone span only \( \bigoplus_i \mathfrak{su}(2)_i \); the entangler's commutators \( [H_{\mathrm{int}},X_i] \) reach two-body terms, whose further brackets propagate to arbitrary weight, so the generated algebra fills all of \( \mathfrak{su}(2^n) \). Universality is precisely this algebra-generation statement, and \( U=e^{-iHt} \) then reaches every point of the group. Parameter counting gives the matching lower bound: \( \dim SU(2^n)=4^n-1 \), and each CNOT layer contributes \( O(n) \) free angles, forcing \( \Omega(4^n/n) \) two-qubit gates for a generic target.

Common misconceptions. Universality does not mean a quantum computer can compute non-computable functions — it means the gate set spans the whole unitary group, nothing about the Church-Turing boundary. Nor does it promise speedups: it is a statement about which operations exist, not which run fast. And "single-qubit gates plus CNOT" being universal does not make CNOT itself universal, nor local gates alone universal; both letters of the alphabet are indispensable.

Worked examples

Example 1 — Building the controlled-Hadamard from CNOT and rotations.

\[ H=\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\qquad H=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta) \]

Match the general \( ZYZ \) form entry by entry. Equal moduli \( 1/\sqrt2 \) force \( \cos\tfrac{\gamma}{2}=\sin\tfrac{\gamma}{2} \), so \( \gamma=\tfrac{\pi}{2} \). B

\[ \alpha=\frac{\pi}{2},\quad \beta=\pi,\quad \gamma=\frac{\pi}{2},\quad \delta=0 \]

Solving the four phase equations: the diagonal entries give \( e^{2i\alpha}=-1 \) and \( \beta+\delta=\pi \); the off-diagonal entries give \( \beta-\delta=\pi \). Hence the listed angles. B

\[ A=R_z(\pi)R_y(\tfrac{\pi}{4}),\quad B=R_y(-\tfrac{\pi}{4})R_z(-\tfrac{\pi}{2}),\quad C=R_z(-\tfrac{\pi}{2}),\quad P(\tfrac{\pi}{2})=S \]

Insert \( \beta=\pi,\gamma=\tfrac{\pi}{2},\delta=0 \) into the Barenco formulas of Step 6. Check \( ABC=R_z(\pi)R_z(-\tfrac{\pi}{2})R_z(-\tfrac{\pi}{2})=R_z(0)=I \). The phase gate is \( P(\tfrac{\pi}{2})=\mathrm{diag}(1,e^{i\pi/2})=S \). C

\[ C\text{-}H \;=\; \big(S\otimes I\big)\,\big(I\otimes A\big)\,\mathrm{CNOT}\,\big(I\otimes B\big)\,\mathrm{CNOT}\,\big(I\otimes C\big) \]

Reading. On the target: \( C \), then flip-by-CNOT, then \( B \), then flip-by-CNOT, then \( A \); on the control apply \( S \). Control \( |0\rangle \) gives \( ABC=I \); control \( |1\rangle \) gives \( AXBXC=H \) up to \( e^{i\pi/2} \), fixed by \( S \). Two CNOTs and five single-qubit gates realise controlled-Hadamard exactly.

Units check. All angles in radians; every factor is in \( SU(2) \) or \( U(2) \), and the product is a \( 4\times4 \) unitary — the controlled-\( H \) as intended.

Example 2 — Toffoli (doubly-controlled NOT) as CNOT + single-qubit gates.

\[ \mathrm{Toffoli}=C^{2}(X),\qquad V=\sqrt{X}=\frac{1}{2}\begin{pmatrix}1+i&1-i\\1-i&1+i\end{pmatrix} \]

Choose \( V \) with \( V^{2}=X \). Compute \( V^{2}=\tfrac14\!\left[(1+i)^2+(1-i)^2\right] \) on the diagonal \( =\tfrac14(2i-2i)=0 \), and off-diagonal \( =\tfrac14\!\left[2(1+i)(1-i)\right]=\tfrac14\cdot4=1 \); so \( V^2=X \). B

\[ C^{2}(X)=C^{1}_{2,3}(V)\,\mathrm{CNOT}_{1,2}\,C^{1}_{2,3}(V^{\dagger})\,\mathrm{CNOT}_{1,2}\,C^{1}_{1,3}(V) \]

The two-control-to-one reduction of Step 9. When either control is \( |0\rangle \) the \( V \) and \( V^{\dagger} \) cancel; when both are \( |1\rangle \) the target sees \( V\cdot V=X \). Each \( C^1(V) \) is CNOT + single-qubit by Step 8. C

\[ \text{gate count: }\;6\ \text{CNOTs}\; +\; 9\ \text{single-qubit gates (}H,T,T^{\dagger}\text{ form)} \]

Expanding the three controlled-\( V^{(\dagger)} \) blocks into CNOT + rotations and merging adjacent single-qubit gates gives the textbook Toffoli circuit. \( V \) and \( V^{\dagger} \) are realised with \( H \) and \( T=\mathrm{diag}(1,e^{i\pi/4}) \). C

\[ \boxed{\ \mathrm{Toffoli}\ =\ \text{6 CNOTs}\ +\ \text{single-qubit }H,T,T^{\dagger}\ } \]

Reading. The archetypal three-qubit gate, which is universal for classical reversible computation, needs exactly six two-qubit entangling gates plus local rotations — a concrete instance of the general descent, and a common cost benchmark for fault-tolerant compilation.

Units check. \( V^2=X \) confirms \( V \) is a genuine unitary square root (dimensionless, \( \det V=i \)); the full circuit is an \( 8\times8 \) permutation-type unitary, matching \( C^2(X) \).

Problems

For \( n=3 \), give the maximum number of two-level unitaries needed to express an arbitrary \( U\in U(8) \).
Solution
The bound is \( \tfrac{d(d-1)}{2} \) with \( d=2^3=8 \): \( \tfrac{8\cdot7}{2}=28 \) two-level unitaries.
Prove \( X\,R_y(\theta)\,X=R_y(-\theta) \).
Solution
\( R_y(\theta)=\begin{pmatrix}\cos\tfrac{\theta}{2}&-\sin\tfrac{\theta}{2}\\ \sin\tfrac{\theta}{2}&\cos\tfrac{\theta}{2}\end{pmatrix} \). Conjugating by \( X=\begin{pmatrix}0&1\\1&0\end{pmatrix} \) swaps both rows and columns: \( X\,R_y(\theta)\,X=\begin{pmatrix}\cos\tfrac{\theta}{2}&\sin\tfrac{\theta}{2}\\ -\sin\tfrac{\theta}{2}&\cos\tfrac{\theta}{2}\end{pmatrix}=R_y(-\theta) \). Equivalently \( XYX=-Y \) so \( X e^{-i\theta Y/2}X=e^{+i\theta Y/2}=R_y(-\theta) \).
Find Euler angles \( (\alpha,\beta,\gamma,\delta) \) for the phase gate \( S=\mathrm{diag}(1,i) \), and state the controlled-\( S \) construction.
Solution
\( S \) is diagonal, so \( \gamma=0 \) and the gate is \( R_z \) up to phase: \( S=\mathrm{diag}(1,i)=e^{i\pi/4}\mathrm{diag}(e^{-i\pi/4},e^{i\pi/4})=e^{i\pi/4}R_z(\tfrac{\pi}{2}) \). Thus \( \alpha=\tfrac{\pi}{4},\ \beta=\tfrac{\pi}{2},\ \gamma=0,\ \delta=0 \) (any split of \( \beta+\delta=\tfrac{\pi}{2} \) works since \( \gamma=0 \)). Controlled-\( S \) is a controlled-phase; with \( A=R_z(\tfrac{\pi}{4}),B=R_z(-\tfrac{\pi}{4}),C=I \), \( ABC=I \), and the control carries \( P(\tfrac{\pi}{4})=T \). So \( C\text{-}S=(T\otimes I)(I\otimes A)\,\mathrm{CNOT}\,(I\otimes B)\,\mathrm{CNOT} \).
Show that SWAP is realised by three CNOTs, hence lies in the gate set.
Solution
\( \mathrm{SWAP}=\mathrm{CNOT}_{1,2}\,\mathrm{CNOT}_{2,1}\,\mathrm{CNOT}_{1,2} \). Track a basis state \( |a,b\rangle \): after \( \mathrm{CNOT}_{1,2} \) it is \( |a,a\oplus b\rangle \); after \( \mathrm{CNOT}_{2,1} \), \( |a\oplus(a\oplus b),a\oplus b\rangle=|b,a\oplus b\rangle \); after \( \mathrm{CNOT}_{1,2} \), \( |b,b\oplus(a\oplus b)\rangle=|b,a\rangle \). So \( |a,b\rangle\mapsto|b,a\rangle \), which is SWAP. No single-qubit gates are even needed.
Using \( \dim SU(2^n)=4^n-1 \) and the fact that each CNOT contributes at most \( O(n) \) continuous single-qubit parameters, give the parameter-counting lower bound on the number of CNOTs for a generic \( U\in SU(2^n) \).
Solution
A generic target sits in a manifold of real dimension \( 4^n-1 \). Each CNOT, flanked by single-qubit gates, introduces a bounded number of independent real angles — at most \( c\,n \) for some constant \( c \) (three angles per qubit touched, plus phases). To match \( 4^n-1 \) parameters the circuit needs at least \( \dfrac{4^n-1}{c\,n}=\Omega\!\left(\dfrac{4^n}{n}\right) \) CNOTs. Hence generic unitaries require exponentially many entangling gates, even though universality guarantees finiteness.