Solovay–Kitaev theorem

In quantum information and computation, the Solovay–Kitaev theorem says that if a set of single-qubit quantum gates generates a dense subgroup of SU(2), then that set can be used to approximate any desired quantum gate with a short sequence of gates that can also be found efficiently. This theorem is considered one of the most significant results in the field of quantum computation and was first announced by Robert M. Solovay in 1995 and independently proven by Alexei Kitaev in 1997.^[1][2] Michael Nielsen and Christopher M. Dawson have noted its importance in the field.^[3]

A consequence of this theorem is that a quantum circuit of ${\displaystyle m}$ constant-qubit gates can be approximated to ${\displaystyle \varepsilon }$ error (in operator norm) by a quantum circuit of ${\displaystyle O(m\log ^{c}(m/\varepsilon ))}$ 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.

Statement

Let ${\displaystyle {\mathcal {G}}}$  be a finite set of elements in SU(2) containing its own inverses (so ${\displaystyle g\in {\mathcal {G}}}$  implies ${\displaystyle g^{-1}\in {\mathcal {G}}}$ ) and such that the group ${\displaystyle \langle {\mathcal {G}}\rangle }$  they generate is dense in SU(2). Consider some ${\displaystyle \varepsilon >0}$ . Then there is a constant ${\displaystyle c}$  such that for any ${\displaystyle U\in \mathrm {SU} (2)}$ , there is a sequence ${\displaystyle S}$  of gates from ${\displaystyle {\mathcal {G}}}$  of length ${\displaystyle O(\log ^{c}(1/\varepsilon ))}$  such that ${\displaystyle \|S-U\|\leq \varepsilon }$ . That is, ${\displaystyle S}$  approximates ${\displaystyle U}$  to operator norm error.^[3] Furthermore, there is an efficient algorithm to find such a sequence. More generally, the theorem also holds in SU(d) for any fixed d.

This theorem also holds without the assumption that ${\displaystyle {\mathcal {G}}}$  contains its own inverses, although presently with a larger value of ${\displaystyle c}$  that also increases with the dimension ${\displaystyle d}$ .^[5]

Quantitative bounds

The constant ${\displaystyle c}$  can be made to be ${\displaystyle \log _{(1+{\sqrt {5}})/2}2+\delta =1.44042\ldots +\delta }$  for any fixed ${\displaystyle \delta >0}$ .^[6] However, there exist particular gate sets for which we can take ${\displaystyle c=1}$ , which makes the length of the gate sequence optimal up to a constant factor.^[7]

Proof idea

Every known proof of the fully general Solovay–Kitaev theorem proceeds by recursively constructing a gate sequence giving increasingly good approximations to ${\displaystyle U\in \operatorname {SU} (2)}$ .^[3] Suppose we have an approximation ${\displaystyle U_{n-1}\in \operatorname {SU} (2)}$  such that ${\displaystyle \|U-U_{n-1}\|\leq \varepsilon _{n-1}}$ . Our goal is to find a sequence of gates approximating ${\displaystyle UU_{n-1}^{-1}}$  to ${\displaystyle \varepsilon _{n}}$  error, for ${\displaystyle \varepsilon _{n}<\varepsilon _{n-1}}$ . By concatenating this sequence of gates with ${\displaystyle U_{n-1}}$ , we get a sequence of gates ${\displaystyle U_{n}}$  such that ${\displaystyle \|U-U_{n}\|\leq \varepsilon _{n}}$ .

The main idea in the original argument of Solovay and Kitaev is that commutators of elements close to the identity can be approximated "better-than-expected". Specifically, for ${\displaystyle V,W\in \operatorname {SU} (2)}$  satisfying ${\displaystyle \|V-I\|\leq \delta _{1}}$  and ${\displaystyle \|W-I\|\leq \delta _{1}}$  and approximations ${\displaystyle {\tilde {V}},{\tilde {W}}\in \operatorname {SU} (2)}$  satisfying ${\displaystyle \|V-{\tilde {V}}\|\leq \delta _{2}}$  and ${\displaystyle \|W-{\tilde {W}}\|\leq \delta _{2}}$ , then

${\displaystyle \|VWV^{-1}W^{-1}-{\tilde {V}}{\tilde {W}}{\tilde {V}}^{-1}{\tilde {W}}^{-1}\|\leq O(\delta _{1}\delta _{2}),}$ 

where the big O notation hides higher-order terms. One can naively bound the above expression to be ${\displaystyle O(\delta _{2})}$ , but the group commutator structure creates substantial error cancellation.

We can use this observation to approximate ${\displaystyle UU_{n-1}^{-1}}$  as a group commutator ${\displaystyle V_{n-1}W_{n-1}V_{n-1}^{-1}W_{n-1}^{-1}}$ . This can be done such that both ${\displaystyle V_{n-1}}$  and ${\displaystyle W_{n-1}}$  are close to the identity (since ${\displaystyle \|UU_{n-1}^{-1}-I\|\leq \varepsilon _{n-1}}$ ). So, if we recursively compute gate sequences approximating ${\displaystyle V_{n-1}}$  and ${\displaystyle W_{n-1}}$  to ${\displaystyle \varepsilon _{n-1}}$  error, we get a gate sequence approximating ${\displaystyle UU_{n-1}^{-1}}$  to the desired better precision ${\displaystyle \varepsilon _{n}}$  with ${\displaystyle \varepsilon _{n}}$ . We can get a base case approximation with constant ${\displaystyle \varepsilon _{0}}$  with an exhaustive search of bounded-length gate sequences.

References

1. Kitaev, A Yu (1997-12-31). "Quantum computations: algorithms and error correction". Russian Mathematical Surveys. 52 (6): 1191–1249. Bibcode:1997RuMaS..52.1191K. doi:10.1070/rm1997v052n06abeh002155. ISSN 0036-0279. S2CID 250816585.
2. 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.
3. 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. Bouland, Adam; Giurgica-Tiron, Tudor (2021-12-03), Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm, arXiv:2112.02040
6. Kuperberg, Greg (2023-06-22), "Breaking the cubic barrier in the Solovay-Kitaev algorithm", arXiv:2306.13158 [quant-ph]
7. Ross, Neil J.; Selinger, Peter. "Optimal ancilla-free Clifford+T approximation of z-rotations". Quantum Information & Computation. 16 (11–12): 901–953. arXiv:1403.2975. doi:10.26421/QIC16.11-12-1.