Solovay–Kitaev theorem

Remarks

Proof idea: density and compactness give a finite word length $\ell_0$ whose words form an $\varepsilon_0$-net of $SU(d)$. To improve an approximation $V$ of $U$, write $U V^{-1}$, which is close to the identity, as a group commutator $A B A^{-1} B^{-1}$ of elements close to the identity. Approximate $A$ and $B$ recursively; the error of the commutator is much smaller than the errors of $A$ and $B$. Each level multiplies the length by $5$ and turns an error $\varepsilon$ into about $\varepsilon^{3/2}$, which gives $c = \log 5 / \log(3/2) \approx 3.97$. The proof is constructive and gives an algorithm that finds the sequence in time polylogarithmic in $1/\varepsilon$.

Example: in quantum computing, $\set{H, T}$ with the Hadamard gate $H$ and $T = \operatorname{diag}(1, e^{i\pi/4})$ generates a dense subgroup of $SU(2)$ modulo phases. So every one-qubit gate can be approximated to accuracy $\varepsilon$ by $O(\log^c(1/\varepsilon))$ gates $H$, $T$ and $T^{-1}$.

Density alone gives some approximating word; the content of the theorem is the polylogarithmic bound on its length. The standard proof uses the inverses in hypothesis 1 to form commutators.

Going deeper

For a student

The theorem is a statement about compact Lie groups, used as a compilation tool. A circuit of $m$ arbitrary gates, compiled to total accuracy $\varepsilon$, needs $O(m \log^c(m/\varepsilon))$ gates from a universal set. This makes the class BQP independent of the choice of a universal gate set. Counting arguments show that length at least of order $\log(1/\varepsilon)$ is needed, so the exponent $c$ cannot go below $1$.