The Solovay-Kitaev algorithm

Abstract

This pedagogical review presents the proof of the Solovay-Kitaev theorem in the form of an efficient classical algorithm for compiling an arbitrary single-qubit gate into a sequence of gates from a fixed and finite set. The algorithm can be used, for example, to compile Shor's algorithm, which uses rotations of $\pi /2^k$, into an efficient fault-tolerant form using only Hadamard, controlled-{\sc not}, and $\pi /8$ gates. The algorithm runs in $O({\log }^{2.71}(1/\epsilon ))$ time, and produces as output a sequence of $O({\log }^{3.97}(1/\epsilon ))$ quantum gates which is guaranteed to approximate the desired quantum gate to an accuracy within $\epsilon >0$. We also explain how the algorithm can be generalized to apply to multi-qubit gates and to gates from $SU(d)$.

15 pages, accepted to Quantum Information and Computation as Review Article

Cited by in corpus (6)

• Double-bracket quantum algorithms for diagonalization
• Quantum Fully Homomorphic Encryption by Integrating Pauli One-time Pad with Quaternions
• Polynomial Equivalence of Complexity Geometries
• Ladder Operator Block-Encoding
• Double-bracket algorithm for quantum signal processing without post-selection
• Policy Gradient Approach to Compilation of Variational Quantum Circuits