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 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 -qubit unitary needs about 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 , 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 needs only 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 ; 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 T gates, essentially optimal. Established
Most unitaries are hard
Counting settles the many-qubit case. Words of length from a finite gate set number at most ; covering the space of -qubit unitaries, of dimension , with balls of radius needs about of them. So almost every unitary needs a circuit exponentially long in . 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.
And one to work out. For single-qubit rotations, the counting bound is about gates. How many for ?
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.