Thresholds and Fault Tolerance

Start with the trap. Chapter 10's three-qubit code stores one logical bit in three physical ones and corrects any single flip by majority vote. If each physical qubit fails independently with probability $p$, the encoded bit fails only when two or more of the three fail:

For small $p$ this is $\approx 3p^2\ll p$: encoding helps. So why not stop here? Because (12.1) quietly assumes the qubits fail independently and that the majority vote is computed for free. Neither holds. The vote is a circuit of real gates, and a single faulty two-qubit gate touches both its qubits at once — one fault becomes two errors, in exactly the qubits the code assumed would fail alone. Worse, a $\mathrm{CNOT}$ copies a bit-flip from control to target and a phase-flip from target to control: errors don't just appear, they propagate.

This is the whole difficulty of the subject in one sentence. A construction is fault-tolerant if a single fault anywhere — in a data qubit, an ancilla, a gate, a measurement — produces at most one error per encoded block, so that a distance-$d$ code still corrects it. Get that property and (12.1) becomes honest: the effective per-block failure really is quadratic in a physical rate. Lose it and no amount of encoding converges. Everything below assumes the circuits have been made fault-tolerant in this sense; our subject is what the resulting recursion does.

If one layer of encoding turns $p$ into $f(p)$, do it again. Take each of the three physical qubits and encode it in three more; encode those in three more; $L$ levels deep. This is concatenation, a code inside a code. A level-$L$ logical qubit is a tree with $3^L$ physical qubits at its leaves:

Because each level is the same map applied to the level below, the logical error rate obeys a one-line recursion:

Everything now turns on the dynamics of iterating one function. Drag $p$ below and watch all six level-curves at once — the physical rate on the horizontal axis, the logical rate $p_L$ on the vertical:

Two things jump out. The curves all pass through a single point, and on either side of it they fan in opposite directions. That pivot is the whole story.

The pivot is a fixed point of the recursion: a rate that maps to itself, $f(p_{th})=p_{th}$. Solving it for our code,

(the other roots, $0$ and $1$, are the stable “perfect” and “dead” states). The value $p_{th}=\frac{1}{2}$ is this code's threshold. Below it, iterating $f$ drives $p_L\to 0$; above it, $p_L\to 1$. To see how fast, look near the perfect state, where $f(p)\approx 3p^2$, and keep only that leading term: the pure-quadratic model $g(p)=A{p}^2$, with $A=3$ for our code. One caution before trusting it: $g$ is a different map with a different threshold — its nonzero fixed point is $1/A=1/3$, not $f$'s $\frac{1}{2}$ — so $g$ models the collapse deep below threshold, not the location of the transition. For $g$, write $p_{th}=1/A$ and define $x=p/p_{th}$; then $x_L=x_{L-1}^2$ exactly, so

Read (12.4) carefully — it is the theorem in miniature. The exponent is $2^L$, so the error is suppressed doubly exponentially in the number of levels whenever $p<p_{th}$. To reach a target logical error $\epsilon$ you need only $L\sim \log \log (1/\epsilon )$ levels, i.e. $\mathrm{polylog}(1/\epsilon )$ physical qubits per logical one. That is the threshold theorem: if the physical error rate is below $p_{th}$, arbitrarily long quantum computation is possible with only polylogarithmic overhead. Above $p_{th}$, the very same formula blows up doubly exponentially — encoding accelerates the failure. There is no gentle middle: it is a phase transition.

A threshold for storage is not enough; we must also compute on encoded qubits without letting one fault cascade. The cleanest way is a transversal gate: apply the physical gate qubit-by-qubit across the block, the $i$-th physical qubit of one block interacting only with the $i$-th of another. A fault in one such gate can corrupt only one qubit per block — exactly the fault-tolerance property of §12.1. Transversal gates are the gold standard: they are fault-tolerant essentially for free.

So why not build the whole computer from them? Because of a hard no-go, the Eastin–Knill theorem (2009): for any code that detects errors, the set of transversal gates is finite, so it cannot be universal. Typically the transversal gates give you the entire Clifford group — the $H$, $S$, and $\mathrm{CNOT}$ of Chapters 2 and 5 — and, by the Gottesman–Knill theorem of Chapter 5, a circuit of only Clifford gates is efficiently classically simulable. To get any quantum advantage at all you need one more gate outside the Clifford group — the non-Clifford $T=\mathrm{diag}(1,e^{i\pi /4})$ — and that is precisely the gate transversality refuses to hand you. The missing ingredient must be manufactured another way.

The escape, due to Sergey Bravyi and Alexei Kitaev (2005), is to move the hard gate off-line. A $T$ gate can be applied to a logical qubit using only Clifford operations if you are also given a special ancilla — a magic state $|A⟩=(|0⟩+e^{i\pi /4}|1⟩)/\sqrt{2}$. The magic state is consumed to inject the gate. So the whole non-Clifford difficulty is reduced to one question: how do you make clean magic states, when everything you build them from is noisy?

You distil them. Feed many noisy copies, each carrying error $\epsilon$, into a small Clifford circuit that checks a stabilizer condition and outputs fewer, cleaner copies. The celebrated 15-to-1 protocol takes fifteen noisy magic states and produces one whose error is

The suppression is cubic for a counted reason. The protocol's checks are the parity checks of the classical [15,11,3] Hamming code, whose minimum distance is 3: no one- or two-error input pattern slips through undetected, and exactly 35 of the $\left(\genfrac{}{}{0ex}{}{15}{3}\right)=455$ three-error patterns do — the lab counts them by walking all $2^{15}=32,768$ patterns, and 35 is what it finds. Iterating rounds gives another fixed-point story. At leading order the distillation threshold solves $35{\epsilon }^3=\epsilon$, i.e. ${\epsilon }_{th}=1/\sqrt{35}\approx 0.169$; the enumerated map keeps every order in $\epsilon$ and its fixed point lands below that — the leading-order threshold is an overestimate, and the lab's panel reports both. Below threshold each round cubes the error, so on a log–log plot $\log {\epsilon }_{\text{out}}$ versus $\log {\epsilon }_{\text{in}}$ approaches a straight line of slope 3 — a slope the lab measures off the enumerated map, to better than $3\times 10^{-8}$.

It is tempting to read the threshold theorem as good news and stop. It is good news — but the honest scorecard is sobering. The polylog overhead is asymptotic; the constants are brutal. A useful logical qubit built on a surface code near a realistic threshold needs hundreds to thousands of physical qubits. Magic-state distillation is often the dominant cost: factories that churn out clean $T$ states can occupy the majority of the chip, each round consuming fifteen inputs for one output.

Concretely, current estimates put a cryptographically relevant Shor factorization (Chapter 8) at millions of physical qubits running for hours or days — orders of magnitude beyond today's few-hundred-qubit devices. This is not a wall of principle; the threshold theorem says the wall is not there. It is a wall of engineering: driving physical error rates well below $p_{th}$ and building the millions of qubits the constants demand. That gap — provably surmountable, presently enormous — is exactly why the next chapter asks a different question.

A lab whose subject is a one-line recursion has an occupational hazard: it is dangerously easy to grade a closed form against itself and report a triumphant zero. So the instruments here never take the polynomial on trust. The first is an actual decoder — majority votes running bottom-up over the $3^L$ leaves of a concatenation tree — and the exact logical rate comes from enumerating every one of the $2^{3^L}$ leaf patterns that decoder gets wrong (all 512 of them at level 2):

1/// Majority vote over three error flags: the block is wrong iff >= 2 of 3 are.
2fn majority3(a: bool, b: bool, c: bool) -> bool {
3    (a & b) | (b & c) | (a & c)
4}
5
6/// Decode a level-L concatenation tree bottom-up from its 3^L leaf error flags.
7/// Returns true iff the LOGICAL bit is wrong. No closed form appears here.
8fn decode_tree(leaves: &[bool], scratch: &mut Vec<bool>) -> bool {
9    scratch.clear();
10    scratch.extend_from_slice(leaves);
11    let mut len = scratch.len();
12    while len > 1 {
13        for k in 0..len / 3 {
14            scratch[k] = majority3(scratch[3 * k], scratch[3 * k + 1], scratch[3 * k + 2]);
15        }
16        len /= 3;
17    }
18    scratch[0]
19}
20
21// …
22
23/// Exact 3-qubit majority-vote logical error: fail iff >= 2 of 3 bits flip.
24fn f_majority(p: f64) -> f64 {
25    3.0 * p * p - 2.0 * p * p * p
26}

The second instrument answers the 15-to-1 question by counting rather than quoting. A pattern of $Z$ errors on the fifteen inputs is detected exactly when it fails a Hamming parity check, and an accepted pattern hurts the output exactly when its weight is odd — so walking all $2^{15}$ patterns yields the protocol's full weight spectrum, and the 35 of (12.5) falls out of it as a count rather than a quote:

1/// Syndrome of a Z-error pattern: XOR of the H columns the pattern selects.
2/// Zero syndrome means the protocol accepts the round.
3fn syndrome(pattern: u32, cols: &[u8]) -> u8 {
4    let mut s = 0u8;
5    for (i, &c) in cols.iter().enumerate() {
6        if (pattern >> i) & 1 == 1 {
7            s ^= c;
8        }
9    }
10    s
11}
12
13/// An accepted pattern is stabilizer-equivalent to the identity iff it lies in
14/// the even-weight subcode; odd weight means it acts as the logical Z, i.e. the
15/// distilled output carries an error.
16fn is_harmful(pattern: u32) -> bool {
17    pattern.count_ones() % 2 == 1
18}
19
20/// Exhaustive walk over all 2^15 Z-error patterns on the 15 inputs. Returns
21/// (accepted_by_weight, harmful_by_weight), each indexed by Hamming weight.
22fn distill_spectrum(cols: &[u8]) -> (Vec<u64>, Vec<u64>) {
23    let mut accepted = vec![0u64; N_MAGIC + 1];
24    let mut harmful = vec![0u64; N_MAGIC + 1];
25    for pattern in 0u32..(1u32 << N_MAGIC) {
26        if syndrome(pattern, cols) != 0 {
27            continue; // detected — the round is thrown away
28        }
29        let w = pattern.count_ones() as usize;
30        accepted[w] += 1;
31        if is_harmful(pattern) {
32            harmful[w] += 1;
33        }
34    }
35    (accepted, harmful)
36}

The lab runs its referees and writes them to JSON, which the panel below reads live. Each grades one code path against an independent other: the enumerated decoder against the recursion $f(p)$ (to $5\times 10^{-15}$ at level 2); a Monte-Carlo tree against both, in $\sigma$; the threshold as a bisected crossing of the two enumerated level curves (within $4\times 10^{-15}$ of the algebraic $\frac{1}{2}$) and again as a million-shot measured crossing with a genuine error bar; the multiplier $f^{\prime }(p_{th})$ differenced off the enumerated curve (repelling, $>1$); and, on the distillation side, the counted 35, the measured cubic coefficient and exponent, a sampled check of the exact acceptance and harm probabilities, and the cascade run on the exact map. Every number in the panel — thresholds, cascade, slope — is whatever your last cargo run --release produced.

Run it yourself with cargo run --release in Rust-QML/ch12-threshold. The two curves are the whole chapter: a family of level-curves pivoting on $p_{th}$, and an error that collapses cubically once you are below ${\epsilon }_{th}$.