Shor and Steane codes

The 3-qubit repetition code catches bit-flips but not phase-flips. Add another layer of protection and you can catch both. The two classic codes that do this — the Shor code (1995) and the Steane code (1996) — were the first demonstrations that general quantum error correction is possible at all.

The Shor code: concatenation

Peter Shor’s insight was simple once you see it: use the repetition code twice, at two different levels.

1. Start with a logical qubit $|\psi\rangle$.
2. Encode it in the phase-flip repetition code, which is the same as the bit-flip code but in the $X$ basis. This turns one qubit into three and protects against $Z$ errors (which are phase-flips in the $Z$ basis but bit-flips in the $X$ basis).
3. Now each of those three qubits gets encoded into the bit-flip repetition code, turning each into three and protecting against $X$ errors.

Total: $3 \times 3 = 9$ physical qubits per logical qubit. The encoded logical states are:

$|0\rangle_L = \frac{1}{2\sqrt{2}}(|000\rangle + |111\rangle)(|000\rangle + |111\rangle)(|000\rangle + |111\rangle)$

$|1\rangle_L = \frac{1}{2\sqrt{2}}(|000\rangle - |111\rangle)(|000\rangle - |111\rangle)(|000\rangle - |111\rangle)$

This 9-qubit Shor code corrects any single-qubit error — bit-flip, phase-flip, or both ($Y$ error) — on any of the nine physical qubits. Concatenation works because bit-flip and phase-flip errors are “independent” in a precise sense, and you can correct them one layer at a time.

The overhead is high (9 physical : 1 logical), but the code works. It was proof of concept.

The Steane code: more efficient

Andrew Steane found a more efficient code shortly after Shor’s. The Steane code encodes one logical qubit into 7 physical qubits and corrects any single-qubit error. It’s based on a classical error-correcting code called the [7, 4, 3] Hamming code, adapted to the quantum setting.

The Steane code’s logical basis states are:

$|0\rangle_L = \frac{1}{\sqrt{8}}\big(|0000000\rangle + |1010101\rangle + |0110011\rangle + |1100110\rangle + |0001111\rangle + |1011010\rangle + |0111100\rangle + |1101001\rangle\big)$

and a similar superposition for $|1\rangle_L$, with the bit labels complemented. Don’t try to memorize these — the point is just that the encoding is an equal superposition over codewords of a classical error-correcting code, which lets the quantum correction “inherit” the classical correction property.

The Steane code is what’s called a CSS code (Calderbank-Shor-Steane), a family where the quantum code’s structure is derived from a pair of classical linear codes. CSS codes are particularly easy to reason about and have played a big role in the theoretical development of QEC.

The quantum threshold theorem

Here is the single most important theoretical result in fault-tolerant quantum computing, which fell out of the work on codes like Shor and Steane:

Quantum threshold theorem. If the physical error rate per gate is below some threshold (estimates range from $10^{-4}$ to $10^{-2}$, depending on the code and noise model), then by using a good enough code and enough redundancy, you can reduce the logical error rate to an arbitrarily small value — while paying only a polylogarithmic overhead per logical gate.

In practical terms: if you can build physical qubits with error rates below the threshold, you can build arbitrarily reliable logical qubits out of them. The error rate of logical qubits can be made as small as you like, by using more physical qubits and more rounds of error correction.

This theorem is why fault-tolerant quantum computing is considered possible in principle. Without a threshold, stacking more error correction just compounds the noise. With a threshold, each layer makes things better.

Today: we’re approaching the threshold

As of the mid-2020s, the best superconducting and trapped-ion qubits have error rates of around $10^{-3}$ per gate — right at the edge of the threshold for the more forgiving codes (notably the surface code, which is the topic of the next lesson and has the most lenient threshold, around $1\%$).

Multiple hardware teams (Google, IBM, AWS, IonQ, Quantinuum, PsiQuantum) have demonstrated small logical qubits with error rates lower than the physical qubits they’re built from — meaning the error correction is net beneficial rather than overhead-to-nowhere. This is a relatively new milestone (first convincingly demonstrated around 2023), and it’s the real kickoff of the fault-tolerant era.

What’s next

The surface code is the modern workhorse of quantum error correction. It doesn’t match the asymptotic scaling of best-known codes, but its extremely lenient error threshold and 2D-lattice layout make it the favorite for actual hardware implementation. It’s what Google, IBM, and most other players are building toward.