Clifford Circuits: Simulating Thousands of Qubits in Milliseconds with Stim

The fastest simulation result on this platform is not a 30-qubit or a 100-qubit circuit. It is a 5,000-qubit GHZ circuit, 5,000 qubits with 5,000 layers of depth, simulated exactly in 0.56 seconds on a laptop. No approximation is involved and no trick is being played. The result follows from a theorem published in 1998 that remains the most consequential and least discussed structural result in quantum computing.

The Gottesman-Knill theorem

The theorem states that a quantum circuit composed entirely of Clifford gates, applied to a computational basis state and followed by measurement in the computational basis, can be simulated on a classical computer in polynomial time.

Two words carry the weight. Entirely: the guarantee is void if a single gate falls outside the set. Polynomial: not merely faster, but in a different complexity class from the exponential cost of statevector simulation.

The Clifford group is defined by a normaliser condition. A unitary U is Clifford if conjugating any Pauli operator by U yields another Pauli operator: U P U-dagger is in the Pauli group for every Pauli P. This is a strong closure property, and it is precisely what makes efficient simulation possible. The group is generated by the Hadamard gate H, the phase gate S, and CNOT, from which CZ, SWAP and all the Pauli gates follow.

The gates excluded are as important as those included. The T gate, a pi/4 phase rotation, is not Clifford. Neither is any Rz(theta) for generic theta, nor the Toffoli. These are exactly the gates that make a gate set universal, so the theorem draws its boundary at the edge of universality and no further.

The stabilizer formalism

The efficiency comes from changing what is stored. Instead of describing a state by its amplitudes, a stabilizer simulator describes it by the operators that leave it fixed.

A state |psi> is stabilized by an operator P when P|psi> = |psi>. For an n-qubit state that can be specified this way, n independent commuting Pauli operators suffice to determine it uniquely. The state |0...0> is stabilized by Z on each qubit individually. Applying a Hadamard to the first qubit changes its stabilizer from Z to X, which fully describes the new state without computing any amplitude.

Each Pauli operator on n qubits is specified by 2n bits plus a sign, so n generators occupy about 2n^2 bits. Storage is quadratic rather than exponential, which is the entire result. A 5,000-qubit stabilizer state occupies roughly 6 MB. The equivalent statevector would require 16 x 2^5000 bytes, a number with more digits than there are atoms in the observable universe.

Applying a Clifford gate updates the generator table by conjugation, which is a linear-time operation on the table. A CNOT with control a and target b sends the generator X on a to X on a and b, sends Z on b to Z on a and b, and leaves the others alone. Measurement is the only step with any subtlety: if the measured Pauli commutes with all generators the outcome is determined, and if it anticommutes with any, the outcome is uniformly random and the table is updated accordingly.

Representation   Storage for n qubits   n = 5,000
Statevector      16 x 2^n bytes         ~10^1500 bytes
Stabilizer       ~2n^2 bits             ~6 MB

Measured performance

Circuit                Qubits   Method        Wall time
GHZ (Clifford)             100   stabilizer    0.01 s
GHZ (Clifford)             500   stabilizer    0.06 s
GHZ (Clifford)           1,000   stabilizer    0.11 s
GHZ (Clifford)           5,000   stabilizer    0.56 s

The scaling visible in this table is roughly quadratic, consistent with the formalism. The reference open-source implementation is Stim, written by Craig Gidney at Google, which is vectorized, cache-tuned and capable of sampling circuits with millions of qubits. A router that scans a circuit's gate list and finds nothing outside the Clifford family selects this engine automatically, which is a single pass over the instruction list.

Why a restricted gate set matters

A method that only handles a fraction of circuits would be a curiosity if that fraction were arbitrary. It is not. Clifford circuits are precisely the circuits that quantum error correction is built from.

Stabilizer codes, which is to say essentially all codes under serious consideration, define their logical states as the joint eigenspace of a set of commuting Pauli operators. Syndrome extraction measures those operators using CNOTs and Hadamards. Surface codes, repetition codes, colour codes and the entire lattice-surgery apparatus are Clifford constructions by design.

The consequence is that the subfield with the largest qubit counts is the one classical simulation handles best. A distance-25 surface code uses over a thousand physical qubits, and studying its behaviour under noise requires millions of sampled shots. Both are routine with a stabilizer simulator and impossible by any other classical method. Essentially every error-correction paper published rests on this.

Hardware verification is the second application. Randomized benchmarking, GHZ fidelity tests and many calibration protocols are deliberately constructed from Clifford operations, precisely so that the ideal output can be computed classically and compared against what the device produced. A protocol whose expected result cannot be computed is not a benchmark.

Noise, and why sampling still works

A reasonable objection is that error correction is about noise, and noise makes states mixed rather than pure. The formalism appears to require pure stabilizer states.

The resolution is that Pauli noise can be sampled rather than represented. Instead of tracking a mixed state, the simulator draws which Pauli errors occurred according to their probabilities, inserts them into the circuit as ordinary gates, and simulates the resulting pure stabilizer circuit. Averaging over many such samples reproduces the noisy behaviour exactly, provided the noise is a Pauli channel.

This is why Pauli channels occupy the position they do in error correction, and why Pauli twirling exists: conjugating gates by random Paulis converts arbitrary noise into an effective Pauli channel, trading a modest fidelity loss for full simulability. The distinction between Pauli strings, Pauli channels and Pauli propagation is set out in Pauli strings, channels and propagation.

Where the hardness actually lives

The theorem carries a lesson that contradicts a widely held intuition.

• Entanglement alone does not make simulation hard. A 5,000-qubit GHZ state is about as entangled as a state can be, and it simulates in half a second. The identity equating entanglement with quantum computational power is false as a general statement, and treating it as true leads directly to mispriced simulation budgets.
• The hardness lives in non-Clifford resources, commonly called magic. This is a measurable quantity with several formal definitions, and it is what separates a classically simulable circuit from a hard one.
• T-gate count is the operative budget line. Simulating a Clifford circuit with t T gates costs roughly 2^t times the cost of the Clifford part under the standard stabilizer-decomposition approach, so a circuit with 40 T gates is at the edge of feasibility regardless of how many qubits it has. Compiler research aimed at T-count reduction is optimising precisely this quantity, for both classical simulation cost and fault-tolerant hardware cost, which are governed by the same resource.

The practical consequence is that a 200-qubit circuit with 20 T gates is easier to simulate than a 40-qubit circuit with 500. Width is the wrong variable.

In practice

For work touching error correction, hardware verification or stabilizer states, the procedure is: scan the gate list, and if nothing lies outside the Clifford family, the qubit ceiling is effectively removed, the answer is exact, and the cost is negligible. On this platform that scan is automatic and the routing follows from it.

For circuits that are nearly Clifford, the T-count determines feasibility, and reducing it through compilation is often the difference between a tractable simulation and an intractable one. For circuits that are neither, the methods in The 34-qubit wall apply instead.