Quantum Threshold Theorem

Every physical quantum computer is noisy: each gate misfires, each measurement lies a little, each idle qubit quietly decoheres. Left unchecked this is fatal — a circuit of $N$ operations, each correct with probability $1-p$ , succeeds with probability $(1-p)^N$ , which collapses toward zero the moment $Np\gtrsim 1$ . For a fixed error rate the reachable computation is bounded, and no algorithmic cleverness changes that. The quantum threshold theorem dissolves this apparent dead end. It states that there exists a constant critical error rate $p_{\mathrm{th}}$ — not a vanishing one, an ordinary number like a fraction of a percent — such that any device operating below it can be driven to simulate an ideal quantum circuit of any length, to any accuracy, with only a polylogarithmic blow-up in resources. The engine of the theorem is recursion. Encode each qubit in a small code that fixes one error; build fault-tolerant gadgets that manipulate the encoded qubit without letting a single fault metastasize into many; then encode the encoded qubits again, and again. One level converts a failure rate $p$ into $c\,p^2$ — quadratic, because a distance-3 code only surrenders when two independent faults conspire. Iterate $L$ times and the logical rate becomes $(cp)^{2^L}/c$ : it falls doubly exponentially in $L$ while the qubit count grows only singly exponentially. Accuracy outruns cost, and the crossover sits exactly at $p_{\mathrm{th}}=1/c$ . Recalling the noise model, discretization, and stabilizer machinery of the preceding QCI articles, this article asks what that single constant means, why it exists, and what it demands of hardware.

Key takeaways

If the physical error rate per operation is below a constant $p_{\mathrm{th}}$ , arbitrarily long and accurate quantum computation is possible with only polylogarithmic resource overhead.
The mechanism is concatenated coding: $L$ levels of recursive fault-tolerant encoding suppress the logical error rate doubly exponentially, $p_L=(cp)^{2^L}/c$ , provided $cp<1$ .
The threshold is a fixed point of $p\mapsto cp^2$ : below $p_{\mathrm{th}}=1/c$ the recursion drives errors to zero; at it nothing changes; above it encoding makes matters worse.
Fault tolerance is indispensable — gadgets must keep one fault to at most one error per block, or CNOT-driven error spreading defeats the code before the recursion can begin.
Numerical thresholds are model-dependent: concatenated bounds sit near $10^{-4}$ , the surface code reaches $\approx 1\%$ under depolarizing noise.
Key idea: below a constant threshold $p<p_{\mathrm{th}}$ , recursive fault-tolerant encoding crushes the logical error rate doubly exponentially in the number of levels while paying only singly-exponential overhead, so any ideal circuit is simulable to arbitrary accuracy with polylogarithmic blow-up.

The core insight

Below a constant threshold $p<p_{\mathrm{th}}$ , recursive (concatenated) fault-tolerant encoding suppresses the logical error rate doubly exponentially in the number of levels while costing only singly-exponential overhead, so any ideal circuit can be simulated to arbitrary accuracy with polylogarithmic resource blow-up.

Where this lives today

The threshold theorem is no longer a paper result; it is the daily target of every serious quantum-hardware program. Its most direct legacy is the "below threshold" experiment. In 2023–2024 Google's superconducting group reported a surface-code memory in which enlarging the code distance from 3 to 5 to 7 lowered the logical error rate per cycle — the first hardware demonstration of the theorem's core promise, with suppression factor $\Lambda\approx 2$ per two units of distance. Neutral-atom and trapped-ion platforms have since shown logical qubits, transversal gates, and repeated correction, each racing to push the physical two-qubit error below the $\sim 10^{-3}$ target a factor of ten under the surface-code threshold. The theorem also sets the scale of the machines that matter. Resource estimates for cryptographically relevant Shor factoring — millions of physical qubits, logical error rates near $10^{-15}$ , magic-state factories consuming much of the chip — flow directly from equations (5) and (6) applied to surface-code parameters. On the frontier, researchers attack the assumptions themselves: thresholds under correlated and non-Markovian noise, leakage handling, and high-rate quantum LDPC codes whose overhead scales far better than $7^L$ . The constant $p_{\mathrm{th}}$ has become the single number that decides whether a device is on the right side of history.

The physical picture

Picture error correction as a leaking boat you are bailing by hand. Each round of syndrome extraction scoops water out, but the very act of bailing — the gates and measurements that read the syndrome — splashes new water back in. If bailing removes errors faster than it introduces them, the water level stays bounded forever; if not, the boat swamps. The threshold is precisely the leak rate at which bailing breaks even. Concatenation is bailing with a hierarchy of ever-more-reliable buckets: each level is a bucket built from seven leakier ones, arranged so the assembly only fails when two parts fail at once. That "two at once" is the whole game — it turns a rate $p$ into $c\,p^2$ , and stacking the construction drives $c\,p^2$ to an astronomically small number after only a handful of levels.

Figure

The concatenation hierarchy for the Steane code: one logical qubit at level 2 is built from 7 level-1 blocks and 49 physical qubits (7^L qubits, single-exponential in L), while the error rate contracts p → c·p² → c(c·p²)² (double-exponential); with c ≈ 10⁴ the threshold is p_th = 1/c ≈ 10⁻⁴

The suppression only bites in one direction. Below the threshold each level makes the encoded qubit better and the improvement compounds; above it each level makes it worse, and that compounds instead. The dividing line is phase-transition sharp: the map $p\mapsto cp^2$ has an unstable fixed point at $p_{\mathrm{th}}=1/c$ , and which side you start on decides everything. The second figure plots the logical rate against level for three physical rates straddling the threshold — the fork that names the theorem.

Figure

Logical error rate p_L versus concatenation level L for c = 10⁴ so that p_th = 10⁻⁴: below threshold p = 10⁻⁵ plunges doubly-exponentially to about 10⁻³⁶ by L = 5, at threshold p = 10⁻⁴ stays pinned, and above threshold p = 10⁻³ climbs to 1 — the fork that defines p_th

The core equations

Start with the disease the theorem cures. If every one of the $N$ locations fails independently with probability $p$ , the computation is error-free only if none fail, and failure approaches certainty once the expected fault count $Np$ exceeds one.

P_{\mathrm{fail}}^{\mathrm{naive}} = 1 - (1-p)^{N} \xrightarrow{\,Np\gg 1\,} 1 \qquad (1)

where: $p$ — physical error probability per operation; $N$ — number of locations (gates, measurements, preparations, idle steps). Reading: for fixed $p$ the reachable circuit size is capped at $N\sim 1/p$ — raw hardware cannot run a long algorithm. The cure is to encode and correct. A distance-3 fault-tolerant construction fails logically only when two faults land in a way that defeats the code, so the leading term is quadratic and its coefficient counts those malignant pairs.

p_1 = c\,p^2 + O(p^3), \qquad c = \binom{A}{2}_{\!\mathrm{mal}} \qquad (2)

where: $p_1$ — logical failure probability of one encoded gadget; $A$ — total fault locations; $c$ — number of malignant fault pairs (those causing a logical error). Reading: shrinking $c$ with a better gadget directly raises the threshold. Because the encoded gadget is itself a "gate" that can be encoded again, the same reduction applies at every level, and iterating the quadratic map gives a closed form.

p_L = \frac{1}{c}\,\big(c\,p\big)^{2^{L}} \qquad (3)

where: $p_L$ — logical failure probability after $L$ levels; $L$ — number of concatenation levels. Reading: the exponent $2^L$ is the double-exponential engine — each level squares the closeness to zero, provided $cp<1$ . That proviso is the threshold: the recursion converges to zero if and only if the reduced rate $cp$ is below one, i.e. below the fixed point of the map.

p_{\mathrm{th}} = \frac{1}{c} \qquad (4)

where: $p_{\mathrm{th}}$ — fault-tolerance threshold for the chosen code, gadgets, and noise model. Reading: $p_{\mathrm{th}}$ is not a constant of nature but a property of the construction; proving thresholds means bounding $c$ . To reach a target accuracy one asks how deep to go. Demanding $N\,p_L\le\varepsilon$ and solving for $L$ gives a startlingly shallow requirement — a double logarithm of the problem size.

L^{*} = \left\lceil \log_2 \frac{\log(c\,N/\varepsilon)}{\log\!\big(1/(c\,p)\big)} \right\rceil = O\big(\log\log(N/\varepsilon)\big) \qquad (5)

where: $\varepsilon$ — target total failure probability; $L^{*}$ — minimum depth with $N\,p_{L^*}\le\varepsilon$ . Reading: $\log\log$ stays in single digits even for $N/\varepsilon=10^{100}$ . Each level multiplies the operation count by a fixed expansion factor $d_{\mathrm{enc}}$ , so cost grows single-exponentially in $L^{*}$ — which, because $L^{*}$ is a double logarithm, is only polylogarithmic in the problem size.

N_{\mathrm{phys}} = N\, d_{\mathrm{enc}}^{\,L^{*}} = O\!\Big(N\,\big(\log(N/\varepsilon)\big)^{\log_2 d_{\mathrm{enc}}}\Big) \qquad (6)

where: $d_{\mathrm{enc}}$ — physical-operation expansion factor per level ( $\sim 7$ qubits for the Steane code, more for gates); $N_{\mathrm{phys}}$ — total physical operations. Reading: polylog overhead is the headline the theorem exists to deliver. None of this closes without fault tolerance, and the reason is how errors move. A CNOT copies a bit-flip forward from control to target and a phase-flip backward from target to control, so one fault feeding a cascade of CNOTs can become many correlated errors in one block.

X_{\mathrm{ctrl}} \xrightarrow{\ \mathrm{CNOT}\ } X_{\mathrm{ctrl}}X_{\mathrm{tgt}}, \qquad Z_{\mathrm{tgt}} \xrightarrow{\ \mathrm{CNOT}\ } Z_{\mathrm{ctrl}}Z_{\mathrm{tgt}} \qquad (7)

where: $X,Z$ — Pauli bit-flip and phase-flip errors; $\mathrm{ctrl},\mathrm{tgt}$ — control and target. Reading: if a gadget lets this copying amplify one fault into two block errors, the distance-3 protection is gone and there is no threshold. The standard defence is transversality: apply the logical gate qubit-by-qubit so no two qubits within a block ever interact, and a fault on one can never spread to a second in the same block.

\overline{U} = U^{\otimes n} \quad (\text{no two qubits of a block interact}) \qquad (8)

where: $\overline{U}$ — logical gate; $n$ — physical qubits per block. Reading: transversal gates are automatically fault-tolerant, so the achievable transversal set governs the construction. Finally, the numbers experimentalists target — strongly dependent on code and noise model, meaningless without both.

p_{\mathrm{th}}^{\mathrm{surface}} \approx 1\% \ \ (\text{depolarizing}), \qquad p_{\mathrm{th}}^{\mathrm{conc.}\,[[7,1,3]]} \sim 10^{-4}\text{–}10^{-3} \qquad (9)

where: $[[7,1,3]]$ — the Steane code: 7 physical qubits, 1 logical, distance 3. Reading: the surface code's high threshold is why it dominates hardware roadmaps despite its qubit-hungry overhead.

Derivation AThe level-reduction lemma and the emergence of a sharp threshold

The goal is to show, from the single hypothesis of fault tolerance, that recursive encoding with a distance-3 code obeys the quadratic recursion $p_{k+1}\le c\,p_k^2$ , that iterating it gives a solution falling doubly exponentially below a sharp critical rate, and that the critical rate is exactly the reciprocal of the malignant-pair count. Model the noisy circuit as one in which each location fails independently with probability at most $p$ , and replace each logical operation by an extended rectangle (an exRec: a fault-tolerant gadget bracketed by error-correction steps).

Step 1. Call an exRec good if it contains at most one fault. Fault tolerance is precisely the property that a good exRec acts as an ideal logical operation followed by an error the next correction round removes — one fault gives at most one error per block, which a distance-3 code corrects. Why: this converts the abstract promise "fault-tolerant" into a countable event whose complement we can bound.

Step 2. Bound the probability that an exRec is bad (two or more faults). With $A$ fault locations, $\Pr[\text{bad}]\le\binom{A}{2}p^2$ , and restricting to pairs that defeat the code defines $c$ , so $\Pr[\text{bad}]\le c\,p^2$ . Why: this is the level-reduction lemma — a bad event needs two faults, so the rate squares.

Step 3. Identify the encoded failure rate. An encoded operation fails only if its exRec is bad, so $p_1\le c\,p^2$ . The construction is self-similar: an encoded gate at level $k$ plays exactly the role a physical gate played at level $k+1$ , so the same lemma applies at every level with the same $c$ . Why: self-similarity lets one lemma be iterated instead of re-proved level by level.

Step 4. Iterate. From $p_{k}\le c\,p_{k-1}^2$ , multiply by $c$ to get $(c p_k)\le (c p_{k-1})^2$ ; setting $q_k=c p_k$ gives $q_k\le q_{k-1}^2$ , solved by $q_L\le q_0^{2^L}$ with $q_0=cp$ . Undoing the substitution, $p_L\le (cp)^{2^L}/c$ . Why: the substitution $q=cp$ turns the recursion into repeated squaring, exposing the $2^L$ exponent.

Step 5. Read off the threshold. The solution converges to zero as $L\to\infty$ iff $q_0=cp<1$ , i.e. $p<1/c$ . Above it, $q_0>1$ and $q_L\to\infty$ , so $p_L$ saturates toward 1: adding levels actively harms. The crossover $p_{\mathrm{th}}=1/c$ is a sharp, unstable fixed point of $p\mapsto cp^2$ . Why: a single inequality on $cp$ decides whether encoding is a friend or an enemy.

Step 6. Convert accuracy into depth. Requiring $N\,p_L\le\varepsilon$ gives $2^L\ge \log(cN/\varepsilon)/\log(1/(cp))$ , hence $L^{*}=O(\log\log(N/\varepsilon))$ ; with the per-level cost factor $d_{\mathrm{enc}}$ this yields the polylogarithmic overhead $N_{\mathrm{phys}}=N\,d_{\mathrm{enc}}^{L^*}$ . Why: this is where "a threshold exists" becomes "large computation is efficient", completing the theorem. *Why: the map $f(p)=cp^2$ has fixed points at $0$ and $1/c$ ; since $f'(p)=2cp$ gives $f'(1/c)=2>1$ , the point $1/c$ is unstable and separates the basin flowing to $0$ from the basin flowing to $1$ — exactly the behaviour required of a threshold.*

Go deeper · Derivation B · 1 minEastin–Knill: why no code is transversally universal

Derivation BEastin–Knill: why no code is transversally universal

The goal is to explain the structural obstruction that forces the construction to include machinery beyond transversal gates — why the cheap, automatically-fault-tolerant transversal operations can never by themselves generate a universal gate set, so a non-Clifford gate must be supplied by a costlier route such as magic-state distillation. This is not a limitation of one code but a theorem about all of them, shaping the resource budget of every fault-tolerant architecture.

Step 1. Observe that the set of logical unitaries a given code can realize transversally is closed under composition and inverse, and hence forms a group $G$ . Why: closure makes $G$ a group, which is the object the no-go theorem constrains.

Step 2. Invoke Eastin–Knill: for any code that detects at least one error, this group $G$ is a finite (discrete) subgroup of the logical unitary group. A finite set of gates cannot densely fill the continuous group $\mathrm{SU}(2^k)$ . Why: universality requires a dense — hence infinite — reachable set, which a finite group cannot provide.

Step 3. Conclude that universal computation needs at least one gate outside $G$ . When $G$ is the Clifford group, the missing ingredient is a non-Clifford gate such as $T=\mathrm{diag}(1,e^{i\pi/4})$ , which by the theorem cannot be transversal on that code. Why: this concentrates all the difficulty of universality in a single non-Clifford operation.

Step 4. Supply that gate another way. Magic-state distillation prepares many noisy copies of a non-stabilizer state $|T\rangle$ , purifies them with transversal Clifford circuits, and injects them by gate teleportation — restoring universality while every physical operation stays below threshold. Why: distillation moves the hard step off-line into a resource state, keeping the on-line circuit transversal and fault-tolerant. *Why: the Steane $[[7,1,3]]$ code realizes $H$ , $S$ , and CNOT transversally — exactly the Clifford group generators, a finite group — while $T$ is not transversal on it, consistent with Eastin–Knill and confirming that distillation is required for the missing $T$ .*

Limiting cases

The behaviour of $p_L$ as the physical rate $p$ , depth $L$ , and code distance $d$ vary summarizes the whole theorem in one table.

Case	Result	Meaning
Deep below threshold	$p\ll p_{\mathrm{th}}\Rightarrow p_L\approx \tfrac1c(cp)^{2^L}$	double-exponential suppression; a few levels reach astronomically small logical error
At threshold	$p=p_{\mathrm{th}}=1/c\Rightarrow p_L=p\ \forall L$	encoding is exactly neutral; adding levels neither helps nor hurts — the fixed point defining $p_{\mathrm{th}}$
Above threshold	$p>p_{\mathrm{th}}\Rightarrow p_L\to 1$ as $L\to\infty$	encoding actively harms; more levels drive the logical error toward certainty as faults percolate
General distance- $d$ code	$p_L\sim p_{\mathrm{th}}\,(p/p_{\mathrm{th}})^{\lfloor(d+1)/2\rfloor^{L}}$	a distance- $d$ code corrects $t=\lfloor(d-1)/2\rfloor$ errors, so $t+1$ faults are needed to fail; a larger $d$ steepens the base exponent
Resource scaling	$N_{\mathrm{phys}}=O\big(N\,\mathrm{poly}(\log(N/\varepsilon))\big)$	below threshold the overhead is polylogarithmic — the efficiency headline of the theorem

Common trapQuoting a threshold as a universal number, or forgetting fault tolerance

Two mistakes recur. The first is saying "the threshold is $1\%$ " as if it were a physical constant. It is not: change the code, decoder, or noise model and the number moves by orders of magnitude — the rigorous concatenated $[[7,1,3]]$ threshold sits near $10^{-4}$ , the surface code reaches $\approx 1\%$ , and a bare unencoded scheme has no threshold at all. Always quote the construction and noise model with the number. The second mistake is imagining a good code is enough. A perfect distance-3 code wrapped in careless gadgets that let one CNOT fault spread into two errors per block has no threshold whatsoever — the level-reduction lemma fails at its first step because the "one fault → one block error" hypothesis is violated. Fault tolerance, not code distance alone, is the load-bearing assumption. And the suppression is double-exponential only strictly below $p_{\mathrm{th}}$ ; at or above it, concatenation is neutral or harmful.

Worked examples

1 · Concatenated Steane code below threshold (fully worked)

Take a construction with malignant-pair count $c=10^4$ , so $p_{\mathrm{th}}=1/c=10^{-4}$ , running on hardware at $p=10^{-5}$ (a factor 10 below threshold). How fast does the logical error fall with depth, and how many levels reach the $p_L\le 10^{-15}$ target typical of a large algorithm?

Step 1. Form the reduced rate. $cp=10^4\times 10^{-5}=0.1$ , below 1, so we are below threshold and the recursion converges. The closed form is $p_L=(cp)^{2^L}/c=(0.1)^{2^L}/10^4$ .

Step 2. Tabulate level by level. $L=1$ : $(0.1)^2/10^4=\mathbf{10^{-6}}$ . $L=2$ : $(0.1)^4/10^4=\mathbf{10^{-8}}$ . $L=3$ : $(0.1)^8/10^4=\mathbf{10^{-12}}$ . $L=4$ : $(0.1)^{16}/10^4=\mathbf{10^{-20}}$ . The exponent doubles $2\to4\to8\to16$ — the signature of double-exponential decay.

Step 3. Find the depth for the target. We need $(0.1)^{2^L}\le 10^{-11}$ , i.e. $2^L\ge 11$ , so the minimum integer level is $\mathbf{L^*=4}$ : three levels ( $10^{-12}$ ) fall just short, four ( $10^{-20}$ ) clear it with room to spare.

Step 4. Count the cost. With Steane's $\sim 7$ qubits per level, one logical qubit at $L^*=4$ uses on the order of $7^4=\mathbf{2401}$ physical qubits (gate overhead is larger but scales the same way). Four levels and a couple thousand physical qubits per logical qubit take a $10^{-5}$ device to a $10^{-20}$ logical error rate — the double-exponential payoff in numbers.

2 · Surface-code distance scaling (fully worked)

The surface code does not concatenate; instead one raises the code distance $d$ . A common empirical fit near threshold is $p_L\approx 0.1\,(p/p_{\mathrm{th}})^{(d+1)/2}$ . With $p_{\mathrm{th}}\approx 1\%$ and a physical rate $p=10^{-3}$ , what distance reaches a logical error of $10^{-15}$ , and how many physical qubits does that cost?

Step 1. Form the suppression ratio. $p/p_{\mathrm{th}}=10^{-3}/10^{-2}=0.1$ , so each increase of $d$ by 2 multiplies the logical rate by $p/p_{\mathrm{th}}=0.1$ — a tenfold suppression per distance step, the " $\Lambda\approx 10$ " of the experimental literature.

Step 2. Set up the target. Require $0.1\,(0.1)^{(d+1)/2}\le 10^{-15}$ , i.e. $(0.1)^{(d+1)/2}\le 10^{-14}$ , i.e. $(d+1)/2\ge 14$ , so $d+1\ge 28$ and $\mathbf{d=27}$ (odd distances only).

Step 3. Convert distance to qubits. A rotated surface-code patch of distance $d$ uses about $2d^2$ physical qubits, so $d=27$ costs $\approx 2\times 27^2=\mathbf{1458}$ physical qubits per logical qubit — the same order of magnitude as the concatenated estimate, reached differently.

Step 4. Read the lesson. Suppression is exponential in $d$ rather than double-exponential in $L$ , so the patch is large, but the high threshold means a modest $p/p_{\mathrm{th}}=0.1$ still gives clean tenfold steps. A distance-27 patch, about 1500 physical qubits per logical qubit, buys a $10^{-15}$ logical error rate from a $10^{-3}$ device — which is why megaqubit, not kiloqubit, machines are quoted for cryptographically relevant algorithms.

Physics of the portrait

The threshold theorem has no single author; it crystallized in a remarkable burst around 1996 out of several independent groups circling the same realization at once. If one name anchors the story it is Peter Shor, who first showed quantum information could be error-corrected at all and then that the correction could survive its own noisy implementation — the leap from a static code to a dynamic, fault-tolerant computation.

Origins · 1 minPeter Shor and how this was discovered

Peter Shor

1959– · fault-tolerant quantum computation

Peter Shor is the mathematician whose 1994 factoring algorithm made quantum computers worth building and whose 1995–1996 work made them worth believing in. Skeptics had argued that superpositions were too fragile to compute with — that decoherence would erase any advantage. Shor answered in two moves. In 1995 he published the first quantum error-correcting code, a nine-qubit construction protecting one logical qubit against an arbitrary single-qubit error, showing the no-cloning theorem does not forbid redundancy if one encodes into entanglement rather than copies. In 1996 he showed how to compute on encoded data with gadgets that do not let a single fault run wild — the birth of fault tolerance and the first threshold-type argument. Almost simultaneously, Aharonov and Ben-Or, Kitaev, and Knill–Laflamme–Zurek proved threshold theorems by concatenation from independent directions, and Preskill's group at Caltech turned the estimates into a physical program. A decade later Aliferis, Gottesman, and Preskill gave the sharp extended-rectangle proof for distance-3 codes underlying the modern statement. Shor's arc — abstract algorithm, first code, fault tolerance — is the spine it all hangs on.

History

1995

— Shor publishes the first quantum error-correcting code, protecting one qubit in nine

1996

— Shor gives the first scheme for fault-tolerant quantum computation

1996

— Aharonov–Ben-Or, Kitaev, and Knill–Laflamme–Zurek independently prove threshold theorems

1998

— Preskill sharpens the threshold estimate and catalogues its physical assumptions

2006

— Aliferis, Gottesman, and Preskill give the rigorous extended-rectangle proof for distance-3 codes

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniv. ed., §10.6 (fault tolerance and the threshold theorem) · Preskill, Lecture Notes for Physics 219, Ch. 7 (quantum error correction), threshold sections · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, AMS (2002), fault-tolerance chapter · Gottesman, An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation, arXiv:0904.2557 · Wilde, Quantum Information Theory, 2nd ed., Cambridge (2017). Every equation here is standard. Key relations include: the naive-failure form $1-(1-p)^N$ ; the quadratic level-reduction $p_{k+1}\le c\,p_k^2$ and its solution $p_L=(cp)^{2^L}/c$ ; the fixed point $p_{\mathrm{th}}=1/c$ with its instability $f'(1/c)=2$ ; the depth $L^*=O(\log\log(N/\varepsilon))$ and polylog overhead; the CNOT Pauli-propagation rules and transversality; and the worked tables (below threshold $10^{-5}\to 10^{-20}$ at $L=4$ for $c=10^4$ ; surface-code $d=27$ for $10^{-15}$ at $p/p_{\mathrm{th}}=0.1$ ). Threshold numbers — surface code $\approx 1\%$ depolarizing and concatenated $[[7,1,3]]$ $\sim 10^{-4}$ – $10^{-3}$ — are model-dependent estimates, not fundamental constants. Eastin–Knill is the structural no-go result motivating magic-state distillation.

Prerequisites. Quantum Error Model and Decoherence Channels · Discretization of Errors · Stabilizer Formalism · Knill–Laflamme Conditions · Syndrome Measurement and Decoding · Code Distance and Logical Operators. Leads to. Magic-State Distillation · Surface Codes · CSS Codes · Pauli Group and Clifford Group.

Ask the tutor: ask me to walk through the exRec malignant-pair count for a specific gadget, or to turn any target logical error rate into the concatenation depth and physical-qubit budget it demands.

Is the threshold a fundamental constant of nature like the speed of light?

No, and this is the single most important caveat. The threshold $p_{\mathrm{th}}=1/c$ is a property of a construction — a specific code, gadget set, decoder, and noise model — not of the universe. Change any of these and the number moves: the rigorous concatenated $[[7,1,3]]$ bound sits near $10^{-4}$ , optimized analyses of the same code reach the $10^{-3}$ range, and the surface code with matching decoding reaches about $1\%$ under depolarizing noise. Because $c$ counts malignant fault pairs, a cleaner gadget literally raises the threshold. A threshold quoted without its construction and noise model is not a physical statement.

Why does concatenation help below the threshold but hurt above it?

Because one level implements the map $p\mapsto cp^2$ , and where you land depends on which side of the fixed point $p_{\mathrm{th}}=1/c$ you start. Below it, $cp<1$ , so $cp^2<p$ : the encoded rate is smaller than the physical rate, and each further level shrinks it again. Above it, $cp>1$ , so $cp^2>p$ : encoding makes the rate larger, and each level makes it larger still, until it saturates near 1. At exactly $p=1/c$ the map returns $p$ unchanged. The fixed point is unstable — its derivative is 2 — so tiny departures grow, which is why the transition is sharp rather than gradual.

What is the difference between a good code and fault tolerance?

A code is a static object: a subspace that detects and corrects certain errors on stored qubits. Fault tolerance is a property of the procedures that manipulate encoded qubits — preparation, gates, measurement, and the correction itself. The distinction matters because those procedures are themselves noisy and can spread errors: a CNOT copies a bit-flip from control to target, so one fault early in a gadget can become several correlated errors in one block, overwhelming even a perfect code. A fault-tolerant gadget is designed so one fault produces at most one error per output block, keeping the code's protection intact. Without this, the level-reduction lemma fails at its first hypothesis and there is no threshold at all.

Why is the overhead polylogarithmic rather than exponential?

Two exponentials race, and the favourable one wins. Accuracy improves doubly exponentially in the levels — the exponent in $p_L=(cp)^{2^L}/c$ is $2^L$ — while cost grows only singly exponentially, $d_{\mathrm{enc}}^L$ . So any realistic target needs only $L^*=O(\log\log(N/\varepsilon))$ levels, which stays in single digits even for absurdly large computations. Feeding that tiny $L^*$ into the cost gives $d_{\mathrm{enc}}^{L^*}=(2^{L^*})^{\log_2 d_{\mathrm{enc}}}$ , and since $2^{L^*}$ is only about $\log(N/\varepsilon)$ , the whole thing is a fixed power of a logarithm — polylogarithmic.

Why can't we just use one big code instead of concatenating small ones?

You can — the surface code is exactly that, a single large code whose distance you raise instead of stacking levels. Both routes obey the same theorem and differ only in engineering. Concatenated distance-3 codes give the cleanest recursive proof and closed form, but demand long-range connectivity and have low thresholds. A single high-distance code like the surface code trades a large qubit overhead ( $\sim 2d^2$ per logical qubit) for strictly local 2D connectivity and a much higher threshold, which is why hardware favours it. The abstract statement is identical; only $p_{\mathrm{th}}$ and the overhead exponent change.

What assumptions could make a real device fall outside the theorem?

The proof leans on several physical hypotheses, and violating them badly can destroy the threshold. It assumes noise is independent or only short-range correlated in space and time; strongly non-Markovian baths or spatially correlated errors can defeat the malignant-pair counting. It assumes operations run in parallel, that fresh ancillas are continuously available to carry away entropy, and that classical syndrome processing keeps up. It also assumes errors stay within the qubit subspace, so leakage is a real threat. Much of modern research is about proving thresholds survive weaker versions of these assumptions.