Improved Simulation of Stabilizer Circuits
read the original abstract
The Gottesman-Knill theorem says that a stabilizer circuit -- that is, a quantum circuit consisting solely of CNOT, Hadamard, and phase gates -- can be simulated efficiently on a classical computer. This paper improves that theorem in several directions. First, by removing the need for Gaussian elimination, we make the simulation algorithm much faster at the cost of a factor-2 increase in the number of bits needed to represent a state. We have implemented the improved algorithm in a freely-available program called CHP (CNOT-Hadamard-Phase), which can handle thousands of qubits easily. Second, we show that the problem of simulating stabilizer circuits is complete for the classical complexity class ParityL, which means that stabilizer circuits are probably not even universal for classical computation. Third, we give efficient algorithms for computing the inner product between two stabilizer states, putting any n-qubit stabilizer circuit into a "canonical form" that requires at most O(n^2/log n) gates, and other useful tasks. Fourth, we extend our simulation algorithm to circuits acting on mixed states, circuits containing a limited number of non-stabilizer gates, and circuits acting on general tensor-product initial states but containing only a limited number of measurements.
This paper has not been read by Pith yet.
Forward citations
Cited by 16 Pith papers
-
BPBO: Blindness-Preserving Brickwork Optimization by Certified Region Resynthesis
BPBO performs certified local resynthesis on one- to three-wire regions of BFK09 brickwork to reduce pattern size while preserving UBQC blindness, demonstrated on Grover and Toffoli cases with reductions up to 3x725 to 3x98.
-
Hierarchy of mixed symmetry protected topological states in extended cluster states under subsystem decoherence
Subsystem decoherence on extended cluster states generates a hierarchy of mixed SPT phases ending in Z2 SWSSB with glassy GHZ entanglement.
-
Clifft: Fast Exact Simulation of Near-Clifford Quantum Circuits
Clifft introduces a factored-state simulator that shifts exponential cost to a dynamic active subspace, generalizing Stim's compile-once model to near-Clifford circuits and enabling the first exact end-to-end simulati...
-
Gauge-invariant QMETTS with mutually unbiased physical bases for $Z_2$ lattice gauge theories at finite temperature and density
Introduces gauge-invariant QMETTS using mutually unbiased physical bases derived from stabilizer formalism for Z2 LGT at finite T and density, with single-shot sampling shown near-optimal and numerical validation in 1+1D.
-
The Pinnacle Architecture: Reducing the cost of breaking RSA-2048 to 100 000 physical qubits using quantum LDPC codes
Pinnacle Architecture using QLDPC codes reduces physical qubits needed to factor RSA-2048 to under 100,000 at 10^{-3} error rate.
-
Simulating quantum circuits with a neural statebank
A compact neural statebank based on autoregressive Transformers simulates 34-qubit quantum circuits with ~0.01 infidelity using 0.3 million parameters, outperforming tested approximate simulators.
-
Clifft: Fast Exact Simulation of Near-Clifford Quantum Circuits
Clifft achieves fast exact simulation of near-Clifford quantum circuits via dynamic active subspaces, delivering orders-of-magnitude speedups and the first full end-to-end simulations of magic state cultivation over h...
-
Clifford Orbits from Cayley Graph Quotients
Quotienting the Cayley graph of the Clifford group by a quantum state's stabilizer subgroup produces a graph of the state's Clifford orbit.
-
Hard-core Bosons in Action: Applications to Quantum Circuits
Hard-core boson algebra is reviewed and extended for quantum circuit simulation with reported speedups over Qiskit and a new genetic-algorithm application for circuit synthesis.
-
Distribution Complexity of Electronic Structure Simulations on Quantum Supercomputers
An algorithm is presented for estimating distribution complexity of electronic structure Hamiltonians, with O(N^3) entanglement estimation per fragment and quadratic/exponential reductions in distribution cost for qua...
-
Quantum Resources and Wigner Symmetry in Nucleon-Nucleon Scattering from Effective Field Theory
Under Wigner's SU(4) symmetry the neutron-proton scattering amplitude generates no new quantum resources while same-nucleon channels do due to identical-particle constraints.
-
Collective neutrino oscillations: Many-body non-forward effects and non-classicality
In a neutrino-gas model, the many-body Hamiltonian yields different evolution timescales and asymptotics than the quantum kinetic approach with collisions, while quantum resources for the full case sit at the low end ...
-
Magic and entanglement in 1+1-dimensional SU(2) lattice gauge theory
Tensor network calculation of magic and entanglement in SU(2) lattice gauge theory ground state shows a crossover from magic-rich to less-magic regime at g_star.
-
PauLIB: A High-Performance Library for Processing Pauli Strings
PauLIB implements a compact bit-packed symplectic representation and SoA layout for Pauli strings, delivering 14x–21,000x speedups and 7.3x memory reduction versus existing Python frameworks at 500 qubits.
-
Magic and Non-Clifford Gates in Topological Quantum Field Theory
Non-Clifford gates including Ising, Toffoli, and T arise as exact path integrals in Chern-Simons and Dijkgraaf-Witten topological quantum field theories.
-
Complexity of Quadratic Quantum Chaos
Hard-core boson two-body models with random interactions exhibit chaotic spectral statistics, operator growth, and eigenstate properties approaching those of random matrices and the SYK model.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.