Improved Simulation of Stabilizer Circuits

By Scott Aaronson, Daniel Gottesman. arXiv.org, 2004

1,660 citations recorded by the source corpus.

The Gottesman-Knill theorem says that a stabilizer circuit\char22{}that is, a quantum circuit consisting solely of controlled-NOT (CNOT), Hadamard, and phase gates\char22{}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 of 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 $\ensuremath{\bigoplus}\mathsf{L}$, 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}∕\mathrm{log}\phantom{\rule{0.2em}{0ex}}n)$ gates, and other useful tasks. Fourth, we extend our simulation algorithm to circuits acting on mixed states, circuits containing a limited number of nonstabilizer gates, and circuits acting on general tensor-product initial states but containing only a limited number of measurements.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/3a80e2ea153afb35ec5a45609787b2da751addd0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Quantum computing with Qiskit (2024, background): “Particularly structured sub-circuits may also be temporarily converted to specialized data structures to facilitate reasoning about the circuit at a more abstract level, for example Boolean linear functions [71], Clif-fords [14], or phase polynomials [20] .”
Quantum circuits and low-degree polynomials over F2 (2016, methodology): “If we choose S to include at least one variable from each of the degree-3 terms in f , each new polynomial produced has degree at most 2, and hence has gap computable in time O ( n 3 ) [16, 2].”
The computational complexity of linear optics (2010, background): “states (such as cos π 8 |0〉 + sin π 8 |0〉) and nonadaptive measurements [4].”
Schur–Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations (2017, background): “ently prepared. This contrasts with random Cliord unitaries and random stabilizer states, both of which can be eciently realized (they require at most O(n2) gates to implement in a quantum circuit) [AG04]. They have therefore repeatedly been suggested as\drop-in replacements"for their Haar-meas”
Qulacs: a fast and versatile quantum circuit simulator for research purpose (2020, methodology): “When quantum circuits are constructed only with efficiently simulatable quantum gates such as Clifford gates [78, 79] or matchgates [80–82], these circuits are efficiently simulated via specialized algorithms.”
Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer (2020, methodology): “Simulation of such a large number of qubits is possible due to the fact that we use a classical noise channel to model approximate GKPs and the circuits we simulate belong to the Clifford group, which makes them efficiently classically simulable [158].”
Quantum advantage with shallow circuits (2017, methodology): “e data register followed by measurement in the computational basis. A solution can be eﬃciently computed classically by simulating this circuit using the Gottesman-Knill Theorem (see for example Ref. [35]). Since p(z) is proportional to the absolute value squared of the Fourier transform of iq(x), s”
Simulating Quantum Computation by Contracting Tensor Networks (2005, background): “ut do not impose additional restrictions on how gates are interconnected or sequenced. A case in point is the seminal Gottesman-Knill Theorem [13] and its recent improvement by Aaronson and Gottesman [1]. These results apply only to circuits with stabilizer gates — Controlled-NOT, Hadamard, Phase, a”
Quantum computational supremacy (2017, background): “A non-trivial example of this is executing computations which are mostly or entirely comprised of Cliﬀord gates, which are known to be eﬃciently classically simulable 5,10 despite displaying such quantum characteristics as allowing the creation of large-scale entanglement.”
Evidence for the utility of quantum computing before fault tolerance (2023, background): “Clifford circuits serve as useful benchmarks of estimates produced by error mitigation, as they can be efficiently simulated classically 29 .”
Contextuality supplies the ‘magic’ for quantum computation (2014, neutral): “The independence number of the exclusivity graph associated with Σ~r is α(Γ~r) = p3 for all A~r ∈ ASIM so that, relative to our construction, exactly the states ρ /∈ PSIM are those that exhibit contextuality.”
Dynamical Purification Phase Transition Induced by Quantum Measurements (2019, methodology): “As a result, the associated encoding and recovery operations can be efficiently computed using the Gottesman-Knill theorem for the classical simulation of stabilizer circuits [62, 63].”
Linear growth of quantum circuit complexity (2021, background): “Hence the extended circuit’s complexity surpassed the original circuit’s complexity only a little—by, at most,O(n(2)/ log(n)) [2].”
Random Quantum Circuits (2022, methodology): “The Clifford property gives an efficient way of storing a class of states (232, 120, 233).”
Stim: a fast stabilizer circuit simulator (2021, background): “I compared Stim’s performance to Aaronson and Gottesman’s chp simulator [1], IBM’s Qiskit simulator (qiskit method=‘stabilizer’) [9], Google’s Cirq simulator (cirq.”
Statistical mechanics of quantum error correcting codes (2020, background): “(2), one can easily verify that [38]”
Predicting many properties of a quantum system from very few measurements (2020, methodology): “This can again be done using classical simulations of stabilizer states [2].”
High-threshold and low-overhead fault-tolerant quantum memory (2023, background): “Since the circuit involves only Clifford operations, its action can be compactly described using stabilizer tableau [49].”
A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits (2012, methodology): “In practice, computing each phase factor causes a significant performance hit, so we sought a more efficient way of removing phase equivalences.”