Gottesman Knill Stabilizer Simulation

Short answer: The Gottesman-Knill theorem says a stabilizer circuit, meaning a quantum circuit made only of controlled-NOT, Hadamard and phase gates, can be simulated efficiently on a classical computer. A 2004 paper made the simulation faster and released a program called CHP that handles thousands of qubits, and a 2006 paper gave a faster algorithm based on graph states. The theorem is why stabilizer circuits alone do not give quantum advantage.

The theorem

The 2004 Physical Review A paper, "Improved simulation of stabilizer circuits", states the theorem as: a stabilizer circuit, consisting solely of CNOT, Hadamard and phase gates, can be simulated efficiently on a classical computer. The 2006 paper on fast simulation says the same of the class of circuits called stabilizer circuits, in the words of the theorem.

Making the simulation faster, 2004

The 2004 paper improves the theorem in several directions. First, by removing the need for Gaussian elimination, it makes the simulation algorithm much faster at the cost of a factor of 2 increase in the number of bits needed to represent a state. The authors implemented it in a freely available program called CHP (CNOT-Hadamard-phase), which they say can handle thousands of qubits easily.

Second, they show that the problem of simulating stabilizer circuits is complete for the classical complexity class parity-L, which means, they say, that stabilizer circuits are probably not even universal for classical computation. Third, they give efficient algorithms for computing the inner product of two stabilizer states and for putting any n-qubit stabilizer circuit into a canonical form needing at most order n squared over log n gates. Fourth, they extend the algorithm to circuits acting on mixed states, circuits with a limited number of nonstabilizer gates, and circuits acting on general tensor-product initial states with a limited number of measurements.

A graph-state approach, 2006

A 2006 Physical Review A paper introduces an algorithm for the same task based on the graph-state formalism. The authors say it shows significant improvement over an existing algorithm by Gottesman and Aaronson in speed and in the number of qubits the simulator can handle, and they present an implementation. In the standard representation, a stabilizer state is described by a tableau of Pauli operators needing space of order N squared for N qubits. The graph-state representation instead stores a graph plus local operators, with space of order N times the average vertex degree, which can be smaller when graphs are sparse.

Why it matters

Stabilizer circuits are central to quantum error correction. Because they can be simulated classically, researchers can test stabilizer-based codes and decoders on large numbers of qubits without a quantum computer. The converse also holds: since these circuits are classically easy, a useful quantum speedup needs gates beyond the stabilizer set. The 2004 paper's extension to circuits with a limited number of nonstabilizer gates shows how the cost grows as such gates are added.

What this does not tell you

The abstracts do not give timing figures or hardware comparisons, and the simulation methods apply to stabilizer circuits and limited extensions, not to general quantum circuits.

FAQ

What does the Gottesman-Knill theorem say?

Circuits made only of CNOT, Hadamard and phase gates can be simulated efficiently on a classical computer.

What is CHP?

A freely available program from the 2004 paper that simulates stabilizer circuits, handling thousands of qubits.

Are stabilizer circuits universal for quantum computing?

No. The 2004 paper says they are probably not even universal for classical computation.

Can the simulation handle other gates?

The 2004 paper extends it to a limited number of nonstabilizer gates.

Is there a faster method?

A 2006 paper gives a graph-state algorithm it reports as faster than the earlier tableau-based method.