nLab Solovay-Kitaev theorem

Contents

Context

Group Theory

Analysis

Computation

Quantum systems

quantum logic


quantum physics


quantum probability theoryobservables and states


quantum information


quantum computation

qbit

quantum algorithms:


quantum sensing


quantum communication

Contents

Idea

Given a finitely generated and dense subgroup g 1,g 1 1,g n,g n 1\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,,g n}\{g_1, \cdots, g_n\} which are needed in order to approximate any given element gSU(2)g \,\in\, SU(2) to given accuracy.

In quantum computation-theory one interprets:

  1. the set {g 0,,g n}\{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 gSU(2)g \,\in\, SU(2) as an intended operation on qbits (an intended quantum program);

  3. the sequence of elements g ig_i used to approximate gg 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 ) SU(d) , d 1d \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 typically far from the usual QBit-basis requiring substantial effort in “topological quantum compilation” (e.g. Bonesteel, Hormozi, Zikos & Simon (2005), Hormozi, Zikos, Bonesteel & Simon (2007), Hormozi, Bonesteel & Simon (2009)).

For example, the following lengthy braid has been proposed [Hormozi, Zikos, Bonesteel & Simon (2007)] as a possible topological quantum compilation of a single CNOT gate:

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:

See also:

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]

  • 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

A textbook account:

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 August 15, 2023 at 20:05:01. See the history of this page for a list of all contributions to it.