The Threshold Theorem

Imagine trying to build a working computer out of parts that occasionally malfunction. Even checking whether a part has failed can itself go wrong. This sounds hopeless, yet classical computers manage it. They rely on components so reliable that failures are astronomically rare. Quantum computers face a much harsher version of this problem. Qubits decohere in microseconds to milliseconds. Gates are never perfectly calibrated. Even the act of measuring a qubit to check for errors can introduce new errors. For decades, skeptics argued that this made large-scale quantum computation a physical impossibility. It was not merely an engineering challenge, they claimed. The threshold theorem is the result that overturned this pessimism. It says that if the physical error rate per gate or per time step is below some constant threshold value, then Fault-Tolerant Quantum Computing techniques can suppress the logical error rate to any desired level. This uses resources that scale only polylogarithmically with the size and length of the computation. In other words, arbitrarily long and arbitrarily large quantum computations are possible in principle. Hardware must clear a fixed, achievable bar — not an ever-receding one. This matters enormously for real systems. It converts quantum error correction from a theoretical curiosity into an engineering roadmap. Hardware teams at Google, IBM, Quantinuum, and elsewhere explicitly report error rates as fractions of estimated thresholds. Crossing that line is the difference between a quantum computer that gets worse as you scale it and one that gets better. The threshold theorem is the mathematical guarantee that scaling up is not just possible. It guarantees that scaling up eventually helps. This article builds the theorem from the ground up. We show how concatenated coding recursively suppresses errors. We explain why the recursion converges below a threshold. We cover the precise resource-overhead bound. We also cover the assumptions on which the whole argument rests: a noise model, independence, and sufficient parallel resources. We end by connecting the theorem to where quantum hardware sits today. This sets up the transition into the NISQ Era and beyond.

Key takeaways

The threshold theorem: below a critical physical error rate $p_{th}$ , concatenated fault-tolerant encoding drives logical error rates to zero as you add more encoding levels.
The mechanism is recursive: encode qubits in a code, encode that code's qubits again, and errors get squared away at each level provided $p < p_{th}$ .
The overhead to reach target logical error rate $\varepsilon$ is polylogarithmic in $1/\varepsilon$ and in circuit size — not exponential.
The proof rests on a level-reduction argument: if fault-tolerant gadgets are used, one level of encoding maps physical error rate $p$ to logical error rate $\approx (p/p_{th})^2 \cdot p_{th}$ .
Real thresholds depend on the code and noise model: roughly $10^{-4}$ for early concatenated schemes, up to about $1\%$ for the surface code under realistic noise.
The theorem assumes independent, local, stochastic noise and enough parallel resources; correlated or non-Markovian noise can violate its premises.

The core insight

Below a critical error rate, encoding a quantum computer in a hierarchy of nested error-correcting codes suppresses errors faster than the overhead required to do so, so scaling up eventually makes computation more reliable, not less.

The idea

Quantum error correction alone is not enough to guarantee scalable computation. A single application of a quantum error-correcting code, such as the seven-qubit Steane code, reduces the probability that an error survives, but the gates used to implement the correction itself are also noisy. If those gates fail often enough, error correction can make things worse rather than better — the "cure" introduces as much damage as the disease. Fault-tolerant circuit constructions are designed so that a single fault, occurring anywhere in one time step of a fault-tolerant gadget, causes at most one error in each output block, preventing errors from cascading uncontrollably within a single encoded operation. The threshold theorem takes this fault-tolerant machinery and asks: if you nest it recursively — encoding the physical qubits in a code, then treating each encoded qubit as itself needing protection and encoding it again, and again — does the logical error rate go to zero, or does it saturate? The answer is that there exists a threshold error rate $p_{th}$ , a property of the code, the fault-tolerant gadgets, and the noise model, such that:

p < p_{th} \implies \text{logical error rate} \to 0 \text{ as the number of concatenation levels} \to \infty.

Concretely, using concatenated codes — the same code applied recursively, level within level, like a fractal — the effective error rate after $L$ levels of concatenation behaves like

p_L \approx p_{th} \left(\frac{p}{p_{th}}\right)^{2^L}.

This double-exponential suppression in $L$ is the heart of the theorem: each additional level of encoding squares the ratio $p/p_{th}$ , and since that ratio is less than 1 whenever $p < p_{th}$ , repeated squaring drives it to zero extremely fast. The overhead — number of physical qubits and gates per logical qubit — grows only polynomially in $L$ , while the achievable error rate shrinks doubly exponentially in $L$ . Converting this into "cost to reach target error $\varepsilon$ ", the resource overhead scales as $\mathrm{poly}(\log(1/\varepsilon))$ , which is the origin of the phrase "polylogarithmic overhead" in the theorem's statement.

How it works

The proof of the threshold theorem is built from a single recursive unit called level reduction, applied to a base fault-tolerant gadget set. We walk through the construction layer by layer.

Step 1 — the base fault-tolerant gadgets. Fix a quantum error-correcting code, say one encoding $k$ logical qubits into $n$ physical qubits and correcting $t$ errors (for concreteness, think of the 7-qubit Steane code, $n=7$ , $t=1$ ). Fault-tolerant procedures exist for: preparing encoded ancilla states, performing encoded gates from a universal gate set, and performing syndrome extraction and correction — all built so that a single physical fault anywhere in the gadget produces at most one erroneous qubit in each output code block. This "one fault, one error" property is what prevents an error from spreading to multiple qubits inside one code block during one gadget's execution.

Step 2 — level-1 analysis. Consider a logical circuit built from these gadgets, encoded once (level 1). A logical error occurs on a given code block only if at least two faults occur among the gadgets that touch that block within the time before the next correction step — because the code corrects any single fault, by design. If each physical location fails independently with probability $p$ , and there are at most $c$ locations (a constant depending on the code and gadget set) that can cause a failure in a given block, then a standard union bound gives

p_1 \le c \binom{c}{2} p^2 =: A\,p^2

for some constant $A$ determined entirely by the code and the gadgets (not by the size of the overall computation). This is the crucial structural fact: the level-1 logical error rate is quadratic in the physical error rate, because it takes two independent faults to defeat a code that corrects one error.

Step 3 — recursive concatenation. Now repeat the construction one level up: treat each level-1 logical qubit as a "physical" qubit for a second copy of the same code, and encode again. The fault-tolerant gadgets for level 2 are built out of level-1 encoded gadgets. By the same counting argument, the level-2 logical error rate satisfies

p_2 \le A\,p_1^2 \le A \cdot (A p^2)^2 = A^3 p^4.

In general, after $L$ levels,

p_L \le A\, (Ap)^{2^L} / A = \frac{1}{A}\left(Ap\right)^{2^L}.

Define the threshold as $p_{th} := 1/A$ . Then whenever $p < p_{th}$ , the quantity $Ap < 1$ , and $(Ap)^{2^L} \to 0$ doubly exponentially fast as $L \to \infty$ . Rewriting in the earlier form,

p_L = p_{th}\left(\frac{p}{p_{th}}\right)^{2^L}.

Step 4 — overhead accounting. Each level of concatenation multiplies the number of physical qubits per logical qubit by $n$ (the code's block size), and multiplies circuit depth per logical gate by some constant factor $d$ from the gadget's time steps. After $L$ levels, the overhead is $n^L$ qubits and $d^L$ time per original logical qubit and gate — exponential in $L$ . But since $p_L$ falls doubly exponentially in $L$ , reaching a target error rate $\varepsilon$ requires only

L = O\!\left(\log \log \frac{1}{\varepsilon}\right)

levels, so the overhead $n^L = n^{O(\log\log(1/\varepsilon))}$ turns out to be $\mathrm{poly}(\log(1/\varepsilon))$ — polylogarithmic, not exponential, in the desired precision. This is the calculation that gives the theorem its name and its practical bite. ```text FUNCTION FaultTolerantCircuit(LogicalCircuit C, PhysicalErrorRate p, TargetError ε):

# Step 0: determine base gadget threshold p_th and per-level constant A = 1/p_th A ← EstimateGadgetConstant(Code) p_th ← 1 / A IF p ≥ p_th: RETURN "FAILURE: physical error rate above threshold; concatenation does not help"

# Step 1: choose number of concatenation levels L so p_L ≤ ε L ← 0 p_L ← p WHILE p_L > ε: p_L ← A p_L^2 # level-reduction recursion: p_{l+1} = A p_l^2 L ← L + 1

# Step 2: build the concatenated encoding EncodedCircuit ← C FOR level = 1 TO L: EncodedCircuit ← EncodeWithFaultTolerantGadgets(EncodedCircuit, Code)

# replaces every logical qubit with an n-qubit code block,

# replaces every gate with a fault-tolerant gadget,

# inserts syndrome extraction + correction after each gadget RETURN EncodedCircuit, L, p_L # logical error rate ≤ ε, achieved with L levels ``` The key subroutine `EncodeWithFaultTolerantGadgets` is where fault tolerance is enforced: it must use transversal gates (applying the same physical gate independently to corresponding qubits across code blocks) wherever possible, since transversal gates cannot propagate a single fault into two errors within one block. Where transversal implementation is not directly available for a universal gate set, techniques such as magic-state distillation or gate teleportation are used, themselves built from the same fault-tolerant primitives — this is a real complication in practice but does not change the asymptotic argument.

Figure

Concatenated encoding: one logical qubit becomes

n^L

physical qubits after

L

levels

Complexity & correctness

Overhead (space and time). After $L$ concatenation levels, one logical qubit is represented by $n^L$ physical qubits, and one logical time step corresponds to $d^L$ physical time steps for constants $n, d$ set by the code and gadgets. To hit target logical error rate $\varepsilon$ per logical gate, we showed $L = O(\log\log(1/\varepsilon))$ suffices, since $p_L$ decreases doubly exponentially in $L$ . Hence:

\text{qubits per logical qubit} = n^L = n^{O(\log\log(1/\varepsilon))} = \mathrm{poly}\!\left(\log \frac{1}{\varepsilon}\right),

and similarly time overhead per logical gate is polylogarithmic in $1/\varepsilon$ . If the overall circuit has $N$ logical gates and we want the entire computation to succeed with constant probability, a union bound over gates forces $\varepsilon = O(1/N)$ , giving total overhead

\mathrm{poly}(\log N)

per gate — the celebrated polylogarithmic-overhead scaling. This is why the theorem is stated as: arbitrarily long computations are possible with only polylogarithmic overhead, provided $p < p_{th}$ .

Correctness (why the recursion is valid, not just numerically suggestive). The proof hinges on an invariant maintained across levels: at every level $l$ , the fault-tolerant gadgets satisfy the same "one fault causes at most one error per block" property that held at level 0, because level- $(l{+}1)$ gadgets are built by transversally applying level- $l$ gadgets, and transversality guarantees that a single faulty level- $l$ block can corrupt at most one output level- $(l{+}1)$ qubit position. This is an inductive argument: assuming the property holds at level $l$ (fault-tolerance of level- $l$ gadgets, with effective error rate $p_l$ ), one shows it holds at level $l{+}1$ with error rate $p_{l+1} \le A p_l^2$ , by exactly the same union-bound counting used to derive $p_1 \le A p^2$ from bare physical gates. The base case is the physical-level fault-tolerant gadget construction itself, verified by direct (finite, checkable) enumeration of fault paths. The recursion $p_{l+1} = A p_l^2$ has a fixed point at $p = 0$ and $p = 1/A = p_{th}$ ; it is a standard exercise in dynamical systems that this map converges to $0$ under iteration whenever the initial value is below the unstable fixed point $p_{th}$ , and diverges (saturates near $1$ , meaningless as a probability but signaling failure of the perturbative argument) above it. This is precisely why $p_{th}$ is called a threshold: it is a genuine phase-transition-like point separating "errors shrink to zero" from "errors do not shrink."

Honest caveats. The constant $A$ (equivalently $p_{th} = 1/A$ ) is derived from a union bound over fault paths, which is typically not tight — actual thresholds computed via more careful combinatorial or numerical methods (mapping the decoding problem to a statistical-mechanics model, for instance) are usually higher than naive union-bound estimates. Second, the theorem as proven assumes:

Local, stochastic, independent (or weakly correlated) noise — each gate fails independently with probability $p$ , uncorrelated across locations and time. Strongly correlated or non-Markovian noise can break the argument.
Sufficient parallel resources — enough physical qubits and classical control to run syndrome extraction and correction in parallel across the whole encoded circuit, and fast, reliable classical computation to decode syndromes in real time.
A universal, fault-tolerant gate set at the base level, which in practice requires non-transversal constructions like magic-state distillation for gates such as the $T$ -gate, adding additional (still polylogarithmic) overhead.

None of these assumptions are free lunches for real hardware, but they are the honest premises under which the theorem — as a mathematical statement — is a theorem, not a conjecture.

Worked example

Let's trace concrete numbers using the level-reduction recursion $p_{l+1} = A p_l^2$ , taking illustrative constants in the ballpark of concatenated Steane-code estimates, $A \approx 10^4$ (so $p_{th} = 10^{-4}$ ), and a physical error rate $p = 10^{-5}$ , aiming for a target logical error rate of $\varepsilon = 10^{-15}$ (a level of reliability relevant for a long Shor's-algorithm run).

Level $l$	Formula	$p_l$
0 (physical)	given	$1 \times 10^{-5}$
1	$A p_0^2$	$10^4 \cdot (10^{-5})^2 = 1 \times 10^{-6}$
2	$A p_1^2$	$10^4 \cdot (10^{-6})^2 = 1 \times 10^{-8}$
3	$A p_2^2$	$10^4 \cdot (10^{-8})^2 = 1 \times 10^{-12}$
4	$A p_3^2$	$10^4 \cdot (10^{-12})^2 = 1 \times 10^{-20}$

Notice level 4 already overshoots the target $10^{-15}$ — so $L = 4$ levels suffice, in fact with margin to spare (level 3 alone, at $10^{-12}$ , is not quite enough, confirming $L=4$ is the correct minimal choice here). This matches the predicted $L = O(\log\log(1/\varepsilon))$ : reaching fifteen orders of magnitude of suppression took only four levels of encoding, not fifteen. Now the overhead. With the Steane code, $n = 7$ qubits per block, and suppose each fault-tolerant gadget takes about $d = 6$ physical time steps per logical time step (a rough illustrative figure). Then:

Level $L$	Qubits per logical qubit ( $7^L$ )	Time steps per logical gate ( $6^L$ )	Achieved $p_L$
1	7	6	$10^{-6}$
2	49	36	$10^{-8}$
3	343	216	$10^{-12}$
4	2,401	1,296	$10^{-20}$

So to go from a bare physical error rate of $10^{-5}$ down to an effective logical error rate of $10^{-20}$ — fifteen orders of magnitude better than target — costs a factor of about 2,401 in qubits and about 1,296 in time per logical operation. That factor is large in absolute terms but it is fixed, independent of how long the overall computation runs; running a computation with $N = 10^{12}$ gates at logical error rate $10^{-20}$ per gate gives total failure probability $\sim 10^{-8}$ , still comfortably below 1 — exactly the polylogarithmic-overhead promise made good. Contrast this with what happens if $p$ is above threshold, say $p = 2\times 10^{-4} > p_{th} = 10^{-4}$ : then $p_1 = A p_0^2 = 10^4 \cdot 4\times10^{-8} = 4\times10^{-4} > p_0$ . The first level of encoding made things worse, and every subsequent level makes it worse still, diverging away from zero. This is the sharp, qualitative difference the threshold marks: the same machinery either helps unconditionally and without limit, or hurts unconditionally, depending purely on which side of $p_{th}$ the hardware sits.

Common pitfalls & traps

Pitfall	Why it happens	Fix / correct view
Treating $p_{th}$ as a universal constant	Threshold values depend heavily on code, gadget design, and noise model	Always cite threshold relative to a specific code + noise assumption (e.g. "1% under circuit-level depolarizing noise for the surface code")
Confusing physical error rate with logical error rate in reported hardware numbers	Marketing or papers sometimes blur "gate fidelity" with "logical qubit error rate"	Check whether the number is per-physical-gate or per-logical-operation; these differ by orders of magnitude post-encoding
Assuming threshold theorem guarantees today's hardware works	The theorem is an asymptotic, idealized-noise-model statement	Real devices must estimate their actual noise model and confirm it is below threshold for that model, which is a nontrivial characterization problem
Ignoring the classical decoding time	Syndrome decoding must complete before the next round of correction, or errors accumulate	Fast, often hardware-accelerated decoders (e.g. for the surface code) are a real engineering bottleneck, not a footnote
Assuming independence of noise across qubits and time holds automatically	Crosstalk, leakage, and 1/f noise create correlations that violate the theorem's premises	Correlated-noise thresholds are a distinct and generally harder theoretical and experimental question
Believing more concatenation levels are always better in practice	Overhead grows exponentially in $L$ even though error rate falls doubly-exponentially	Choose $L$ just large enough for the target $\varepsilon$ ; excess levels waste qubits and time for no benefit

Pioneers & history

The threshold theorem emerged from the convergence of fault-tolerant circuit design and concatenated coding theory in the mid-1990s, shortly after Shor and Steane introduced the first quantum error-correcting codes. Multiple groups — Aharonov and Ben-Or; Knill, Laflamme, and Zurek; Kitaev — independently proved versions of the theorem around 1996–1998, using variants of the level-reduction argument presented here.

Origins · 1 minDorit Aharonov and how this was discovered

Dorit Aharonov

born 1970 · Hebrew University of Jerusalem; co-proved fault-tolerance thresholds for quantum computation with independent noise, and later contributed foundational results on quantum algorithms and Hamiltonian complexity

History

1995

— Peter Shor introduces the first quantum error-correcting code and fault-tolerant ideas.

1996

— Aharonov and Ben-Or, and independently Knill, Laflamme, and Zurek, prove early threshold theorems for quantum computation with local independent noise.

1997

— Kitaev develops the surface code and topological approaches, later shown to have favorable, higher thresholds.

2005–2007

— Threshold estimates for the surface code under realistic circuit-level noise are computed numerically, reaching roughly 1%.

2015

–present — Google, IBM, and others report experimental logical error suppression below physical error rates, empirically approaching threshold-crossing behavior with the surface code.

Where this matters

The threshold theorem is the load-bearing theoretical justification behind every serious industrial quantum-computing roadmap that talks about "logical qubits." Google's superconducting-qubit surface-code experiments, IBM's heavy-hex architecture, and trapped-ion efforts at Quantinuum and IonQ are all explicitly engineering toward crossing a threshold for their chosen code and noise profile — the entire notion of a "logical qubit" that outperforms its constituent physical qubits is meaningless without a threshold to be below. The surface code in particular, built from Fault-Tolerant Quantum Computing techniques using only nearest-neighbor two-qubit gates on a 2D lattice, is favored in practice precisely because numerical estimates put its threshold near 0.5–1% under realistic circuit-level noise — dramatically higher than the roughly $10^{-4}$ estimated for early concatenated codes, and closer to error rates achievable with current superconducting and trapped-ion hardware. This gap between theoretical possibility and practical achievability is exactly the terrain of the NISQ Era: today's devices are noisy and mostly above useful thresholds for deep fault-tolerant computation, which is why near-term algorithm design leans on error mitigation rather than full error correction. Looking further ahead, the threshold theorem is the reason serious estimates of The Outlook for Quantum Advantage talk in terms of "once hardware crosses threshold" rather than "if quantum error correction is possible at all" — the mathematics of scalability is settled; what remains is the sustained hardware engineering to get physical error rates reliably and verifiably below the relevant threshold, at scale, with enough qubits to run the concatenated or topological codes the theorem requires.

Ask the tutor: How does the threshold value change if we assume correlated noise instead of independent stochastic noise?

What is the actual numerical value of the threshold?

There is no single number — the threshold depends on the code, the fault-tolerant gadget design, and the assumed noise model. Early concatenated-code proofs using loose union bounds gave pessimistic estimates around $10^{-6}$ to $10^{-4}$ . More careful analyses and the surface code, which tolerates only local two-qubit gates and has efficient decoders, push estimates to roughly $0.5\%$ – $1\%$ under realistic circuit-level depolarizing noise. Experimental hardware error rates for two-qubit gates in leading superconducting and trapped-ion systems are now in the $0.1\%$ – $1\%$ range, which is why the surface code is the leading practical candidate: its threshold is within reach of achievable physical fidelities, unlike the much stricter concatenated-code thresholds of the 1990s.

Does crossing the threshold mean a quantum computer immediately becomes useful?

No. Crossing the threshold only guarantees that logical error rates can in principle be suppressed arbitrarily by adding more encoding levels or larger code distance. It says nothing about whether the overhead required is small enough to be practical with a given number of physical qubits, nor about algorithmic speed. In practice, useful fault-tolerant algorithms like large-instance Shor's algorithm are estimated to need millions of physical qubits even with surface-code overheads, because the polylogarithmic factor, while asymptotically small, still carries a large constant. Threshold-crossing is a necessary condition for scalability, not a sufficient one for near-term utility.

How is the threshold theorem different from ordinary quantum error correction?

Ordinary quantum error correction (a single application of a code) can reduce the error rate for one round of correction, but says nothing about repeated, long-running computation, because the correction circuitry itself introduces new errors. The threshold theorem specifically addresses fault tolerance under recursive concatenation: it proves that if you build gadgets satisfying strict fault-tolerance properties and nest them, the net effect including all the correction overhead still drives errors toward zero, provided the base error rate is low enough. It's the difference between "this code can fix an error" and "this entire error-correcting architecture, including its own imperfections, converges to arbitrary reliability."

Why is the overhead described as "polylogarithmic" rather than "constant"?

Because the number of concatenation levels $L$ needed to reach a target error rate $\varepsilon$ grows as $O(\log\log(1/\varepsilon))$ , and the physical resources per logical qubit grow exponentially in $L$ (as $n^L$ ). Composing these, the resource count becomes $n^{O(\log \log(1/\varepsilon))}$ , which simplifies to a polynomial in $\log(1/\varepsilon)$ — hence polylogarithmic in $1/\varepsilon$ , and in turn polylogarithmic in the circuit size $N$ once you set $\varepsilon \sim 1/N$ via a union bound over all gates in the computation. It's not constant because deeper computations genuinely need more suppression, but it grows extremely slowly compared to the size of the computation itself.

Can the threshold theorem fail for real quantum hardware even if the theorem is mathematically true?

Yes, in the sense that the theorem's guarantees apply only under its stated noise model assumptions. If real hardware exhibits strongly correlated errors (e.g., cosmic-ray-induced bursts affecting many qubits simultaneously, or non-Markovian drift), the independent-fault-counting argument underlying the proof does not directly apply, and the effective threshold for that noise could be different or the theorem's guarantees could be weaker. This is why experimental groups work hard to characterize their actual noise (via randomized benchmarking, gate-set tomography, and related techniques) before claiming operation below threshold — the theorem is only as good as the noise model it's checked against.

How does the surface code get a higher threshold than early concatenated codes?

The surface code's threshold is higher partly because it uses only local, geometrically constrained two-qubit gates, which matches well with real hardware connectivity and avoids costly long-range operations that are themselves noisy. It also allows for efficient, near-optimal decoding algorithms (like minimum-weight perfect matching) that extract more error-correcting power from the syndrome data than the simple union-bound arguments used in early concatenated-code proofs. The comparison is somewhat apples-to-oranges: concatenated-code thresholds in early papers were often deliberately conservative analytic bounds, while surface-code thresholds are typically estimated numerically via mapping to statistical-mechanics models, which tend to find substantially higher true thresholds.

What is the relationship between the threshold theorem and the code distance?

Code distance $d$ (the minimum number of errors needed to cause an undetectable logical error) determines how error rate scales with fixed encoding, but the threshold theorem is fundamentally about the recursive or scaling structure — either concatenation levels or, for topological codes like the surface code, increasing code distance directly. In the surface-code formulation, the threshold theorem states that increasing the code distance $d$ while keeping physical error rate below $p_{th}$ suppresses logical error roughly as $(p/p_{th})^{d/2}$ , an exponential (not doubly exponential) suppression in $d$ , which requires a polynomial (in $d$ ) number of physical qubits — a different but equally valid route to the same qualitative conclusion as concatenation.