Stabilizer formalism, Clifford group, Gottesman–Knill theorem
A circuit of a million gates on a thousand qubits ought to be impossible to simulate: amplitudes. Yet if the gates are only Hadamards, phase gates and CNOTs, a laptop does it in seconds, and Craig Gidney’s Stim simulator does billions of such gates per second. The trick is to stop tracking amplitudes and instead track which Pauli operators leave the state unchanged. Recognizing these easy circuits tells you exactly where quantum hardness has to come from.
On the plate: three qubits, tracked two ways at once: by amplitudes, and by stabilizers.
Stabilizers
The Pauli group on qubits is all products of I, X, Y, Z on each qubit, times ±1 or ±i. A state is a stabilizer state if it is the unique +1 eigenstate of commuting, independent Pauli operators, its stabilizer generators. is stabilized by Z; by X; the Bell state by XX and ZZ; the three-qubit GHZ state by XXX, ZZI, IZZ. Instead of amplitudes, you store Pauli strings: about bits. Established
Clifford gates update stabilizers
The Clifford group is the set of gates that map Pauli operators to Pauli operators under conjugation, . It is generated by H, S and CNOT. If stabilizes , then stabilizes , so each gate just rewrites the generators: H swaps X and Z on its qubit; S turns X into Y; CNOT spreads X from control to target and Z from target to control. Apply gates: . The tableau and the state vector stay in agreement.
The Gottesman–Knill theorem
Daniel Gottesman showed in 1997 (with credit to Emanuel Knill) that any circuit of Clifford gates, starting from computational basis states and ending in Pauli measurements, can be simulated efficiently classically. Scott Aaronson and Gottesman made it fast in 2004 with the CHP tableau algorithm. Clifford circuits can create highly entangled states, like large GHZ states, so entanglement alone does not make a quantum computer hard to simulate. One qubit has 24 Clifford gates up to phase; two qubits have 11,520. Established
Where hardness lives
Add one non-Clifford gate, such as T, and stabilizer tracking breaks: is not a Pauli operator. Simulations that handle a few T gates exist, with cost growing exponentially in their number. So T gates, or the magic states that supply them (Chapter 140), are the costly resource; contextuality (Chapter 107) is what they supply. Error correction, conversely, runs almost entirely on Clifford operations, which is why decoders and code simulators like Stim are fast.
What you now have
The Pauli group, stabilizer states and generators, Clifford gates as stabilizer updates, the tableau simulator, the Gottesman–Knill theorem, the sizes of the Clifford groups, and why T gates carry the cost.
· · ·
Three questions to carry with you.
And one to work out. How many single-qubit Clifford gates are there, up to global phase?
Sources: D. Gottesman, PhD thesis, Caltech (1997), arXiv:quant-ph/9705052; arXiv:quant-ph/9807006 (1998). S. Aaronson and D. Gottesman, Phys. Rev. A 70, 052328 (2004). C. Gidney, Quantum 5, 497 (2021) (Stim). M. A. Nielsen and I. L. Chuang, §10.5. Checked by code: breadth-first search over H and S finds 24 single-qubit Cliffords mod phase; the tableau updates agree with Book.QSim on every gate in the plate.