Solovay–Kitaev theorem

From Wikipedia, the free encyclopedia
  (Redirected from Solovay-Kitaev theorem)
Jump to navigation Jump to search

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.[1] Solovay also gave a talk on his result at MSRI in 2000 but it was interrupted by a fire alarm.[2] Christopher M. Dawson and Michael Nielsen call the theorem one of the most important fundamental results in the field of quantum computation.[3]

A consequence of this theorem is that a quantum circuit of constant-qubit gates can be approximated to error (in operator norm) by a quantum circuit of gates from a desired finite universal gate set.[4] 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.


Let be a finite set of elements in SU(2) containing its own inverses (so implies ) and such that the group they generate is dense in SU(2). Consider some . Then there is a constant such that for any , there is a sequence of gates from of length such that . That is, approximates to operator norm error.[3]

Quantitative bounds[edit]

The constant can be made to be for any fixed .[5] However, there exist particular gate sets for which we can take , which makes the length of the gate sequence tight up to a constant factor.[6]

Proof idea[edit]

The proof of the Solovay–Kitaev theorem proceeds by recursively constructing a gate sequence giving increasingly good approximations to .[3] Suppose we have an approximation such that . Our goal is to find a sequence of gates approximating to error, for . By concatenating this sequence of gates with , we get a sequence of gates such that .

The key idea is that commutators of elements close to the identity can be approximated "better-than-expected". Specifically, for satisfying and and approximations satisfying and , then

where the big O notation hides higher-order terms. One can naively bound the above expression to be , 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 . This can be done such that both and are close to the identity (since ). So, if we recursively compute gate sequences approximating and to error, we get a gate sequence approximating to the desired better precision with . We can get a base case approximation with constant by brute-force computation of all sufficiently long gate sequences.


  1. ^ Kitaev, A Yu (1997-12-31). "Quantum computations: algorithms and error correction". Russian Mathematical Surveys. 52 (6): 1191–1249. doi:10.1070/rm1997v052n06abeh002155. ISSN 0036-0279.
  2. ^ Solovay, Robert (2000-02-08). Lie Groups and Quantum Circuits. MSRI.
  3. ^ a b c Dawson, Christopher M.; Nielsen, Michael (2006-01-01). "The Solovay-Kitaev algorithm". Quantum Information & Computation. 6: 81–95. arXiv:quant-ph/0505030. doi:10.26421/QIC6.1-6.
  4. ^ Nielsen, Michael A.; Chuang, Isaac L. (2010). The Solovay–Kitaev theorem. Quantum Computation and Quantum Information: 10th Anniversary Edition. pp. 617–624. doi:10.1017/cbo9780511976667.019. ISBN 9780511976667. Retrieved 2020-05-20.
  5. ^ Kitaev, Alexei Yu.; Shen, Alexander; Vyalyi, Mikhail N. (2002). Classical and quantum computation. Providence, Rhode Island: American Mathematical Society. ISBN 0-8218-2161-X. OCLC 48965167.
  6. ^ Harrow, Aram W.; Recht, Benjamin; Chuang, Isaac L. (2002-08-20). "Efficient discrete approximations of quantum gates". Journal of Mathematical Physics. 43 (9): 4445–4451. arXiv:quant-ph/0111031. doi:10.1063/1.1495899. ISSN 0022-2488. S2CID 119043335.