REVIEW 29 cited by
The Solovay-Kitaev algorithm
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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)$.
Forward citations
Cited by 29 Pith papers
-
PhD thesis: Modes, States, and Symmetries in quantum Optics for quantum Information and Metrology
Modal structure, photon statistics, and bosonic/phase symmetries jointly determine the usable resources for photonic quantum information and metrology, with explicit gains and limits for time-frequency, HOM, and SSR settings.
-
Suppressing errors in analog logical rotation gates via balanced fusion
Balanced fusion RUS implements small logical rotations with error O(pφ^1.5) instead of O(pφ), by fusing resource states in a balanced tree rather than directly preparing ever-larger angles.
-
Removing Online Exponential Net Search from Solovay-Kitaev
Replacing the depth-zero net search with an 'integerized trotterization' over a good exponential basis makes online synthesis poly(d, log 1/ε), moving the exponential net cost into a one-time preprocessing step.
-
Universality of Magic in Local Quantum Field Theory
In any local QFT, vacuum-like states have non-flat entanglement spectra because local algebras are type III₁, so no stabilizer state can flow to them in the continuum: QFT states necessarily carry magic.
-
Magic Gate Teleportation: Structure, Useful Resource States, and Simpler Feedforward
MGT protocols encode the input into a measurement-heralded stabilizer code then apply a logical non-Clifford gate; useful resource states are Clifford-equivalent to diagonal states, and feedforward can often be Pauli.
-
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.
-
Complementary 3D color codes for transversal quantum logic
Complementary tetrahedral and H-tetrahedral 3D color codes supply transversal magic and most entanglement; a pieceable round-robin CZ with 2D Steane extraction completes a universal FT gate set.
-
Explicit Matrices over $\mathbb Z_2$ with CNOT and Row Complexity $4n-\mathrm{o}(n)$ and Local Logic Gates
Explicit n imes n matrices over Z_2 require 4n−o(n) CNOT/row/2-local linear gates, and the same bound holds for the quantum complexity of the associated affine permutations.
-
Geometric Algebra Quantum Gate Decomposition
Reformulates Pauli and Clifford groups in geometric algebra with a greedy rotor decomposition algorithm for Clifford operators and geometric view of Clifford+T universality.
-
Graphical and algebraic methods for Boolean factoring
Biclique-covering and Horner-based algorithms for Boolean polynomial factoring achieve up to 5x AND-count reduction versus EXORCISM-4 on random functions up to 12 variables.
-
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.
-
No-Go Theorem on Fault Tolerant Gadgets for Multiple Logical Qubits
No stabilizer code can implement the full logical Clifford group on multiple logical qubits using transversal gates, fold-transversal gates beyond two qubits, or code automorphisms.
-
Nontrivial multi-product commutation relation toward reducing T-count in sequential Pauli-based computation
A group of four non-commuting pi/4 Pauli rotations can be reordered as blocks whenever their axes satisfy a simple algebraic condition, and this rule defeats current T-count optimizers on specially built circuits.
-
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.
-
Optimising Trotter-Suzuki Simulations of Markovian Open Quantum Systems via Classical Search
Binary search on diamond-norm error functions yields far fewer Trotter steps than closed-form analytic bounds for deterministic and randomised TS product formulas on Markovian open systems, with second-order randomise...
-
DeComp2: Description Complexity aware Decomposition
Adding a description-length term to the quantum-compiler objective changes the chosen circuit on ~0.3% of tested single-qubit targets, showing gate-count-only compilation discards genuinely structured alternatives.
-
Geometric Algebra Quantum Gate Decomposition
Pauli and Clifford groups are formulated in complex Geometric Algebra, with Clifford operators generated by π/4-Pauli rotors and a greedy rotor algorithm yielding compact decompositions.
-
Lie Algebra-Based Quantum Optimal Controls Interpolation
Lie algebra precomputation of pulses plus neural network interpolation generates optimal controls for arbitrary unitaries in 2-4 qubit systems and generalizes to neutrino Trotter propagators.
-
Analog photonic simulator for large-scale transport
Continuous-variable photonic platform with 20,000-mode cluster state simulates advection transport equation, achieving relative errors of 0.8% and 0.92% on first- and second-order moments via homodyne readout.
-
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.
-
Hybrid Quantum Neural Networks for Efficient Protein-Ligand Binding Affinity Prediction
A hybrid quantum-classical network matches or slightly beats classical baselines on protein-ligand binding affinity prediction while using fewer parameters.
-
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.