Solovay–Kitaev theorem
In quantum information and computation, the Solovay–Kitaev theorem says, roughly, that if a set of single-qubit quantum gates generates a dense subset of SU(2) then that set is guaranteed to fill SU(2) quickly, which means any desired gate can be approximated by a fairly short sequence of gates from the generating set. Robert M. Solovay initially announced the result on an email list in 1995, and Alexei Kitaev independently gave an outline of its proof in 1997. Solovay also gave a talk on his result at MSRI in 2000 but it was interrupted by a  fire alarm. Christopher M. Dawson and Michael Nielsen call the theorem one of the most important fundamental results in the field of quantum computation. A consequence of this theorem is that a quantum circuit of formula_1 constant-qubit gates can be approximated to formula_2 error (in operator norm) by a quantum circuit of formula_3 gates from a desired finite universal gate set. By comparison, just knowing that a gate set is universal only implies that constant-qubit gates can be approximated by a finite circuit from the gate set, with no bound on its length. So, the Solovay–Kitaev theorem  shows that this approximation can be made surprisingly "efficient", thereby justifying that quantum computers need only implement a finite number of gates to gain the full power of quantum computation. Statement. Let formula_4 be a finite set of elements in SU(2) containing its own inverses (so formula_5 implies formula_6) and such that the group formula_7 they generate is dense in SU(2). Consider some formula_8. Then there is a constant formula_9 such that for any formula_10, there is a sequence formula_11 of gates from formula_4 of length formula_13 such that formula_14. That is, formula_11 approximates formula_16 to operator norm error. Quantitative  bounds. The constant formula_9 can be made to be formula_18 for any fixed formula_19. However, there exist particular gate sets for which we can take formula_20, which makes the length of the gate sequence tight up to a constant factor. Proof idea. The proof of the Solovay–Kitaev theorem proceeds by recursively constructing a gate sequence giving increasingly good approximations to formula_21. Suppose we have an approximation formula_22 such that formula_23. Our goal is to find a sequence of gates approximating formula_24 to formula_25 error, for formula_26. By concatenating this sequence of gates with formula_27, we get a sequence of  gates formula_28 such that formula_29. The key idea is that commutators of elements close to the identity can be approximated "better-than-expected". Specifically, for formula_30 satisfying formula_31 and formula_32 and approximations formula_33 satisfying formula_34 and formula_35, then where the big O notation hides higher-order terms. One can naively bound the above expression to be formula_37, but the group commutator structure creates substantial error cancellation. We use this observation by rewriting the expression we wish to approximate as a group commutator formula_38. This can be done such that both formula_39 and formula_40 are close to the identity (since formula_41 ). So, if we recursively compute gate sequences approximating formula_39 and formula_40 to formula_44 error, we get a gate sequence approximating formula_24 to the desired better precision formula_25 with formula_25. We can get a base case approximation with constant formula_48 by brute-force computation of all sufficiently long gate sequences.