# nLab Solovay-Kitaev theorem

Contents

group theory

### Cohomology and Extensions

#### Computation

intuitionistic mathematics

# Contents

## Idea

Given a finitely generated and dense subgroup $\langle g_1, g_1^{-1} \cdots, g_n, g_n^{-1} \rangle$ of the topological group SU(2), the Solovay-Kitaev theorem [Kitaev (1997), Nielsen & Chuang (2000, §A3)] gives a strong bound on the length of sequences of elements from $\{g_1, \cdots, g_n\}$ which are needed in order to approximate any given element $g \,\in\, SU(2)$ to given accuracy.

In quantum computation-theory one interprets:

1. the set $\{g_0, \cdots, g_n\}$ as a given set of (operations of) quantum gates on qbits

(that the subgroup these generate is dense in SU(2) is said to mean that this is a universal set of quantum gates);

2. the target element $g \,\in\, SU(2)$ as an intended operation on qbits (an intended quantum program);

3. the sequence of elements $g_i$ used to approximate $g$ as a quantum circuit realizing the quantum program (“quantum compilation”),

and then the Solovay-Kitaev theorem guarantees that the maximum depth of the quantum circuit grows only slowly with its required accuracy.

In fact, the theorem holds in the generality of $SU(d)$, $d \in \mathbb{N}_{\geq 1}$, which in terms of quantum computation corresponds to working with qdits instead of just qbits.

Regarding the practical relevance, it has been argued [MO:a/22197] that quantum computing-hardware such as based on superconductors will already allow to approximate any operation on a “physical qbit” by a single quantum gate, but that for such hardware the Solovay-Kitaev theorem is still relevant on the level of “logical qbits”, i.e. taking quantum error correction into account.

Similarly, in topological quantum computation the available set of basic anyon braid gates is highly constrained and the Solovay-Kitaev algorithm is used for “topological quantum compilation” (e.g. Bonesteel, Hormozi, Zikos & Simon (2005), Hormozi, Zikos, Bonesteel & Simon (2007), Hormozi, Bonesteel & Simon (2009))

## References

### General

According to Dawson & Nielsen (2006, p. 13) the first announcement of the theorem was

• “by Solovay in 1995 on an email discussion list”.

A proof was then outlined in:

followed by talk announcement:

Following Kitaev (1997), a full proof was spelled out in:

Review:

Further refinement of the algorithm:

• Attila B. Nagy, On an implementation of the Solovay-Kitaev algorithm, 10th Rhine Workshop on Computer Algebra [arXiv:quant-ph/0606077]

### Quantum circuit compilation

More on quantum circuit compilation:

• Neil J. Ross, Chapters 6-7 in: Algebraic and Logical Methods in Quantum Computation, Ph.D. thesis, Dalhousie University (2015) [arXiv:1510.02198]

• Adi Botea, Akihiro Kishimoto, Radu Marinescu, On the Complexity of Quantum Circuit Compilation, Proceedings of the International Symposium on Combinatorial Search, 9 1 (2018) [doi:10.1609/socs.v9i1.18463]

• Robert Wille; Stefan Hillmich; Lukas Burgholzer, Efficient and Correct Compilation of Quantum Circuits, in 2020 IEEE International Symposium on Circuits and Systems (ISCAS) IEEE Explore (2020) [doi:10.1109/ISCAS45731.2020.9180791]

• Marco Maronese, Lorenzo Moro, Lorenzo Rocutto, Enrico Prati, Quantum Compiling, in Quantum Computing Environments, Springer (2021) [arXiv:2112.00187, doi:10.1007/978-3-030-89746-8_2]

• Nathanial Stemen, Quantum Circuit Compilation from the Ground Up (2022) [pdf]

• Giulia Meuli, Fereshte Mozafari, Bruno Schmitt, Heinz Riener, Mathias Soeken, Giovanni De Micheli: Quantum Compilation

Quantum compilation with a proof assistant based on QWIRE:

### Topological quantum compilation

Discussion of the Solovay-Kitaev theorem for quantum compilation in the context of topological quantum computation:

Last revised on February 27, 2023 at 07:12:42. See the history of this page for a list of all contributions to it.