The Solovay-Kitaev algorithm

2005/05/06 by Christopher M. Dawson, Dawson, Christopher M., Michael A. Nielsen +1 · 72 citations
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0505030

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

openalex publication_date 2005/05/06 · arxiv created 2005/08/23 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 π/ 2^k, into an efficient fault-tolerant form using only Hadamard, controlled-\sc not, and π/ 8 gates. The algorithm runs in O(log^2.71(1/ε)) time, and produces as output a sequence of O(log^3.97(1/ε)) quantum gates which is guaranteed to approximate the desired quantum gate to an accuracy within ε> 0. We also explain how the algorithm can be generalized to apply to multi-qubit gates and to gates from SU(d).

Cited by

• Local Universality and Structural Certificates for Minimal Fixed-Depth Two-Qutrit Gate Decomposition
• Compiling Quantum Regular Language States
• DeComp2: Description Complexity aware Decomposition
• Aligning Quantum Operators with Large Language Models
• Fault-tolerant execution of error-corrected quantum algorithms
• Universal Blind Quantum Computation with Recursive Rotation Gates
• A nonlinear quantum neural network framework for entanglement engineering
• F2: Offline Reinforcement Learning for Hamiltonian Simulation via Free-Fermionic Subroutine Compilation
• Matchgate synthesis via Clifford matchgates and T gates
• Phase Estimation with Compressed Controlled Time Evolution
• Performance Guarantees for Quantum Neural Estimation of Entropies
• Approximation rates of quantum neural networks for periodic functions via Jackson's inequality
• Topological quantum compilation for non-semisimple Ising anyons via monte carlo simulations
• Fidelity sweet spot in transmon qubit rings under strong connectivity noise
• Quantum Circuit Pre-Synthesis: Learning Local Edits to Reduce T-count
• On universality of hardware-efficient ansatzes
• Space-Time Tradeoffs of Pauli-Based Computation in Distributed qLDPC Architectures
• Exact Quantum Circuit Optimization is co-NQP-hard
• CNOT Minimal Circuit Synthesis: A Reinforcement Learning Approach
• On Encoding Matrices using Quantum Circuits
• Asymptotic Gate Count Bounds for Ancilla-Free Single-Qubit Synthesis with Arithmetic Gates
• Optimal ancilla-free Clifford+T synthesis for general single-qubit unitaries
• Characterization of permutation gates in the third level of the Clifford hierarchy
• Provably Optimal Quantum Circuits with Mixed-Integer Programming
• Unitary synthesis with fewer T gates
• Photonic Simulation of Beyond-Quantum Nonlocal Correlations (e.g. Popescu-Rohrlich Box) with Non-Signaling Quantum Resources
• Complexity of Einstein-Maxwell-non-minimal coupling R²F²: the role of the penalty factor
• Two bases suffice for QMA1-completeness
• Low-Overhead and High-Fidelity Preparation of Logical Non-Clifford States with Multi-Level Transversal Injection
• Optimizing the non-Clifford-count in unitary synthesis using Reinforcement Learning
• Nontrivial multi-product commutation relation for reducing T-count in sequential Pauli-based computation
• Entanglement Detection with Quantum-inspired Kernels and SVMs
• TITAN: A Trajectory-Informed Technique for Adaptive Parameter Freezing in Large-Scale VQE
• Qompiler: A Traceable Quantum Circuit Synthesizer for Arbitrary Hamiltonians
• Hybrid Quantum Neural Networks for Efficient Protein-Ligand Binding Affinity Prediction
• Quantum Coherence and Anomalous Work Extraction in Qubit Gate Dynamics
• FeynmanDD: Quantum Circuit Analysis with Classical Decision Diagrams
• On the Complexity of Quantum States and Circuits from the Orthogonal and Symplectic Groups
• Unitary Synthesis with AlphaZero via Dynamic Circuits
• Compilation-informed probabilistic logical-error cancellation
• Quantum computing on encrypted data with arbitrary rotation gates
• Resource-Efficient Synthesis of Sparse Quantum States
• Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy
• Q-Sylvan: A Parallel Decision Diagram Package for Quantum Computing
• Reducing Quantum Circuit Synthesis to #SAT
• A small and interesting architecture for early fault-tolerant quantum computers
• Exponentially robust non-Clifford gate in a driven-dissipative circuit
• Grover's algorithm is an approximation of imaginary-time evolution
• Local limit theorems for random isometries of the plane
• Design Automation in Quantum Error Correction
• Optimized Qubit Routing for Commuting Gates via Integer Programming
• Efficient Simulation of High-Level Quantum Gates
• Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms
• Quantum Framework for Simulating Linear PDEs with Robin Boundary Conditions
• Architectural mechanisms of a universal fault-tolerant quantum computer
• Quantum Catalytic Space
• Transversal Gates for Highly Asymmetric qLDPC Codes
• A Solovay-Kitaev theorem for quantum signal processing
• Quantum circuits as a game: A reinforcement learning agent for quantum compilation and its application to reconfigurable neutral atom arrays
• Synthesis of discrete-continuous quantum circuits with multimodal diffusion models
• Symbolic Hamiltonian Compiler for Hybrid Qubit-Boson Processors
• Benincasa-Dowker causal set actions by quantum counting
• Fast correlated decoding of transversal logical algorithms
• Quantum Circuit Overhead
• Trading inverses for an irrep in the Solovay-Kitaev theorem
• Cultivating logical catalysts for fault-tolerant dyadic phase rotations
• Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics
• Quantum Homomorphic Encryption: Towards Practical and Private Computation on Untrusted Quantum Hardware
• O3LS: Optimizing Lattice Surgery via Automatic Layout Searching and Loose Scheduling
• Quantum phase classification via quantum hypothesis testing
• Quantum error correction via multi-particle discrete-time quantum walk
• Kernpiler: Compiler Optimization for Quantum Hamiltonian Simulation with Partial Trotterization

Related

• Efficient Fault-Tolerant Single Qubit Gate Approximation And Universal Quantum Computation Without Using The Solovay-Kitaev Theorem
• Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm
• A Solovay-Kitaev theorem for quantum signal processing
• A Note on a Quantitative Form of the Solovay-Kitaev Theorem
• On the Role of Hadamard Gates in Quantum Circuits