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 simulations of magic-state cultivation over hundreds of billions of shots.
Improved simulation of stabilizer circuits
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
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.
citation-role summary
background 1
method 1
citation-polarity summary
representative citing papers
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.
Pinnacle Architecture using QLDPC codes reduces physical qubits needed to factor RSA-2048 to under 100,000 at 10^{-3} error rate.
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 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.
Non-Clifford gates including Ising, Toffoli, and T arise as exact path integrals in Chern-Simons and Dijkgraaf-Witten topological quantum field theories.
citing papers explorer
-
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 simulations of magic-state cultivation over hundreds of billions of shots.
-
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.
-
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.
-
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.
-
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.