# Solovay–Kitaev theorem

The Solovay–Kitaev theorem is a result in quantum computation stating that any unitary operation can be approximated to accuracy \( \epsilon \) by a short sequence of gates drawn from any fixed finite gate set that generates a dense subgroup, with the sequence length growing only as a power of \( \log(1/\epsilon) \). In its standard form for single-qubit gates, if a finite set of elements of \( SU(2) \) contains its own inverses and generates a dense subgroup, then any element of \( SU(2) \) can be approximated to precision \( \epsilon \) with \( O(\log^{c}(1/\epsilon)) \) gates, where \( c \approx 3.97 \) in the standard analysis.<sup>[1](https://arxiv.org/abs/quant-ph/0505030)</sup> The theorem was proved independently by Robert Solovay, in an unpublished manuscript from 1995, and by [Alexei Kitaev](https://www.edgepedia.org/alexei-kitaev), who published it in 1997 in *Russian Mathematical Surveys*.<sup>[2](https://annals.math.princeton.edu/wp-content/uploads/annals-v181-n1-p04-p.pdf)</sup><sup> • </sup><sup>[3](https://www.mathnet.ru/php/archive.phtml?jrnid=rm&option_lang=eng&paperid=892&wshow=paper)</sup>

| Key fact | Detail |
|---|---|
| Statement | A finite gate set in \( SU(2) \), closed under inverses and generating a dense subgroup, approximates any unitary to precision \( \epsilon \) with \( O(\log^{c}(1/\epsilon)) \) gates<sup>[1](https://arxiv.org/abs/quant-ph/0505030)</sup> |
| Standard exponent | \( c \approx 3.97 \) in the common analysis (equal to \( \log 5 / \log(3/2) \)); a variant due to Kitaev and coauthors achieves \( c = 3 + \delta \) for any \( \delta > 0 \)<sup>[4](https://arxiv.org/abs/1212.6253)</sup> |
| Compilation time | The Dawson–Nielsen implementation of the algorithm runs in \( O(\log^{2.71}(1/\epsilon)) \) classical time<sup>[1](https://arxiv.org/abs/quant-ph/0505030)</sup> |
| Lower bound | A counting argument shows the exponent cannot fall below 1; Harrow, Recht, and Chuang achieved \( O(\log(1/\epsilon)) \) length for certain gate sets<sup>[5](https://arxiv.org/abs/quant-ph/0111031)</sup> |
| Recursion depth | \( \Theta(\log\log(1/\epsilon)) \) levels of recursion suffice, with sequence length multiplied by a constant factor at each level<sup>[6](https://theoryofcomputing.org/articles/v008a001/v008a001.pdf)</sup> |
| Generality | Applies to any computationally universal finite gate set, and generalizes to multi-qubit gates and to \( SU(d) \)<sup>[1](https://arxiv.org/abs/quant-ph/0505030)</sup> |
| Later improvements | Kuperberg's methods give \( O(\log^{c}(1/\epsilon)) \) with \( c > 1.44042 \); for the specific Clifford+T set, specialized algorithms reach \( T \)-count \( K + 4\log_{2}(1/\epsilon) \)<sup>[7](https://arxiv.org/abs/2406.04846)</sup><sup> • </sup><sup>[4](https://arxiv.org/abs/1212.6253)</sup> |

## Why the theorem matters

Quantum algorithms are usually written assuming arbitrary single-qubit rotations are available, but practical and fault-tolerant machines implement only a fixed finite set of gates, such as the [Hadamard gate](https://www.edgepedia.org/hadamard-gate), the controlled-NOT, and the \( \pi/8 \) gate \( T \).<sup>[5](https://arxiv.org/abs/quant-ph/0111031)</sup> The theorem closes this gap: it guarantees that a gate set whose generated subgroup is dense in the target group can approximate any gate efficiently, so compilation introduces only a polylogarithmic slowdown in \( 1/\epsilon \). This preserves the complexity class BQP, since a polynomial quantum speedup survives a polylogarithmic overhead.<sup>[8](https://cba.mit.edu/docs/theses/01.05.aram.pdf)</sup>

A concrete use is compiling Shor's factoring algorithm, which uses rotations of \( \pi/2^{k} \), into an efficient fault-tolerant form built only from Hadamard, controlled-NOT, and \( \pi/8 \) gates.<sup>[1](https://arxiv.org/abs/quant-ph/0505030)</sup>

## How the algorithm works

The constructive proof yields a recursive classical algorithm. Given a target unitary \( U \) and a recursion level \( \ell \), it returns a sequence of gates from the set \( S \) whose product approximates \( U \) to error \( \epsilon_{\ell} \), where \( \epsilon_{0} \) is a small fixed constant and each recursion level reduces the error from \( \epsilon \) to \( O(\epsilon^{3/2}) \).<sup>[6](https://theoryofcomputing.org/articles/v008a001/v008a001.pdf)</sup><sup> • </sup><sup>[13](https://www.physics2u.com/vault/solovay-kitaev-theorem.html)</sup>

The base case uses brute force search over short gate strings to find an \( \epsilon_{0} \)-approximation with a constant number of gates. The inductive step rests on a group-commutator fact inspired by Lie theory: if a unitary \( A \) is close to the identity, it can be written approximately as a commutator \( V W V^{\dagger} W^{\dagger} \) of unitaries \( V \) and \( W \) that are generally farther from the identity than \( A \), being typically \( O(\sqrt{\delta}) \) from it when \( A \) is \( \delta \)-close.<sup>[8](https://cba.mit.edu/docs/theses/01.05.aram.pdf)</sup> The algorithm first makes a recursive call to translate \( U \) near the identity, then makes recursive calls to approximate \( V \) and \( W \), and strings together the four sequences for \( V \), \( W \), \( V^{\dagger} \), and \( W^{\dagger} \). Reversing a sequence and inverting each gate produces the inverse sequences, which is where the assumption that the gate set is closed under inverses enters.<sup>[6](https://theoryofcomputing.org/articles/v008a001/v008a001.pdf)</sup>

Because each level multiplies the sequence length by a constant factor (5 in the standard analysis) while the number of levels needed is \( \Theta(\log\log(1/\epsilon)) \), the final sequence length is polylogarithmic in \( 1/\epsilon \).<sup>[6](https://theoryofcomputing.org/articles/v008a001/v008a001.pdf)</sup> The Dawson–Nielsen review gives the concrete bounds of \( O(\log^{2.71}(1/\epsilon)) \) running time and \( O(\log^{3.97}(1/\epsilon)) \) output length.<sup>[1](https://arxiv.org/abs/quant-ph/0505030)</sup>

## Exponents, lower bounds, and improvements

A counting argument fixes what is achievable: a ball of radius \( \epsilon \) in \( SU(d) \) has volume proportional to \( \epsilon^{d^{2}-1} \), so approximating every element to precision \( \epsilon \) requires on the order of \( (1/\epsilon)^{d^{2}-1} \) distinct gate strings, and no algorithm can push the exponent below 1.<sup>[5](https://arxiv.org/abs/quant-ph/0111031)</sup> The Solovay–Kitaev construction, based on successive approximation, was not expected to beat \( c = 2 \) by that method.<sup>[5](https://arxiv.org/abs/quant-ph/0111031)</sup>

Several results narrow the gap from above. A more technical proof in Kitaev's textbook with coauthors reduces the exponent to \( c = 3 + \delta \) for any \( \delta > 0 \).<sup>[4](https://arxiv.org/abs/1212.6253)</sup><sup> • </sup><sup>[6](https://theoryofcomputing.org/articles/v008a001/v008a001.pdf)</sup> A different approach reaches \( O(\log^{2}(1/\epsilon)/\log\log(1/\epsilon)) \), though not for every universal set, and the construction of Harrow, Recht, and Chuang achieves \( O(\log(1/\epsilon)) \), optimal up to constant factors, for certain gate sets but is not constructive and does not apply to every universal set.<sup>[6](https://theoryofcomputing.org/articles/v008a001/v008a001.pdf)</sup> Kuperberg's later work implies that approximating any single-qubit gate to accuracy \( \epsilon \) requires \( O(\log^{c}(1/\epsilon)) \) gates with \( c > 1.44042 \).<sup>[7](https://arxiv.org/abs/2406.04846)</sup> For general [universal gate sets](https://www.edgepedia.org/universal-gate-set), an algorithm with strictly logarithmic running time, linear in the output length, is not known.<sup>[9](https://quantumcomputing.stackexchange.com/questions/44501/synthesis-of-single-qubit-rotation-in-time-o-log1-epsilon/44502)</sup>

## Specialized compilation over Clifford+T

For the single-qubit Clifford+[T gate](https://www.edgepedia.org/t-gate) set \( \{H, S, T\} \), the most common choice for fault-tolerant quantum computation, algebraic and number-theoretic methods have produced provably optimal compiling algorithms that outperform Solovay–Kitaev for the non-Clifford gate-count metric.<sup>[10](https://api.drum.lib.umd.edu/server/api/core/bitstreams/b0af76c2-e426-41f7-b361-071f589325f6/content)</sup> The Ross–Selinger algorithm approximates an arbitrary element of \( SU(2) \) with expected runtime polynomial in \( \log(1/\epsilon) \); for \( z \)-rotations it achieves \( T \)-count \( K + 4\log_{2}(1/\epsilon) \) with \( K \approx 10 \), against a worst-case lower bound of \( K + 4\log_{2}(1/\epsilon) \) with \( K = -9 \), and \( T \)-count \( K + 12\log_{2}(1/\epsilon) \) for general \( SU(2) \) elements. By comparison, the Solovay–Kitaev algorithm achieves \( T \)-count \( O(\log^{3.97}(1/\epsilon)) \).<sup>[4](https://arxiv.org/abs/1212.6253)</sup> These specialized results do not remove the theorem's role: Solovay–Kitaev remains the general method that applies to any computationally universal set.<sup>[5](https://arxiv.org/abs/quant-ph/0111031)</sup>

## Variants and generalizations

**Inverse-free compilation.** The standard proof requires the gate set to be closed under inverses. Slepoy and coauthors constructed the first inverse-free Solovay–Kitaev algorithm, which assumes nothing about the gate set beyond universality and works for both \( SU(d) \) and \( SL(d, \mathbb{C}) \); it builds \( \epsilon^{2} \)-precise approximate inverses from \( \epsilon \)-precise components while keeping the polylogarithmic asymptotics.<sup>[11](https://arxiv.org/abs/2112.02040)</sup> Earlier intermediate results reformulated the algorithm for gate sets containing an exact irreducible representation of a finite group.<sup>[11](https://arxiv.org/abs/2112.02040)</sup>

**Space efficiency.** Van Melkebeek and Watson gave a space-efficient version of the theorem: with matrix entries approximated to precision \( O(\log(1/\epsilon)) \), the algorithm runs in space \( O(\log(1/\epsilon)) \) while keeping polylogarithmic time in a standard finite-precision model of computation.<sup>[6](https://theoryofcomputing.org/articles/v008a001/v008a001.pdf)</sup>

**Higher dimensions.** The theorem and its algorithm generalize from single-qubit gates to multi-qubit gates and to \( SU(d) \) for arbitrary \( d \); the cost of the underlying net construction is exponential in \( d^{2} \), but for any fixed \( d \) this is a constant.<sup>[1](https://arxiv.org/abs/quant-ph/0505030)</sup><sup> • </sup><sup>[8](https://cba.mit.edu/docs/theses/01.05.aram.pdf)</sup> A version of the theorem also holds without the inverse-closed condition, by a different proof.<sup>[12](https://www.cs.umd.edu/~amchilds/qa/qa.pdf)</sup>

## References

1. [Christopher M. Dawson and Michael A. Nielsen (2005). The Solovay-Kitaev algorithm. arXiv:quant-ph/0505030.](https://arxiv.org/abs/quant-ph/0505030)
2. [Annals of Mathematics 181 (2015), 243–301 (source noting Solovay's 1995 description and Kitaev's 1997 publication)](https://annals.math.princeton.edu/wp-content/uploads/annals-v181-n1-p04-p.pdf)
3. [A. Yu. Kitaev (1997). Quantum computations: algorithms and error correction. Russian Mathematical Surveys 52(6), 1191–1249.](https://www.mathnet.ru/php/archive.phtml?jrnid=rm&option_lang=eng&paperid=892&wshow=paper)
4. [Ross and Selinger (2012). Efficient Clifford+T approximation of single-qubit operators. arXiv:1212.6253.](https://arxiv.org/abs/1212.6253)
5. [Aram W. Harrow, Benjamin Recht, Isaac L. Chuang (2002). Efficient Discrete Approximations of Quantum Gates. arXiv:quant-ph/0111031.](https://arxiv.org/abs/quant-ph/0111031)
6. [Dieter van Melkebeek and Thomas Watson (2012). Time-Space Efficient Simulations of Quantum Computations. Theory of Computing 8, 1–51.](https://theoryofcomputing.org/articles/v008a001/v008a001.pdf)
7. [Efficient Fault-Tolerant Single Qubit Gate Approximation And Universal Quantum Computation Without Using The Solovay-Kitaev Theorem. arXiv:2406.04846.](https://arxiv.org/abs/2406.04846)
8. [Aram Harrow. Quantum Compiling thesis, MIT.](https://cba.mit.edu/docs/theses/01.05.aram.pdf)
9. [Quantum Computing Stack Exchange: Synthesis of single-qubit rotation in time O(log(1/ε)).](https://quantumcomputing.stackexchange.com/questions/44501/synthesis-of-single-qubit-rotation-in-time-o-log1-epsilon/44502)
10. [Quantum Compiling dissertation, University of Maryland.](https://api.drum.lib.umd.edu/server/api/core/bitstreams/b0af76c2-e426-41f7-b361-071f589325f6/content)
11. [Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm. arXiv:2112.02040.](https://arxiv.org/abs/2112.02040)
12. [Andrew Childs. Lecture Notes on Quantum Algorithms, University of Maryland.](https://www.cs.umd.edu/~amchilds/qa/qa.pdf)
13. [The Solovay-Kitaev Theorem](https://www.physics2u.com/vault/solovay-kitaev-theorem.html)

---
*Topic: Encyclopedia › Physical world and mathematics › Physics › Quantum physics › Quantum information science › Quantum computing and algorithms › Quantum gates and circuits › Gate decompositions and synthesis*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 11, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license