dorsal/arxiv
View SchemaImproved Simulation of Stabilizer Circuits
| Authors | Scott Aaronson, Daniel Gottesman |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0406196 |
| URL | https://arxiv.org/abs/quant-ph/0406196 |
| DOI | 10.1103/PhysRevA.70.052328 |
| Journal | Phys. Rev. A 70, 052328 (2004) (14 pages) |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
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.
{
"annotation_id": "d50b9879-f65b-465b-9bc0-48948779d65f",
"date_created": "2026-03-02T18:02:09.530000Z",
"date_modified": "2026-03-02T18:02:09.530000Z",
"file_hash": "034261e9bfcd907dc3e97f15fd2e56b399e93f0c4c3daa6bfbf43e61fa4c658d",
"private": false,
"record": {
"abstract": "The Gottesman-Knill theorem says that a stabilizer circuit -- that is, a\nquantum circuit consisting solely of CNOT, Hadamard, and phase gates -- can be\nsimulated efficiently on a classical computer. This paper improves that theorem\nin several directions. First, by removing the need for Gaussian elimination, we\nmake the simulation algorithm much faster at the cost of a factor-2 increase in\nthe number of bits needed to represent a state. We have implemented the\nimproved algorithm in a freely-available program called CHP\n(CNOT-Hadamard-Phase), which can handle thousands of qubits easily. Second, we\nshow that the problem of simulating stabilizer circuits is complete for the\nclassical complexity class ParityL, which means that stabilizer circuits are\nprobably not even universal for classical computation. Third, we give efficient\nalgorithms for computing the inner product between two stabilizer states,\nputting any n-qubit stabilizer circuit into a \"canonical form\" that requires at\nmost O(n^2/log n) gates, and other useful tasks. Fourth, we extend our\nsimulation algorithm to circuits acting on mixed states, circuits containing a\nlimited number of non-stabilizer gates, and circuits acting on general\ntensor-product initial states but containing only a limited number of\nmeasurements.",
"arxiv_id": "quant-ph/0406196",
"authors": [
"Scott Aaronson",
"Daniel Gottesman"
],
"categories": [
"quant-ph",
"cs.CC"
],
"doi": "10.1103/PhysRevA.70.052328",
"journal_ref": "Phys. Rev. A 70, 052328 (2004) (14 pages)",
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Improved Simulation of Stabilizer Circuits",
"url": "https://arxiv.org/abs/quant-ph/0406196"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c92ef678-1678-4b16-a9f3-bdd2c0838b20",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}