100
Part Three · A · Foundations of quantum information

Circuits, universality, and the Solovay–Kitaev theorem

A real quantum computer offers a handful of gates, not every unitary matrix. Yet any operation on any number of qubits can be approximated, to any accuracy, by stringing those few gates together. That a finite gate set is enough is not obvious, and how many gates you need is a subtle question. The answer for single qubits is “surprisingly few”, the Solovay–Kitaev theorem; the answer for most operations on many qubits is “exponentially many”, and that is no contradiction.

On the plate: strings of H and T gates hunting for a target rotation.

Breaking a big unitary into small ones

Any unitary on nn qubits can be written as a product of two-level unitaries, each acting nontrivially on only two basis states, by eliminating off-diagonal entries one at a time like Gaussian elimination. Each two-level unitary becomes single-qubit gates plus CNOTs. So {single-qubit gates, CNOT} is exactly universal. The catch: an arbitrary nn-qubit unitary needs about 4n4^n such gates. Established

A finite set: H, T and CNOT

Single-qubit gates form a continuum, but H and T alone generate rotations by an angle that is an irrational multiple of π\pi, so products of them come arbitrarily close to any single-qubit rotation. Pick a target, a z-rotation by 0.3 radians. The plate searches every H/T word up to length 16 and plots the best error found so far. Brute force improves slowly: lengths are cheap, but the number of words grows exponentially.

Solovay–Kitaev

Robert Solovay and Alexei Kitaev showed in the late 1990s that, for any universal gate set closed under inverses, an approximation to accuracy ε\varepsilon needs only O(log⁡c(1/ε))O(\log^c(1/\varepsilon)) gates, found efficiently by recursion: approximate coarsely, then fix the error using group commutators of coarser approximations, whose error shrinks faster than their length grows. Christopher Dawson and Michael Nielsen’s version has c≈3.97c \approx 3.97; in 2023 Greg Kuperberg lowered the exponent to about 1.44. For the specific set {H, T}, Neil Ross and Peter Selinger’s number-theoretic “gridsynth” finds z-rotations with about 3log⁡2(1/ε)3\log_2(1/\varepsilon) T gates, essentially optimal. Established

Most unitaries are hard

Counting settles the many-qubit case. Words of length LL from a finite gate set number at most gLg^L; covering the space of nn-qubit unitaries, of dimension 4n4^n, with balls of radius ε\varepsilon needs about (1/ε)4n(1/\varepsilon)^{4^n} of them. So almost every unitary needs a circuit exponentially long in nn. Efficient quantum algorithms are the rare exceptions with special structure. This is why a quantum computer is not a machine that does everything fast.

What you now have

Two-level decomposition and exact universality, {H, T, CNOT} as an approximately universal set, the Solovay–Kitaev theorem and modern synthesis, and the counting argument that most unitaries need exponentially many gates.

· · ·

Three questions to carry with you.

Why can H and T approximate any rotation?tap
They generate a rotation by an irrational multiple of π, whose powers fill the circle densely, and combinations cover all axes.
What does Solovay–Kitaev guarantee?tap
Accuracy ε with polylogarithmic length O(log^c(1/ε)), found efficiently.
Why are most n-qubit unitaries hard?tap
There are far more ε-distinguishable unitaries than short circuits.

And one to work out. For single-qubit rotations, the counting bound is about 3log⁡2(1/ε)3\log_2(1/\varepsilon) gates. How many for ε=10−3\varepsilon = 10^{-3}?

L ≈

Sources: A. Yu. Kitaev, Russ. Math. Surv. 52, 1191 (1997). C. M. Dawson and M. A. Nielsen, Quantum Inf. Comput. 6, 81 (2006). G. Kuperberg, arXiv:2306.13158 (2023, v2 2025). N. J. Ross and P. Selinger, Quantum Inf. Comput. 16, 901 (2016). A. Barenco et al., Phys. Rev. A 52, 3457 (1995). Checked by code: brute-force best error for R_z(0.3) falls from 0.171 to 0.050 by length 19; 3 log₂(10³) = 29.9.

Next · Chapter 101
Measurement: projective, POVM, weak

You can tell two non-orthogonal states apart perfectly, some of the time, if you're allowed to answer "I don't know."

Turn the page