The Solovay-Kitaev algorithm

By Christopher M. Dawson, Morten Nielsen. Quantum information & computation, 2005

654 citations recorded by the source corpus.

This pedagogical review presents the proof of the Solovay-Kitaev theorem in the form ofan efficient classical algorithm for compiling an arbitrary single-qubit gate into a sequenceof gates from a fixed and finite set. The algorithm can be used, for example, to compileShor's algorithm, which uses rotations of π/2k, into an efficient fault-tolerant form usingonly Hadamard, controlled-not, and π/8 gates. The algorithm runs in O(log2.71(1/e))time, and produces as output a sequence of O(log3.97(1/e)) quantum gates which isguaranteed to approximate the desired quantum gate to an accuracy within e > 0. Wealso explain how the algorithm can be generalized to apply to multi-qubit gates and togates from SU(d).

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/6d24e178f433964ed9f44618bd62c43cfadaa480

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits (2012, methodology): “Dawson and Nielsen [9] provide an algorithm for computing -approximations of single-qubit gates in time O(log(1/ )), along with a generalization to multiqubit cases.”
Quantum error correction: an introductory guide (2019, background): “m any unitary operation Uthat evolves a qubit register from one state to another U|ψi = |ψ′i. It has been shown that any such operation Ucan be eﬃciently compiled from a ﬁnite set of elementary gates [65]. An example of a universal gate set is hUi = hX,Z,Y,H,CNOT,Ti, where T= diag(1,eiπ/4). In this ”
On the spectral gap for finitely-generated subgroups of SU(2) (2007, background): “8.4. In the context of quantum computation (see [ 6 ] and references therein) elements of SU(2) are viewed as “quantum gates” and a set of elements S generating a dense subgroup is called “computationally universal” (since any element of SU(2) “can be approximated by by some word in � S� to an arbit”
Optimal ancilla-free Clifford+V approximation of z-rotations (2015, neutral): “, [1], [3]).”
Error bounds for approximations with deep ReLU networks (2016, background): “…network, a deep one can be viewed as a long sequence of non-commutative transformations, which is a natural setting for high expressiveness (cf. the well-known Solovay-Kitaev theorem on fast approximation of arbitrary quantum operations by sequences of non-commutative gates, see Kitaev et…”
Quantum-assisted quantum compiling (2018, background): “The notion of approximate compiling [32–37] requires an operational figure-of-merit that quantifies how close the compilation is to exact.”
A Spectral Gap Theorem in $SU(d)$ (2011, methodology): “J]. 3It might be worth remarking, that, in the stressed crucial reliance on multi-scale and Lie algebra structures, this approach is reminiscent of the Solovay-Kitaev algorithm in quantum computation [DN]. 2 necessitating the use of non-Archimedian local ﬁelds and exterior powers of the Lie algebra ”
Elucidating reaction mechanisms on quantum computers (2016, methodology): “These methods require near–quartically fewer operations than the Solovay–Kitaev algorithm would need [56] and are useful, if not necessary, for reducing the gate counts of the simulation algorithm to a palatable level.”