REVIEW 32 cited by
Improved Simulation of Stabilizer Circuits
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
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.
Forward citations
Cited by 32 Pith papers
-
Local Equivalences of Graph States
Graph states are LU-equivalent if and only if they are linked by r-local complementations for some integer r; LU-equivalence is decidable in quasi-polynomial time, and LU=LC holds on at most 19 qubits.
-
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.
-
Fast logical operations in quantum LDPC codes using simple resource states
A scheduler-code protocol jointly measures up to 20 commuting logical operators in quantum LDPC codes with ~1.7 cat states per operator, yielding up to 3x faster logical measurements and up to 74x faster Clifford circ...
-
Magic without a phase: phase-independent stabilizer R\'enyi entropy in gluon scattering
A phase-averaged stabilizer Rényi entropy is introduced for tree-level gluon scattering, with color-independent phase-independent magic that is larger in 3→2 than 2→2 and has a soft-limit lower bound in 2→3.
-
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.
-
Efficiently simulable quantum circuits with large entanglement, magic, and non-Gaussianity via code-compiled tensor networks
High-rate CSS codes compile nonlocal Clifford and non-Clifford logical circuits into onsite phases and classical permutations, so MPS bond dimension stays fixed by the encoder while logical entanglement, magic, and no...
-
Analytical Landscape of Maximal Magic for Two-Qutrit States and Beyond
Maximal stabilizer Rényi entropy for two-qutrit states is ln(81/17), achieved at 18 degenerate maxima; a general prime-d formula ln[d⁴/(2d²−1)] is conjectured and verified for d=2,3,5.
-
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...
-
DAGAF: A directed acyclic generative adversarial framework for joint structure learning and tabular data synthesis
A data-agnostic circuit harmonic matrix C factorises Fourier-coefficient statistics and quantum neural tangent kernels for a broad class of re-uploading parametrised quantum circuits.
-
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.
-
Harvest: Resource-Aware Quantum Compilation for Magic State Protocols
Harvest co-optimizes placement, routing, scheduling, and magic-state supply for lattice-surgery quantum programs, reporting up to 17.8x speedup over sequential execution and reclaiming up to 72% of unused magic-state patches.
-
Magic-protected entanglement and Clifford-irreducible structure in magic state space
Quantum states are classified by how much bipartite entanglement survives optimal simplification by classically easy Clifford operations, yielding a split into weakly protected T-magic and strongly protected W-magic regimes.
-
A conditional no-go for resource-free magic-axis measurement on a static surface code
Under three stated assumptions, a resource-free static surface-code patch cannot sharply measure the magic axis at polynomial acceptance; it must pay with a resource, leave the dilute regime, or accept exponentially rarely.
-
Wigner negativity in Krylov space and emergent semiclassicality
Wigner negativity in Krylov space stays O(1) or grows as t^{1/2} (without Hilbert-space scaling) in 2d CFTs, one-cut matrix models, and double-scaled SYK, indicating emergent semiclassicality.
-
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.
-
Efficient simulation of logical magic state preparation protocols
A classical simulation method that propagates circuit-level Pauli noise to a Clifford error makes logical magic-state preparation protocols simulable in time polynomial in qubits and the target state's stabilizer rank.
-
On the stabilizer complexity of Hawking radiation
In the PSSY model, the Wigner negativity (stabilizer magic) of Hawking radiation is O(1) before the Page time and grows as sqrt(2/pi) exp((S_max - S_2)/2) afterward; a similar formula is proposed for holographic state...
-
Extremal Magic States from Symmetric Lattices
Vectors from symmetric lattices E8, BW16, and E6 map onto stabiliser and maximal-magic states, yielding explicit three-qubit and one-qutrit magic states and conjectured complete counts.
-
Stabilizer Tensor Networks with Magic State Injection
A classical simulation framework called MAST, built by adding magic state injection to stabilizer tensor networks, simulates random T-doped Clifford circuits with up to N T-gates in polynomial time and hidden shift ci...
-
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.
-
Production of Magic States via $Z$ Bosons and Dark Photons
Magic distributions are computed for EW processes (reproducing QED at low energy, new at high energy/Z resonance) and dark-sector scatterings, reaching maximal magic at mass ratios m_f/m_χ → 0 and → 1.83929.
-
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.
-
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.
-
Delay-Independent Stability of Nonlinear Delay Differential Equations via Isospectral Reduction
Claims a delay-independent global exponential stability criterion for a broad class of nonlinear nonautonomous delay differential equations using isospectral reduction of an associated sequence of matrices.
Discussion (0). Continue with ORCID to comment.