138
Part Three · D · Error correction and fault tolerance

Stabilizer codes in depth

Shor’s and Steane’s codes are two members of a vast family, and one language describes them all. Daniel Gottesman’s 1997 PhD thesis recast quantum codes in terms of the Pauli operators that leave them unchanged, the stabilizer formalism of Chapter 108. In that language you can read off how many logical qubits a code holds, which operators act on them, and how many errors it survives. It also leads to a theorem that shapes the architecture of every planned quantum computer.

On the plate: a stabilizer-code explorer that computes each code’s parameters from its generators.

[[n, k, d]]

A stabilizer code on nn qubits is defined by n−kn-k independent, commuting Pauli generators; the code space is their common +1 eigenspace, of dimension 2k2^k. Logical operators are Paulis that commute with every stabilizer but are not themselves in the stabilizer group: they move between codewords without being detected. The distance dd is the smallest weight of a logical operator. A code of distance dd detects d−1d-1 errors and corrects ⌊(d−1)/2⌋\lfloor(d-1)/2\rfloor. Double brackets distinguish quantum codes from classical [n,k,d][n,k,d] codes. Established

Explore codes

Choose a code: . The plate shows the generators, checks that they commute, computes kk by Gaussian elimination over pairs of bits, and finds the distance by searching all Pauli operators up to weight 4 for the lightest logical one.

Notice the bit-flip code: as a quantum code it has distance 1, because a single Z on any qubit is a logical error. The five-qubit code, found by Raymond Laflamme and colleagues and by Charles Bennett and colleagues in 1996, is the smallest that corrects any single-qubit error. Established

Bounds, transversal gates, and Eastin–Knill

The quantum Singleton bound says n−k≥2(d−1)n - k \ge 2(d-1): to correct one error in one logical qubit you need n≥5n\ge5. The quantum Hamming bound for nondegenerate codes, 2n−k≥1+3n2^{n-k}\ge 1 + 3n for single errors, is met with equality at n=5n = 5: the five-qubit code is perfect, every syndrome used exactly once.

The easiest fault-tolerant gates are transversal: apply a gate to each physical qubit separately, so one fault cannot spread within a code block. The Steane code has transversal H, S and CNOT, the whole Clifford group, but not T. Bryan Eastin and Emanuel Knill proved in 2009 that no code that detects errors can have a universal set of transversal gates. Every architecture must therefore supply at least one gate another way, usually by consuming specially prepared “magic states” (Chapter 140). That single theorem is why magic-state factories dominate resource estimates (Chapter 143). Established

What you now have

[[n, k, d]] notation, logical operators as the normalizer modulo the stabilizer, distance, the quantum Singleton and Hamming bounds, the perfect five-qubit code, transversal gates, and the Eastin–Knill theorem.

· · ·

Three questions to carry with you.

How is k determined?tap
k = n minus the number of independent stabilizer generators.
Why is the 3-qubit bit-flip code distance 1 as a quantum code?tap
A single Z commutes with all its ZZ stabilizers and flips the logical phase.
What does Eastin–Knill forbid?tap
An error-detecting code with a universal set of transversal gates.

And one to work out. By the quantum Singleton bound, what is the smallest nn for k=1k = 1, d=3d = 3?

n ≥

Sources: D. Gottesman, PhD thesis, Caltech (1997), arXiv:quant-ph/9705052. D. Gottesman, Surviving as a Quantum Computer in a Classical World (draft, 2026). R. Laflamme et al., Phys. Rev. Lett. 77, 198 (1996). C. H. Bennett et al., Phys. Rev. A 54, 3824 (1996). E. Knill and R. Laflamme, Phys. Rev. A 55, 900 (1997). B. Eastin and E. Knill, Phys. Rev. Lett. 102, 110502 (2009). Checked by the plate: k and d computed from generators; it returns [[3,1,1]], [[4,2,2]], [[5,1,3]], [[7,1,3]], [[9,1,3]].

Next · Chapter 139
The surface code and decoders (MWPM, union-find, ML decoders)

In 2024, Google showed that adding qubits made errors fall, by a factor of 2.14 for each step up in code size.

Turn the page