How can you describe a quantum state by what leaves it unchanged, and why is that the language error correction is written in?
Topic 04 showed that an unknown state cannot be copied, which is why error correction cannot simply keep three copies. This topic shows what it does instead: it names a state by the operators that leave it unchanged, and reads errors off by checking those operators. It sits last because it was written last, not because it must be read last: it needs topic 01 and the Bell pair of topic 02, and the error-correction lesson's Formal tier points here.
Topic 01 described a state by its amplitudes, and an n-qubit state has 2n of them. There is a second way to describe some states, much shorter: list the operations that leave the state exactly as it was. The Bell pair is unchanged by XX (flip both qubits), unchanged by ZZ (it only asks whether the two qubits agree, and in 00 and 11 they do), and so by their product, −YY. Those two generators pin the state down completely. The states that can be named this way are called stabilizer states, and the operators that fix them are built only from the Pauli matrices I, X, Y and Z.
Why error correction is written in this language. A code is the set of states that a chosen list of commuting Pauli operators all leave unchanged. Measure those operators and you learn whether an error has happened, because a Pauli error that anticommutes with one of them flips the value you read for it, without telling you anything about which state you were protecting. The smallest example is the three-qubit repetition code with checks Z1Z2 and Z2Z3: an X error on qubit 1 fires only the first check, on qubit 3 only the second, on qubit 2 both, and the pattern says where to fix it. The surface code in the error-correction lesson is the same idea with more checks.
Cliffords. A gate that turns every Pauli operator into another Pauli operator keeps a stabilizer state a stabilizer state. These gates form the Clifford group, generated by H, S and CNOT. They are exactly the gates you can track by rewriting the short list of generators, and that is the whole of why they are easy: circuits made only of Clifford gates, stabilizer-state inputs and Pauli measurements can be simulated efficiently on an ordinary computer (the Gottesman–Knill theorem). Add one gate that is not a Clifford, such as T, and the shortcut stops working. That single missing ingredient is what the “magic states” in the error-correction lesson supply.
What this does not mean. It does not mean entanglement is somehow cheap or fake: the Bell pair above is entangled, and Clifford circuits make it. It means that entanglement of this particular, highly structured kind can be bookkept in a short list. Nor does it mean a classical computer can simulate “a quantum computer”: only the Clifford-and-stabilizer part.
The Pauli group. On n qubits, the Pauli strings are the 4n tensor products of I, X, Y, Z, and the Pauli group Pn also allows a sign or a factor of i. Any two Pauli strings either commute or anticommute. Write each string as a binary vector (x|z) with a 1 in x where it has an X or Y and a 1 in z where it has a Z or Y; two strings commute exactly when the symplectic product x·z′ + z·x′ is 0 mod 2, and a non-identity string commutes with exactly half of all 4n strings.
A stabilizer state. Take an abelian subgroup S of Pn that does not contain −I, with n independent generators g1…gn. Exactly one state (up to a global phase) is fixed by all of S, and its projector is
|ψ⟩⟨ψ| = (1/2n) Σg∈S g
For the Bell pair, S = {II, XX, ZZ, −YY}, so the projector is (II + XX + ZZ − YY)/4; and XX·ZZ = (XZ)⊗(XZ) = (−iY)⊗(−iY) = −YY. Of all 32 signed two-qubit Pauli strings, exactly these four fix the Bell state.
A stabilizer code. Use only n − k independent commuting generators on n qubits. Their common +1 space has dimension 2k: k logical qubits. Three qubits with Z1Z2 and Z2Z3 gives k = 1, with code states |000⟩ and |111⟩ and these syndromes (1 means that check reads −1):
X1 → (1,0) X2 → (1,1) X3 → (0,1) Z1, Z2, Z3 → (0,0)
so every single X error is located and corrected, while single Z errors are not even seen: this code protects against only one kind of error, and the surface code needs both kinds of check. The distance-3 surface code on nine data qubits, numbered row by row, has eight generators, four of each type:
Z1Z2Z4Z5 Z5Z6Z8Z9 Z4Z7 Z3Z6
X2X3X5X6 X4X5X7X8 X1X2 X8X9
They all commute and are independent, so k = 9 − 8 = 1. No Pauli string of weight 1 or 2 commutes with all eight without already being in the group, so no one or two errors go unseen; weight 3 is the smallest that does, for example X1X4X7 or Z1Z2Z3, which anticommute with each other and are the logical X and Z. That is distance 3. Verified exhaustively: 8 commuting independent generators on 9 qubits, no undetected non-trivial Pauli of weight 1 or 2, and 24 of weight 3.
The Clifford group. A unitary U is a Clifford if U P U† is a signed Pauli string for every Pauli string P. The generators act on the Paulis as
H: X → Z, Y → −Y, Z → X
S: X → Y, Y → −X, Z → Z
CNOT (first controls): XI → XX, IX → IX, ZI → ZI, IZ → ZZ
and T does not belong: T X T† = (X + Y)/√2, a sum of two Pauli strings. All of these tables, and the non-Clifford status of T, are recomputed in every Pauli string through H, S, CNOT and T, by explicit matrices.
The bookkeeping. To follow a stabilizer state through a Clifford circuit, keep each generator as bits (x|z) and a sign, and update them gate by gate: H swaps x and z on that qubit and flips the sign if both were 1; S adds x into z and flips the sign if both were 1; CNOT from a to b adds xa into xb, adds zb into za, and flips the sign when xa = zb = 1 and xb = za. That is n generators of 2n + 1 bits: n(2n + 1) bits, 20,100 bits for 100 qubits, against 2100 amplitudes. Checked against exact simulation: 5,000 random Clifford circuits on 2 to 5 qubits, every tracked generator had expectation +1 on the exactly simulated state. Aaronson and Gottesman's improved version, the CHP simulator, handles thousands of qubits; they also show the problem is complete for the classical class ParityL.
How many stabilizer states. There are 2n ∏k=1..n(2k + 1) of them on n qubits: 6, 60 and 1,080 for one, two and three qubits, each counted here as the orbit of |0…0⟩ under H, S and CNOT (6, 60 and 1,080 for n = 1, 2, 3, equal to the formula). The six for one qubit are the six points where the Bloch sphere meets its axes.
Beyond Cliffords. The set {H, T, CNOT} is universal in the approximate sense (Boykin et al. 1999); the Clifford gates are not. Gottesman, Stabilizer Codes and Quantum Error Correction (Caltech thesis, 1997), arXiv quant-ph/9705052, and The Heisenberg Representation of Quantum Computers, arXiv quant-ph/9807006; Aaronson & Gottesman, Improved Simulation of Stabilizer Circuits, Phys. Rev. A 70, 052328 (2004), arXiv quant-ph/0406196; Boykin, Mor, Pulver, Roychowdhury & Vatan, arXiv quant-ph/9906054.
Every surface-code check, and the reason magic states exist The parity checks a surface-code patch measures every cycle are stabilizer generators, and a decoder is a program that reads their pattern of flips and guesses the error (the error-correction lesson). The same structure explains why logical Clifford gates are comparatively cheap on such a code and why the T gate is not: a T gate is the one ingredient that breaks the stabilizer bookkeeping, so a fault-tolerant machine prepares special “magic” states and consumes them. On the classical side, stabilizer simulators such as Stim (Gidney, Quantum 5, 497, 2021) are what lets researchers test thousands of error-correction experiments on a laptop, precisely because the circuits are Clifford. Where a circuit is not Clifford, that shortcut is gone and the cost climbs steeply.
Check yourself
A circuit starts in |000⟩, uses only H, S and CNOT gates, and ends with Pauli measurements. What does the Gottesman–Knill theorem say about simulating it?
Every one of those gates turns a Pauli operator into another Pauli operator, so the state stays a stabilizer state and can be followed by rewriting three short generators, not eight amplitudes. Entanglement is no obstacle: this very circuit family makes Bell pairs. The shortcut is lost only when a non-Clifford gate such as T is added.
The tempting wrong answers.