Quantum Error Correction

Chapter 5 gave us the language; now we use it to protect. A stabilizer code encodes $k$ logical qubits into $n$ physical ones by choosing a set of $n-k$ independent, mutually commuting Pauli operators — the stabilizer generators $g_1,\dots ,g_{n-k}$ — and declaring the code space to be their simultaneous $+1$ eigenspace:

One requirement hides in plain sight: the group the $g_i$ generate must not contain $-I$, for no state satisfies $-I|\psi ⟩=|\psi ⟩$ — a stabilizer group containing $-I$ stabilizes nothing at all. With that guaranteed, the $n-k$ generators each halve the space, so the code space has dimension $2^k$ — room for $k$ logical qubits. Now suppose an error $E$ (a Pauli) strikes. Each generator either commutes or anticommutes with $E$ (Chapter 5's dichotomy), so measuring all $n-k$ generators returns a bit string — the syndrome — whose $i$-th bit is 0 if $[g_i,E]=0$ and 1 if they anticommute. Crucially, measuring $g_i$ on a code state reveals only this parity; it does not touch the logical information, because the logical operators are chosen to commute with every generator.

A code is rated by three numbers, $[[n,k,d]]$: $n$ physical qubits, $k$ logical qubits, and the distance $d$ — the weight of the smallest Pauli error that is undetectable (commutes with every generator yet acts nontrivially on the code space). A distance-$d$ code corrects any error on up to $\lfloor (d-1)/2\rfloor$ qubits. The precise condition, due to Knill and Laflamme (1997), is that a set of errors $\{E_a\}$ is correctable on the code with projector $P$ exactly when

for some Hermitian matrix $c_{ab}$. When $c$ is invertible the code is nondegenerate, and — exactly as for a classical distance-$d$ code — two distinct correctable errors carry distinct syndromes. When $c$ is singular the code is degenerate: two distinct errors can share a syndrome, but harmlessly, because their product $E_a^{†}{E}_b$ then lies in the stabilizer and so acts identically on the code space — one recovery fixes both. Shor's code in the next section is degenerate, so beware the tempting half-truth that correctable errors can never collide: they can, and the code loses nothing for it. The whole game of this chapter is building codes with large $d$ out of simple, local checks.

The first quantum code, and still the clearest, is Peter Shor's nine-qubit code (1995). It confronts the two ways a qubit can go wrong — a bit flip $X$ and a phase flip $Z$ — and beats them by concatenation: nesting one code inside another. Start with the three-qubit repetition code of Chapter 10, which corrects a single bit flip by encoding

Its Hadamard-conjugate, encoding $|\pm ⟩\mapsto |\pm \pm \pm ⟩$, corrects a single phase flip instead. Shor's insight: nest them. Encode the qubit first in the phase-flip code, then encode each of those three qubits in the bit-flip code. The result uses $9$ qubits and its logical states are

Now any single-qubit error is caught. A bit flip is corrected inside its block of three; a phase flip is corrected across the three blocks. And here is the part that first looked like magic: a small continuous rotation $e^{i\theta X}=\cos \theta I+i\sin \theta X$ is also corrected, because the syndrome measurement digitizes it — projecting the state onto either “no error” or “a clean $X$,” each of which the code handles. The continuum of quantum errors, which seemed to doom the whole enterprise, collapses to a finite set the moment you measure the stabilizers. That single fact is why quantum error correction is possible.

Shor's code hints at a general construction. If bit flips and phase flips can be handled separately, why not build a quantum code out of two classical codes — one to catch $X$ errors, one to catch $Z$ errors? This is the idea of CSS codes, after Calderbank, Shor, and Steane. Take two classical linear codes $C_1,C_2$ with $C_2\subset C_1$. The $Z$-type stabilizers are the parity checks of $C_1$ (they detect $X$ errors), and the $X$-type stabilizers come from the dual of $C_2$ (they detect $Z$ errors). Because these two check sets are built to be orthogonal over ${\mathbb{F}}_2$, every $X$-check commutes with every $Z$-check — the stabilizer requirement is met automatically.

The Steane code is the jewel of the family: take $C_1$ to be the $[7,4,3]$ Hamming code and $C_2=C_1^{\perp }$ its dual — the $[7,3,4]$ simplex code, which the Hamming code contains, so $C_2\subset C_1$ holds — and you get a $[[7,1,3]]$ quantum code — seven physical qubits, one logical qubit, distance three, correcting any single-qubit error with six stabilizer generators (three $X$-type, three $Z$-type), each a weight-four parity. It is more efficient than Shor's nine and, because its $X$ and $Z$ checks have the same form, it admits especially clean logical gates. CSS codes remain the backbone of the field — the surface code we turn to next is itself a CSS code, just laid out on a grid so that every check is local.

The Steane code is beautiful but its checks are non-local — a weight-four parity may involve qubits scattered anywhere, which no two-dimensional chip can wire up cheaply. The surface code (Kitaev, 1997) fixes this with a layout so simple it looks like graph paper. Put data qubits on the edges of a square lattice. On each vertex place a $Z$-type check (a star: the product of $Z$ on the four incident edges); on each face place an $X$-type check (a plaquette: the product of $X$ on the four bordering edges). At a boundary a check simply loses the edges that are not there. Every check touches only its few nearest neighbours — perfectly local, perfectly 2-D. This is the convention the lab and every widget in this chapter use: $Z$-checks on vertices catch $X$ errors, $X$-checks on faces catch $Z$ errors.

What is a logical qubit here? The stars and plaquettes leave a few degrees of freedom unfixed, and those are the logical operators: strings of $X$ or $Z$ that run all the way across the lattice from one boundary to the other (or, on a torus, all the way around). Such a string commutes with every local check — it crosses each check an even number of times — so it is invisible to the syndrome, yet it acts nontrivially on the encoded state. Its length is the code distance $d$, equal to the lattice size. Make the lattice bigger and the shortest logical string gets longer: the distance grows with the lattice's linear size $L$, while the qubit count grows with its area — $n\sim L^2$ qubits buy $d\sim L\propto \sqrt{n}$ — all with only local checks. That is the surface code's decisive advantage, and why it is the front-runner for real hardware — high tolerance to error, a flat nearest-neighbour layout, and a distance you scale just by adding qubits.

An $X$ error on one edge anticommutes with the two $Z$-stars at its endpoints, so it lights up the two adjacent vertex checks — two defects. A whole chain of $X$ errors lights up only its two endpoints: the checks in the interior of the chain each see two errors and stay silent. So the syndrome never shows you the error — it shows you the endpoints of error chains, in pairs. The decoder's job is to guess a chain that could have produced those endpoints. That is the problem of the next section.

The defects come in pairs, and any error chain joining two defects would reproduce them. Which chain actually happened? We cannot know — but under independent noise, a shorter chain is exponentially more likely than a longer one (each extra errored qubit costs a factor $p/(1-p)$). So the maximum-likelihood guess is the shortest set of chains that pairs up all the defects. Pairing up points to minimize total path length is a classic combinatorial problem: minimum-weight perfect matching (MWPM). Give every pair of defects a weight equal to the lattice distance between them, and ask for the perfect matching of least total weight.

Apply the correction along the matched paths and one of two things happens. The correction chain plus the true error chain together form closed loops (they share the same endpoints). If every loop is contractible — shrinkable to a point — it is a product of stabilizers and acts as the identity on the code space: success. But if the true error was long and the decoder paired the defects the other way around the lattice, the combined loop is non-contractible — it wraps the code — and that is a logical operator: a logical error. The decoder fails precisely when the error chain is long enough to fool it about which way to close the loop. Toggle errors below and watch the matching form; the “spanning chain” preset shows a chain long enough to flip the logical qubit:

Notice the structure the widget makes visible. A single error, or any short chain, is matched by a correction that cancels it exactly — the residual is nothing. Only when a chain spans more than half the lattice does the nearest matching go the wrong way and leave a loop around the torus. This is why distance matters: $d$ must exceed twice the longest likely error chain for correction to win. And it is why there is a threshold — a physical error rate $p_{\text{th}}$ below which long chains are so rare that a bigger lattice always helps, and above which errors are so dense that a bigger lattice only gives them more room to fail.

The lab implements the toric code — the surface code on a torus, chosen because its periodic boundary makes the matching perfectly clean: defects always pair with each other, with no boundary special-casing, so the decoder's correctness is easy to pin down. Data qubits live on the $2d^2$ edges of a $d\times d$ torus; the syndrome is the parity at each vertex. This is the heart of it — read the defects straight off the four incident edges:

1/// The Z-check syndrome: vertex (r,c) is lit (a "defect") when an odd number
2/// of its four incident edges carry an X error.
3fn syndrome(&self) -> Vec<(usize, usize)> {
4    let d = self.d;
5    let mut defects = Vec::new();
6    for r in 0..d {
7        for c in 0..d {
8            let mut parity = false;
9            parity ^= self.h[r][c]; // right edge out of (r,c)
10            parity ^= self.h[r][(c + d - 1) % d]; // left edge into (r,c)
11            parity ^= self.v[r][c]; // down edge out of (r,c)
12            parity ^= self.v[(r + d - 1) % d][c]; // up edge into (r,c)
13            if parity {
14                defects.push((r, c));
15            }
16        }
17    }
18    defects
19}

Exact minimum-weight perfect matching in general is Edmonds' blossom algorithm, which is intricate; since correctness matters more than speed here, the lab instead does an exhaustive branch-and-bound that is obviously exact and, thanks to an admissible lower bound, fast on the metric instances the code produces (30-plus defects resolve in milliseconds):

1/// Admissible lower bound on the cost to finish matching the unmatched defects:
2/// half the sum, over unmatched defects, of each one's nearest unmatched-
3/// neighbour weight. Since ½(nn(a)+nn(b)) ≤ dist(a,b) for every pair, it never
4/// overestimates — so pruning with it never discards the optimum.
5fn match_lb(dist: &[Vec<i64>], n: usize, matched: &[usize]) -> i64 {
6    let mut sum = 0i64;
7    for v in 0..n {
8        if matched[v] != usize::MAX {
9            continue;
10        }
11        let mut nearest = i64::MAX;
12        for w in 0..n {
13            if w != v && matched[w] == usize::MAX && dist[v][w] < nearest {
14                nearest = dist[v][w];
15            }
16        }
17        if nearest != i64::MAX {
18            sum += nearest;
19        }
20    }
21    sum / 2
22}
23
24/// Exact minimum-weight perfect matching by branch-and-bound: always match the
25/// lowest-indexed unmatched defect, try partners nearest-first, prune with
26/// `match_lb`.
27fn bnb(
28    dist: &[Vec<i64>],
29    n: usize,
30    matched: &mut Vec<usize>,
31    cur: i64,
32    best: &mut i64,
33    best_match: &mut Vec<usize>,
34) {
35    let i = match (0..n).find(|&k| matched[k] == usize::MAX) {
36        Some(x) => x,
37        None => {
38            if cur < *best {
39                *best = cur;
40                best_match.clone_from(matched);
41            }
42            return;
43        }
44    };
45    if cur + match_lb(dist, n, matched) >= *best {
46        return; // cannot beat the incumbent — prune
47    }
48    let mut cand: Vec<usize> = (i + 1..n).filter(|&j| matched[j] == usize::MAX).collect();
49    cand.sort_by_key(|&j| dist[i][j]);
50    for j in cand {
51        matched[i] = j;
52        matched[j] = i;
53        bnb(dist, n, matched, cur + dist[i][j], best, best_match);
54        matched[i] = usize::MAX;
55        matched[j] = usize::MAX;
56    }
57}

The decoder is not trusted on faith. A first referee pits the branch-and-bound matcher against an independent exact bitmask dynamic program on hundreds of random instances — identical optimal costs, every time. A second replays a battery of hand-built error patterns with known corrections and confirms the residual is trivial, while planted non-contractible loops correctly trip the logical-error detector. Then the decisive referee measures the threshold: for $d=3,5,7$ it Monte-Carlos the logical error rate across physical $p$, carrying a binomial one-$\sigma$ uncertainty on every point, and checks that the ordering of the curves flips across the crossing — below $p_{\text{th}}$ a bigger code protects better, above it a bigger code protects worse. Each ordering gap is a z-score and must clear $3\sigma$, so no pass can be a statistical fluke of unstated size. Sanity holds at the ends: zero logical failures at $p=0$, and a coin-flip rate within $3\sigma$ of exactly $0.5$ at $p=0.5$. Every number below is whatever your last cargo run --release produced:

One pair of numbers needs an honest reconciliation. The referee table pins the crossing between $p=0.06$ and $p=0.13$ and estimates it live above — the known value for this exact model is $10.3\%$ — while §11.5's history note quoted Fowler's $\sim 1\%$ for the very same code. Both are right, because they price different noise models. The lab measures the code-capacity threshold: data qubits fail independently with probability $p$, but the syndrome is read out perfectly, free of charge. In a real machine syndrome extraction is itself a circuit of faulty CNOTs and measurements — each round can lie, so it must be repeated $\sim d$ times and decoded in three dimensions (space $\times$ time), and every faulty two-qubit gate spreads errors onto fresh qubits. Charging honestly for all that machinery — circuit-level noise — costs roughly a factor of ten in threshold: that is Fowler et al.'s $\sim 1\%$. Same code, same matching decoder; the tenfold gap is purely how much of the correction machinery is allowed to fail.

Run it yourself with cargo run --release in Rust-QML/ch11-surface. The crossing — the panel above reports its live value from your own run — is the whole point of error correction made quantitative: it is the promise that if your hardware is good enough — below threshold — you can buy any logical fidelity you like simply by making the lattice bigger. What that promise costs, and how it composes into arbitrarily long computations, is Chapter 12.