The Problem of Errors

Classical error correction is almost insultingly simple. To protect a bit, write it three times — $0\to 000$, $1\to 111$ — send all three through the noisy channel, and on the far side take a majority vote. A single flipped bit is outvoted two-to-one and silently repaired. Try to lift this to a qubit and you hit three walls in a row, each looking fatal.

Wall 1 — no cloning. The very first step, “write it three times,” asks for a machine that takes $|\psi ⟩$ to $|\psi ⟩|\psi ⟩|\psi ⟩$. No such machine exists. The no-cloning theorem says there is no unitary $U$ with $U(|\psi ⟩|0⟩)=|\psi ⟩|\psi ⟩$ for every $|\psi ⟩$ — a one-line consequence of linearity (Exercise 1). Copying is out.

Wall 2 — measurement destroys. Majority voting needs you to look at the three copies and compare them. But reading a qubit collapses it: measure $\alpha |0⟩+\beta |1⟩$ and you get one classical bit, the amplitudes gone for good. The act of checking for an error would itself destroy the information you are trying to protect.

Wall 3 — errors are continuous. A classical bit flips or it does not — a discrete event you can count. A qubit error is any small unwanted unitary: a rotation $e^{-i\theta X/2}$ by an arbitrary tiny angle, a partial dephasing, a drift. There is a whole continuum of them, parametrized by real numbers. Even if you could somehow spot an error, how would you ever correct a continuum of them with a finite set of operations?

Every one of these walls is real. The genius of the theory — Shor and Steane, 1995–96 — is that each becomes, on inspection, exactly the resource the next step needs. Wall 1 forces us to store information in entanglement instead of copies (§10.2). Wall 2 is sidestepped by measuring an error syndrome rather than the data (§10.3). And Wall 3 — the deepest — collapses spectacularly: measuring the syndrome digitizes the continuous error, and fixing three discrete Pauli errors turns out to fix them all (§10.4).

Keep the spirit of the classical code — spread the information across three qubits — but drop the illegal part, the copying. The 3-qubit bit-flip code encodes

which looks superficially like triplication but is nothing of the kind. Three copies would be the product $|\psi {⟩}^{\otimes 3}=(\alpha |0⟩+\beta |1⟩{)}^{\otimes 3}$, a state with eight nonzero amplitudes — and no-cloning says we cannot make it. Equation (10.1) has only two. It is a highly entangled state: the two logical basis states $|0_L⟩=|000⟩$ and $|1_L⟩=|111⟩$ are spread over all three qubits at once, and the amplitudes $\alpha ,\beta$ live on the whole triple, not on any single qubit. No qubit alone carries a copy of $|\psi ⟩$ — trace any one out and you get noise. That is the loophole in no-cloning: we did not clone the state, we delocalized it.

Building (10.1) needs no forbidden operation, just two CNOTs from the data qubit onto two fresh ancillas prepared in $|0⟩$: $\text{CNOT}(0\to 1)$ then $\text{CNOT}(0\to 2)$. On $\alpha |0⟩+\beta |1⟩$ the first CNOT gives $\alpha |00⟩+\beta |11⟩$, the second spreads it to (10.1). The left half of the circuit below is exactly this; the right half is the measurement we build in §10.3.

Now Wall 2. We must detect an error without measuring $\alpha ,\beta$. The trick is to measure a relationship between qubits rather than any qubit's value. Consider the two observables

These are stabilizers in the sense of Chapter 5: both fix the code space, $S_1|{\psi }_L⟩=S_2|{\psi }_L⟩=|{\psi }_L⟩$, because $|000⟩$ and $|111⟩$ each have even parity on every adjacent pair. Crucially, each $S_i$ asks only “do these two qubits agree?” — a question whose answer is the same for $|000⟩$ and $|111⟩$, and therefore reveals nothing about $\alpha$ versus $\beta$. Measuring $S_1$ and $S_2$ yields two bits, the syndrome $(s_1,s_2)$, while leaving the logical superposition perfectly intact.

Work out what a single bit-flip does. An $X$ on qubit 1 sends $\alpha |000⟩+\beta |111⟩$ to $\alpha |010⟩+\beta |101⟩$: now qubits 0 and 1 disagree and qubits 1 and 2 disagree, so $(s_1,s_2)=(1,1)$. Each error location leaves its own fingerprint:

The four syndromes are distinct, so the decoder reads $(s_1,s_2)$, looks up the offending qubit, and applies an $X$ there to undo it. This is the quantum version of majority vote — but performed on parities, not values. Inject an error and watch the syndrome light up:

The panel is entirely deterministic — the syndrome is a lookup, not a coin flip. Two facts deserve emphasis. First, the correction is itself a Pauli $X$, its own inverse, so “undoing” the error is a single clean gate. Second, and this is the whole point of Wall 2: nothing in $(s_1,s_2)$ depended on $\alpha$ or $\beta$. We learned where the error was without learning what we were protecting.

Wall 3 is the deep one, and knocking it down is the single most important idea in this chapter. Real errors are continuous: instead of a clean $X$, qubit 0 suffers a small rotation

a coherent superposition of “no error” and “a full bit-flip,” for some arbitrary real $\theta$. Applied to $|{\psi }_L⟩$ it produces the entangled mess $\cos \frac{\theta }{2}|{\psi }_L⟩-i\sin \frac{\theta }{2}{X}_0|{\psi }_L⟩$— the state is now a continuum away from any codeword. But watch what the syndrome measurement of §10.3 does to it. The first term lives in the $(0,0)$ syndrome sector; the second, carrying $X_0$, lives in the $(1,0)$ sector. Measuring $(s_1,s_2)$ therefore projects onto one or the other:

The continuous parameter $\theta$ survived only as the probability of each branch. The state that emerges is, in both cases, exactly $|{\psi }_L⟩$ after correction — fidelity 1, no residual $\theta$-dependence at all. The measurement digitized the error: a continuum rounded to one of two discrete outcomes, each of which we know how to fix. This is why a finite code can defeat an infinite family of errors.

The argument generalizes completely. Any single-qubit error, even a non-unitary one from Chapter 4, can be expanded in the Pauli basis $E=c_{I}I+c_{X}X+c_{Y}Y+c_{Z}Z$. Syndrome measurement collapses this sum onto one Pauli term; so a code that corrects each of $X$, $Y$, and $Z$ on every qubit corrects any single-qubit error whatsoever. Discretize the enemy, and a handful of corrections suffices. (Our 3-qubit code only handles the $X$ part — hence the $e^{-i\theta X/2}$ error above; §10.5 explains the gap and Chapter 11 closes it.)

The bit-flip code is blind to a $Z$ error: since $Z$ commutes with both stabilizers $Z_0{Z}_1$ and $Z_1{Z}_2$, a phase-flip leaves the syndrome at $(0,0)$ and sails through undetected — yet $Z$ flips the relative phase, turning $\alpha |0_L⟩+\beta |1_L⟩$ into $\alpha |0_L⟩-\beta |1_L⟩$. To catch phase errors we simply rotate the whole problem into the $|\pm ⟩$ basis, where a $Z$ error is a bit-flip. Conjugating everything by Hadamards gives the phase-flip code:

built by the same two CNOTs followed by an $H$ on all three qubits, and decoded by the identical syndrome table (10.3) with $Z$ corrections in place of $X$ (Exercise 4). It is the bit-flip code seen in a mirror — literally its Hadamard conjugate, since $HXH=Z$ and $HZH=X$. The lab verifies both codes with one piece of machinery.

And here is the catch that drives the rest of Part III. The bit-flip code fixes $X$ but not $Z$; the phase-flip code fixes $Z$ but not $X$. Neither fixes both, and a general error has both parts. Three qubits buy you exactly one kind of protection. By the digitization argument, correcting a truly arbitrary single-qubit error requires catching $X$, $Y$, and $Z$ at once — and that, as Shor first saw, needs the two codes nested together, at a cost of nine qubits. That is the doorway to Chapter 11.

The lab is a fresh 3-qubit state-vector simulator — eight amplitudes, moved by hand — with encode, syndrome measurement, and correction for both codes. Encoding is two CNOTs (plus a layer of Hadamards for the phase-flip variant of §10.5), and it is worth seeing in code that this is entanglement, not copying:

1/// Encode a|0> + b|1> into the chosen 3-qubit code. Bit-flip:
2/// a|000> + b|111> via CNOT(0->1), CNOT(0->2). Phase-flip: additionally H on
3/// all three qubits -> a|+++> + b|--->.
4fn encode(kind: Kind, a: C, b: C) -> State {
5    let mut s = State::input(a, b);
6    s.cnot(0, 1);
7    s.cnot(0, 2);
8    if kind == Kind::PhaseFlip {
9        for q in 0..N {
10            s.apply_1q(&g_h(), q);
11        }
12    }
13    s
14}
15
16/// CNOT(ctrl -> tgt): flip tgt on the branches where ctrl is set.
17fn cnot(&mut self, ctrl: usize, tgt: usize) {
18    let cbit = 1usize << ctrl;
19    let tbit = 1usize << tgt;
20    for i in 0..DIM {
21        if i & cbit != 0 && i & tbit == 0 {
22            self.amps.swap(i, i | tbit);
23        }
24    }
25}

Syndrome measurement is an honest projective measurement onto the $\pm 1$ eigenspaces of a stabilizer, $P_{\pm }=(I\pm S)/2$ — which is why the logical amplitudes survive it — followed by the lookup table:

1/// Project onto the +/-1 eigenspaces of a single stabilizer S.
2/// Returns [(prob_plus, |plus>), (prob_minus, |minus>)] with the branch states
3/// renormalized (or left zero if the branch has vanishing probability).
4fn project(psi: &State, stab: &[(usize, Pauli)]) -> [(f64, State); 2] {
5    let s_psi = psi.pauli_string(stab);
6    let (mut plus, pp) = combine(psi, &s_psi, 1.0);
7    let (mut minus, pm) = combine(psi, &s_psi, -1.0);
8    // …
9    [(pp, plus), (pm, minus)]
10}
11
12/// Map a syndrome (s1, s2) to the qubit to correct: 00 -> none, 10 -> q0,
13/// 11 -> q1, 01 -> q2.
14fn infer_qubit(s1: u8, s2: u8) -> Option<usize> {
15    match (s1, s2) {
16        (0, 0) => None,
17        (1, 0) => Some(0),
18        (1, 1) => Some(1),
19        (0, 1) => Some(2),
20        _ => unreachable!(),
21    }
22}

The sharpest referee is the digitization test. We apply a continuous rotation error, measure the syndrome, correct each branch, and confirm the branch-averaged fidelity is 1 to machine precision — independent of the rotation angle:

1// --- Referees 5-7: DIGITIZATION OF ERRORS (the conceptual heart) -------
2// Apply the CONTINUOUS rotation error e^{-i theta X/2} on a data qubit.
3// Syndrome measurement projects the continuum onto {no error, X error};
4// BOTH branches, after correction, return the exact logical state. So the
5// syndrome-averaged post-correction fidelity is 1 for EVERY theta.
6// …
7for &theta in &thetas {
8    // the chart follows the error on q0; the referees sweep all three qubits
9    let mut chart_uncorr = 1.0;
10    let mut chart_corr = 1.0;
11    for q in 0..N {
12        let mut errored = psi_l.clone();
13        errored.apply_1q(&g_rx(theta), q);
14
15        // uncorrected fidelity to the clean logical state
16        let f_unc = fidelity(&psi_l, &errored);
17        // …
18
19        // syndrome-averaged post-correction fidelity
20        let branches = syndrome_and_correct(Kind::BitFlip, &errored);
21        let mut avg_f = 0.0;
22        let mut ptot = 0.0;
23        for b in &branches {
24            avg_f += b.prob * fidelity(&psi_l, &b.corrected);
25            ptot += b.prob;
26        }
27        avg_f /= ptot.max(1e-300);
28        worst_digit = worst_digit.max((avg_f - 1.0).abs());
29        if q == 0 {
30            chart_uncorr = f_unc;
31            chart_corr = avg_f;
32        }
33        // …
34    }
35    digitization.push(DigitPoint { theta, uncorrected: chart_uncorr, corrected: chart_corr });
36}

The referees run and write their results to JSON, which the panel reads live — nothing here is hardcoded. Single $X$ and $Z$ errors are corrected to fidelity 1; the continuous rotation is digitized away (its computed corrected fidelity stays within the referee's $2\times 10^{-15}$ tolerance of 1 across the whole $\theta$ sweep); and the encoded logical error rate matches the closed form $3p^2-2p^3$ both by exact enumeration and by Monte Carlo. That last curve carries the chapter's honest scorecard:

Read the crossover carefully. For a per-qubit error rate $p<\frac{1}{2}$ the encoded rate $3p^2-2p^3$ sits below the bare rate $p$: encoding helps, and helps quadratically when $p$ is small. But above $p=\frac{1}{2}$ the code makes things worse — three bad qubits outvote the truth. That there is a break-even point at all is the seed of the threshold theorem, the result that ultimately says large-scale quantum computing is possible, which Chapter 12 proves. Run it yourself with cargo run --release in Rust-QML/ch10-codes.