The Solovay-Kitaev algorithm
read the original 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)$.
This paper has not been read by Pith yet.
Forward citations
Cited by 12 Pith papers
-
Efficient Simulation of High-Level Quantum Gates
A gadget-based simulator directly simulates high-level quantum gates via low-rank stabilizer decompositions of magic states, improving both theoretical complexity and practical runtime over standard compilation-based methods.
-
Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
Any n-qubit unitary can be implemented approximately with Õ(2^{n/2}) oracle queries or exactly with Õ(2^{n/2}) circuit depth via Grover search reductions, with matching lower bounds for certain implementations.
-
Sub-Cubic Quantum Gate Synthesis via Stochastic Commutator Decomposition
Stochastic Commutator Synthesis integrates sub-cubic Solovay-Kitaev with Gibbs-sampled commutator selection and randomized compilation to cut T-counts by 10-25% and raise fidelity by up to 35% on Forrelation circuits.
-
From Characterization To Construction: Generative Quantum Circuit Synthesis from Gate Set Tomography Data
A generative QMLC framework tokenizes GST data, embeds it via curriculum-trained set-vision transformers into a context-aware latent space, and uses diffusion models to synthesize circuits conditioned on desired measu...
-
Universality of Quantum Gates in Particle and Symmetry Constrained Subspaces
Hardware-efficient gates are universal for state preparation in particle-number and symmetry-constrained subspaces because commutators generate Pauli Z projectors that span the full so(w) and su(w) algebras.
-
An Oracle-Free Quantum Algorithm for Nonadiabatic Quantum Molecular Dynamics
An oracle-free Trotter-based quantum algorithm for nonadiabatic molecular dynamics achieves circuit depth advantages over QROM architectures and retains T-gate scalability compared to quantum signal processing.
-
O3LS: Optimizing Lattice Surgery via Automatic Layout Searching and Loose Scheduling
O3LS reduces space overhead by up to 46.7% and time overhead by up to 36% in lattice surgery while suppressing logical error rates by up to an order of magnitude compared with prior layout and scheduling approaches.
-
Quantum Coherence and Anomalous Work Extraction in Qubit Gate Dynamics
Coherence enables anomalous work extraction in qubit gate dynamics via negative Kirkwood-Dirac quasiprobabilities, with a compositional relation connecting circuit-level work statistics to individual gates.
-
Quantum Circuit Overhead
Introduces QCO and T-QCO measures and numerically shows that the T gate is non-optimal for completing the Clifford set among order-8 gates.
-
Lower overhead fault-tolerant building blocks for noisy quantum computers
New combinatorial proofs and circuit designs for quantum error correction reduce physical qubit overhead by up to 10x and time overhead by 2-6x for codes including Steane, Golay, and surface codes.
-
A Timelike Quantum Focusing Conjecture
A timelike quantum focusing conjecture implies a complexity-based quantum strong energy condition and a complexity bound analogous to the covariant entropy bound for suitable codimension-0 field theory complexity measures.
-
Benchmarking and Resource Analysis for Augmented-Lagrangian Quantum Hamiltonian Descent
AL-QHD benchmarks on nonconvex test functions and ACOPF power problems show useful accuracy at fixed qubit cost but require roughly 10^8 T gates for realistic instances.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.