Simple Algorithm
Quantum Computing · Excited State · 22 min

Universality & Gate Sets

A finite set of gates can approximate any computation.

Your hardware offers a handful of gates, yet quantum programs form a continuum. How can a finite menu run every computation? The answer, approximate universality, turns out to be surprisingly cheap.

What you’ll learn

  • Define approximate universality with the operator norm, and prove that gate errors add at most linearly.
  • Explain why CNOT plus single-qubit gates is exactly universal, and why generic unitaries still cost exponentially many gates.
  • Show that HH and TT generate a rotation by an irrational angle, and hence a dense set of single-qubit gates.
  • Compare the cost of approximation: Solovay–Kitaev's O(log⁡c(1/ε))\order{\log^c(1/\varepsilon)} versus the Ω(log⁡(1/ε))\Omega(\log(1/\varepsilon)) counting bound.
  • Classify common gate sets as universal or not, and explain why Clifford+T dominates fault-tolerant computing.

What "universal" can mean

A gate set is a menu of unitary operations on one or two qubits. Can a finite menu build every nn-qubit unitary exactly? No, for a counting reason: over a finite menu there are only countably many circuits, but uncountably many unitaries (already Rz(θ)R_z(\theta) for every real θ\theta).

So the right goal is approximation, and approximation needs a yardstick for the distance between two gates.

Why this norm? Two facts make it the right currency. First, if ∥U−V∥≤ε\norm{U-V}\le\varepsilon, then every outcome probability of every measurement after UU is within 2ε2\varepsilon of the one after VV. Second, the errors of a long circuit add up at most linearly:

DerivationErrors add at most linearly
  1. U2U1−V2V1=U2 (U1−V1)+(U2−V2) V1U_2U_1 - V_2V_1 = U_2\,(U_1 - V_1) + (U_2 - V_2)\,V_1

    Add and subtract U2V1U_2V_1.

  2. ∥U2U1−V2V1∥≤∥U2∥ ∥U1−V1∥+∥U2−V2∥ ∥V1∥\norm{U_2U_1 - V_2V_1} \le \norm{U_2}\,\norm{U_1 - V_1} + \norm{U_2 - V_2}\,\norm{V_1}

    Triangle inequality and ∥AB∥≤∥A∥ ∥B∥\norm{AB}\le\norm{A}\,\norm{B}.

  3. ∥U2U1−V2V1∥≤∥U1−V1∥+∥U2−V2∥\norm{U_2U_1 - V_2V_1} \le \norm{U_1 - V_1} + \norm{U_2 - V_2}

    Unitaries have norm 11.

  4. ∥Um⋯U1−Vm⋯V1∥≤∑j=1m∥Uj−Vj∥\norm{U_m\cdots U_1 - V_m\cdots V_1} \le \sum_{j=1}^{m}\norm{U_j - V_j}

    Induction on mm. To get a whole circuit within ε\varepsilon, approximate each of its mm gates within ε/m\varepsilon/m.

Think first Prove the first fact: if 0≤M≤I0\le M\le\id is a measurement operator, then ∣⟨ψ∣U†MU∣ψ⟩−⟨ψ∣V†MV∣ψ⟩∣≤2∥U−V∥\abs{\bra{\psi}U^\dagger MU\ket{\psi} - \bra{\psi}V^\dagger MV\ket{\psi}}\le 2\norm{U-V}.

Let ∣Δ⟩=(U−V)∣ψ⟩\ket{\Delta} = (U-V)\ket{\psi}, so ∥Δ∥≤∥U−V∥\norm{\Delta}\le\norm{U-V}. Then ⟨ψ∣U†MU∣ψ⟩−⟨ψ∣V†MV∣ψ⟩=⟨ψ∣U†M∣Δ⟩+⟨Δ∣MV∣ψ⟩\bra{\psi}U^\dagger MU\ket{\psi} - \bra{\psi}V^\dagger MV\ket{\psi} = \bra{\psi}U^\dagger M\ket{\Delta} + \bra{\Delta}MV\ket{\psi}. By Cauchy–Schwarz and ∥M∥≤1\norm{M}\le1, each term has modulus at most ∥Δ∥\norm{\Delta}.

Check your understanding

A circuit has 10001000 gates and you want every output probability within 0.010.01 of ideal. What is the largest per-gate error ∥Uj−Vj∥\norm{U_j - V_j} that the two bounds above certify as safe?

  1. 10−210^{-2}
  2. 10−510^{-5}
  3. 5×10−65\times10^{-6}
  4. 10−1110^{-11}
Show the answer

C. 5×10−65\times10^{-6}

The circuit error is at most 1000 εg1000\,\varepsilon_g, and probabilities move by at most twice the circuit error, so we need 2⋅1000 εg≤0.012\cdot1000\,\varepsilon_g\le0.01, i.e. εg≤5×10−6\varepsilon_g\le5\times10^{-6}. Errors add linearly; they do not compound exponentially.

Exact universality: CNOT plus single-qubit gates

First allow infinitely many gates. Theorem (Barenco et al., 1995): CNOT together with all single-qubit unitaries is exactly universal. The proof has two moves, and move one is pure linear algebra.

DerivationEvery unitary is a product of two-level unitaries
  1. A two-level unitary acts non-trivially on only two basis vectors ∣s⟩,∣t⟩\ket{s},\ket{t}: a 2×22\times2 unitary block, and the identity elsewhere.

  2. 1∣a∣2+∣b∣2(aˉbˉb−a)(ab)=(∣a∣2+∣b∣20)\frac{1}{\sqrt{\abs{a}^2+\abs{b}^2}}\begin{pmatrix}\bar a & \bar b\\ b & -a\end{pmatrix}\begin{pmatrix}a\\ b\end{pmatrix} = \begin{pmatrix}\sqrt{\abs{a}^2+\abs{b}^2}\\ 0\end{pmatrix}

    Like a Givens rotation in Gaussian elimination: a two-level unitary on rows 11 and jj zeroes the entry Uj1U_{j1} of the first column.

  3. Ud−1⋯U2U1 U=(100U′)U_{d-1}\cdots U_2U_1\,U = \begin{pmatrix}1 & 0\\ 0 & U'\end{pmatrix}

    After d−1d-1 such steps the first column is (1,0,…,0)T(1,0,\dots,0)^T (it has norm 11 and a positive first entry), and unitarity forces the first row to be (1,0,…,0)(1,0,\dots,0) as well.

  4. #{two-level factors}≤(d−1)+(d−2)+⋯+1=d(d−1)2\#\{\text{two-level factors}\}\le(d-1)+(d-2)+\cdots+1 = \frac{d(d-1)}{2}

    Recurse on the (d−1)(d-1)-dimensional block U′U'. For nn qubits (d=2nd=2^n) that is at most 2n−1(2n−1)2^{n-1}(2^n-1) factors.

Move two is circuitry. A two-level unitary on ∣s⟩,∣t⟩\ket{s},\ket{t} is a multi-controlled single-qubit gate in disguise. Walk a Gray code from ss to tt, flipping one bit per step; for s=000s=000, t=111t=111 use 000→001→011→111000\to001\to011\to111. Multi-controlled NOTs move the amplitude of ∣s⟩\ket{s} along the code until it sits on a string differing from tt in one bit. Apply the 2×22\times2 block there, controlled on all other bits, and walk back.

Multi-controlled gates reduce to CNOTs and single-qubit gates (the ABC and Toffoli constructions), which proves the theorem.

Think first Why can single-qubit gates alone never be universal, no matter how many you allow?

They map product states to product states, so they never create entanglement. One entangling gate repairs this: together with all single-qubit gates, any entangling two-qubit gate is exactly universal (Brylinski & Brylinski, 2002).

Going discrete: H and T

Now make the menu finite. The standard choice is the Hadamard gate HH, the T gate T=diag⁡(1,eiπ/4)T=\diag(1,e^{i\pi/4}), and CNOT. Up to global phase, TT is a π/4\pi/4 turn about zz, and HTHHTH is a π/4\pi/4 turn about xx (because HZH=XHZH=X). Compose the two:

DerivationAn irrational rotation from H and T
  1. T=eiπ/8Rz(π4),HTH=eiπ/8Rx(π4)T = e^{i\pi/8}R_z(\tfrac{\pi}{4}),\qquad HTH = e^{i\pi/8}R_x(\tfrac{\pi}{4})

    With RP(θ)=e−iθP/2=cos⁡θ2 I−isin⁡θ2 PR_P(\theta) = e^{-i\theta P/2} = \cos\tfrac{\theta}{2}\,\id - i\sin\tfrac{\theta}{2}\,P.

  2. Rz(π4) Rx(π4)=(c I−isZ)(c I−isX),c=cos⁡π8, s=sin⁡π8R_z(\tfrac{\pi}{4})\,R_x(\tfrac{\pi}{4}) = (c\,\id - isZ)(c\,\id - isX),\qquad c = \cos\tfrac{\pi}{8},\ s = \sin\tfrac{\pi}{8}

    Multiply out, using ZX=iYZX = iY.

  3. =c2 I−i[ sc (X+Z)+s2 Y ]= c^2\,\id - i\big[\,sc\,(X+Z) + s^2\,Y\,\big]
  4. =cos⁡θ2 I−isin⁡θ2  n^⋅σ⃗,cos⁡θ2=cos⁡2π8,n^∝(cos⁡π8, sin⁡π8, cos⁡π8)= \cos\tfrac{\theta}{2}\,\id - i\sin\tfrac{\theta}{2}\;\hat n\cdot\vec\sigma,\qquad \cos\tfrac{\theta}{2} = \cos^2\tfrac{\pi}{8},\quad \hat n\propto\big(\cos\tfrac{\pi}{8},\ \sin\tfrac{\pi}{8},\ \cos\tfrac{\pi}{8}\big)

    So the circuit H,T,H,TH,T,H,T (operator T⋅HTHT\cdot HTH) is, up to phase, a single rotation Rn^(θ)R_{\hat n}(\theta).

Predict before you look

Compute that rotation angle, θ=2arccos⁡(cos⁡2π8)\theta = 2\arccos\big(\cos^2\tfrac{\pi}{8}\big), in degrees.

Show the answer

63 degrees

cos⁡2π8=2+24≈0.8536\cos^2\tfrac{\pi}{8} = \tfrac{2+\sqrt2}{4}\approx0.8536, so θ/2≈31.4∘\theta/2\approx31.4^\circ and θ≈62.8∘\theta\approx62.8^\circ. Not a nice fraction of 360∘360^\circ, and provably not a rational one.

One axis is not yet everything. But conjugating by HH moves the axis: H Rn^(α) H=Rm^(α)H\,R_{\hat n}(\alpha)\,H = R_{\hat m}(\alpha) with m^∝(cos⁡π8,−sin⁡π8,cos⁡π8)\hat m\propto(\cos\tfrac{\pi}{8},-\sin\tfrac{\pi}{8},\cos\tfrac{\pi}{8}). Rotations about two non-parallel axes generate every rotation with finitely many factors, so HH and TT approximate every single-qubit unitary. Add CNOT and the exact theorem of the previous step: {H,T,CNOT}\{H,T,\mathrm{CNOT}\} is universal. Try it yourself.

Think first Stuck? How short can the sequences be?

A brute-force search finds that nothing with four or fewer gates beats HH alone (93.3%93.3\%). Five gates, H,T,H,T,TH,T,H,T,T, reach 98.3%98.3\%: they land exactly on cos⁡π8∣0⟩+sin⁡π8∣1⟩\cos\tfrac{\pi}{8}\ket0+\sin\tfrac{\pi}{8}\ket1 (the +1+1 eigenstate of HH), 15∘15^\circ from the target. Six gates, H,T,H,T,H,T†H,T,H,T,H,T^\dagger, reach 99.5%99.5\%. More accuracy demands longer sequences; the next step asks how much longer.

The price of approximation

Density guarantees that some sequence works. How long must it be? The pigeonhole argument is wasteful: its sequences grow polynomially in 1/ε1/\varepsilon. Two results pin down the truth.

MethodGates for accuracy ε\varepsilonNotes
Pigeonhole (density)poly⁡(1/ε)\poly(1/\varepsilon)Existence only; hopeless in practice.
Solovay–KitaevO(log⁡3.97(1/ε))\order{\log^{3.97}(1/\varepsilon)}Any finite, inverse-closed, dense set. Recursive and efficient.
Number-theoretic synthesis≈3log⁡2(1/ε)\approx3\log_2(1/\varepsilon) TT gatesClifford+T zz-rotations (Ross–Selinger), exploiting the arithmetic of HH and TT.
Counting lower boundΩ(log⁡(1/ε))\Omega(\log(1/\varepsilon))Matched, up to a constant factor, by number-theoretic synthesis.
gates(m-gate circuit, total error ε)=O(mlog⁡c(m/ε))\text{gates}\big(m\text{-gate circuit, total error }\varepsilon\big) = \order{m\log^c(m/\varepsilon)}
Approximate each gate within ε/m\varepsilon/m and let the errors add. A polylogarithmic factor keeps polynomial-size circuits polynomial-size, so BQP does not depend on the choice of universal gate set (as long as its entries are efficiently computable).

Gate sets you will meet

Not every finite set is universal, and not every universal set is equally useful. Here are the ones you will meet in the literature.

Gate setUniversal?Reason
CNOT + all single-qubit UUExactlyTwo-level decomposition. An infinite set.
HH, TT, CNOT (Clifford+T)YesIrrational rotation. The standard fault-tolerant set.
HH, SS, CNOT (Clifford)NoA finite group up to phases; classically simulable (Gottesman–Knill).
Toffoli + HHFor computationReal matrices only, but it simulates any circuit using one extra qubit to carry real and imaginary parts (Shi 2003; Aharonov 2003).
Toffoli, CNOT, XXNoPermutation matrices: universal only for classical reversible logic.
Almost any single two-qubit gateYesA generic two-qubit unitary, applied to arbitrary pairs of qubits, is universal on its own (Deutsch, Barenco & Ekert 1995; Lloyd 1995).
Check your understanding

Which single addition makes {H,S,CNOT}\{H,S,\mathrm{CNOT}\} universal?

  1. Another Clifford gate, such as CZ
  2. The Pauli gates XX, YY, ZZ
  3. Any single-qubit gate outside the Clifford group, such as TT
  4. Nothing: no finite gate set is universal
Show the answer

C. Any single-qubit gate outside the Clifford group, such as TT

Up to phase, the single-qubit Cliffords form the 24-element rotation group of the octahedron, a maximal finite subgroup of SO(3)SO(3). Adding any non-Clifford rotation therefore generates an infinite group; its closure contains the octahedral group, which forces it to be all of SO(3)SO(3). Single-qubit gates become dense, and CNOT does the rest.

Key takeaways

  • Finite gate sets can only be approximately universal; errors are measured in operator norm and add at most linearly over a circuit.
  • CNOT plus all single-qubit gates is exactly universal (two-level decomposition), yet generic unitaries still need exponentially many gates.
  • HH and TT compose to a rotation by an irrational angle; with CNOT, Clifford+T approximates every unitary.
  • Solovay–Kitaev costs only O(log⁡c(1/ε))\order{\log^c(1/\varepsilon)} gates per approximated gate, so BQP does not depend on the gate set.
  • Cliffords alone are not universal (and are classically simulable); the non-Clifford TT gate is the expensive, essential ingredient.

Check yourself

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

Question 1

Why can no finite gate set implement every single-qubit unitary exactly?

  1. Because HH and TT do not commute
  2. Finitely many gates give countably many circuits, but there are uncountably many unitaries
  3. Because exact implementation would violate the no-cloning theorem
  4. Because real gates are always noisy
Show the answer

B. Finitely many gates give countably many circuits, but there are uncountably many unitaries

Circuits over a finite alphabet are finite words, so there are countably many of them, while {Rz(θ):θ∈[0,2π)}\{R_z(\theta):\theta\in[0,2\pi)\} alone is uncountable. Exact universality needs an infinite gate set; finite sets can only be universal approximately.

Question 2

What makes the product T⋅HTHT\cdot HTH so useful for universality?

  1. It is the identity, so it can be inserted anywhere for free
  2. It is a Clifford gate, so it is cheap
  3. It is a rotation by an irrational multiple of 2π2\pi, so its powers are dense in a circle of rotations
  4. It is a CNOT in disguise
Show the answer

C. It is a rotation by an irrational multiple of 2π2\pi, so its powers are dense in a circle of rotations

T⋅HTH∝Rn^(θ)T\cdot HTH\propto R_{\hat n}(\theta) with cos⁡θ2=cos⁡2π8\cos\frac\theta2 = \cos^2\frac\pi8, and θ/2π\theta/2\pi is irrational. Its powers approximate every rotation about n^\hat n; conjugating by HH gives a second axis, and two axes generate everything.

Question 3

For a fixed universal gate set, how does the Solovay–Kitaev sequence length grow as the target accuracy ε→0\varepsilon\to0?

  1. O(log⁡c(1/ε))\order{\log^c(1/\varepsilon)}, with c≈4c\approx4 in the standard version
  2. O(1/ε)\order{1/\varepsilon}
  3. O(21/ε)\order{2^{1/\varepsilon}}
  4. It does not depend on ε\varepsilon
Show the answer

A. O(log⁡c(1/ε))\order{\log^c(1/\varepsilon)}, with c≈4c\approx4 in the standard version

Polylogarithmically: the basic recursion gives c=log⁡5/log⁡32≈3.97c=\log5/\log\frac32\approx3.97. The counting argument shows that Ω(log⁡(1/ε))\Omega(\log(1/\varepsilon)) gates are unavoidable.

Question 4

Why does the polylogarithmic overhead of Solovay–Kitaev matter for complexity theory?

  1. It shows that quantum computers solve NP-complete problems efficiently
  2. It shows that every unitary has a polynomial-size circuit
  3. It removes the need for error correction
  4. It makes BQP the same for every reasonable universal gate set
Show the answer

D. It makes BQP the same for every reasonable universal gate set

Switching gate sets costs a factor O(log⁡c(m/ε))\order{\log^c(m/\varepsilon)} per gate, so polynomial-size circuits stay polynomial-size. That is why BQP can be defined with any fixed universal set whose entries are efficiently computable.

Go deeper

Further reading

  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §4.5 (Cambridge, 10th anniv. ed., 2010).
  • 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).
  • C. M. Dawson & M. A. Nielsen, "The Solovay–Kitaev algorithm", Quantum Inf. Comput. 6, 81 (2006), arXiv:quant-ph/0505030.
  • P. O. Boykin, T. Mor, M. Pulver, V. Roychowdhury & F. Vatan, "A new universal and fault-tolerant quantum basis" (2000).