REVIEW 34 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
Signed reviews
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 34 Pith papers
-
Can effective descriptions of bosonic systems be considered complete?
Polynomial Hamiltonians are proven universal for physical single-mode bosonic unitary evolutions, with explicit error bounds and an infinite-dimensional Solovay-Kitaev theorem.
-
Quantum algorithm for estimating volumes of convex bodies
A quantum algorithm estimates the volume of an n-dimensional convex body within error epsilon using O-tilde(n^3 + n^2.5/epsilon) membership queries, the first quantum speedup for this task.
-
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.
-
Local Universality and Structural Certificates for Minimal Fixed-Depth Two-Qutrit Gate Decomposition
A four-copy fixed-core architecture with five local SU(3)⊗SU(3) layers is shown to be locally universal for two-qutrit gates, via an explicit Clifford core that makes the differential an exact isometry.
-
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.
-
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.
-
Transversal Gates for Highly Asymmetric qLDPC Codes
First qLDPC code constructions with transversal non-Clifford phase gates, obtained by embedding a local code with the desired transversal gate into a Tanner-based hypergraph or balanced product code, at the cost of O(...
-
Quantum circuits as a game: A reinforcement learning agent for quantum compilation and its application to reconfigurable neutral atom arrays
A transformer-based reinforcement learning agent learns to reconfigure atoms in neutral atom arrays and reduces estimated logarithmic infidelity by up to about 20% on benchmark circuits, including unseen ones.
-
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.
-
Unlocking the power of global quantum gates with machine learning
Finite-depth circuits made of global CZ/CX gates and single-qubit rotations can approximate ground states of Heisenberg and toric code Hamiltonians in variational training.
-
Topological quantum compilation of metaplectic anyons based on the genetic optimized algorithms
A gate compilation scheme for SO(3)_2 metaplectic anyons, using braids plus auxiliary Z-anyon insertions, is shown to approximate H, T, and CNOT gates with high numerical precision but without topological protection.
-
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.
-
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.
-
A small and interesting architecture for early fault-tolerant quantum computers
An early fault-tolerant quantum computer architecture that uses teleportation between the [[4,2,2]] and [[8,3,2]] color codes for a universal transversal gate set, plus a mirror-circuit benchmarking protocol.
-
Quantum Framework for Simulating Linear PDEs with Robin Boundary Conditions
Linear PDEs with Robin boundary conditions can be simulated with explicit oracle-free quantum circuits whose gate count grows polynomially in grid size and linearly in dimension.
-
Symbolic Hamiltonian Compiler for Hybrid Qubit-Boson Processors
An automated symbolic compiler maps second-quantized fermion-boson Hamiltonians to qubit-boson gate sets, with gate counts per Trotter step that grow linearly with system size in the 1D benchmarks.
-
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.
-
RH: An Architecture for Redesigning Quantum Circuits on Quantum Hardware Devices
An EQ-GAN architecture with random input states learns quantum circuit behavior and is used for equivalence checking and variational circuit optimization.
-
Transpiler-Architecture Co-Design to Curb Clifford Costs in Fault-Tolerant Quantum Computing
TACO cuts 91.7% of Clifford gates in benchmark circuits using RX(pi/4)-based rewrites and a 1.5n+4 tile architecture, though reported speedups range from 2.3x to a contradictory 21.9x.
-
Design Automation in Quantum Error Correction
A comprehensive review of automated tools and methods for designing quantum error-corrected circuits, with case studies on T-gate optimization, surface-code layout, ML decoders, and verification.
-
Quantum Machine Learning: A Hands-on Tutorial for Machine Learning Practitioners and Researchers
A structured tutorial that introduces quantum machine learning concepts, algorithms, theory, and PennyLane code to classical ML practitioners.
Discussion (0). Continue with ORCID to comment.