The Threshold Theorem

The central guarantee of the field

The threshold theorem is the result that makes large-scale quantum computing possible in principle. It says that there is a fixed error rate — a positive constant set by the code, fault-tolerant construction, decoder, and noise model, but independent of the size of the computation — below which arbitrarily long, arbitrarily accurate quantum computation is achievable, at a cost that grows only mildly with the target accuracy. Everything else in this module — gadgets, concatenation, codes, overhead — is either an ingredient of its proof or a consequence of its statement.

Statement

The two clauses carry all the weight. First, $p_{\text{th}}$ is a constant: it does not shrink as the computation grows. Second, the overhead is polylogarithmic in $1/\varepsilon$ — to halve the allowed failure probability you pay only a small additive number of extra layers, not a doubling of hardware.

Why a threshold exists: the recursion

The cleanest proof uses concatenation. Encode each qubit in a distance-3 code; the fault-tolerant gadgets guarantee one fault produces at most one error, so the logical block fails only when two or more faults coincide inside it. If a level-0 (physical) component fails with probability $p$ , and a level-1 gadget contains roughly $A$ fault locations, the level-1 logical failure rate is at most

p_1 \;\le\; A\, p^2 ,

because at least two of the $A$ locations must fail. Define $p_{\text{th}} = 1/A$ . Concatenating again replaces each level-1 component by a level-2 gadget, and the same argument gives

p_{L} \;\le\; \frac{1}{A}\,(A\,p)^{2^{L}} = p_{\text{th}}\left(\frac{p}{p_{\text{th}}}\right)^{2^{L}} .

Reading the double-exponential

The factor $(p/p_{\text{th}})^{2^L}$ is the engine. If $p < p_{\text{th}}$ the ratio $p/p_{\text{th}} < 1$ , so raising it to the power $2^L$ drives $p_L$ toward zero doubly exponentially in the number of levels $L$ . To reach a target logical error $\varepsilon$ we need

\left(\frac{p}{p_{\text{th}}}\right)^{2^{L}} \approx \frac{\varepsilon}{p_{\text{th}}} \quad\Longrightarrow\quad L \approx \log_2 \frac{\log(p_{\text{th}}/\varepsilon)}{\log(p_{\text{th}}/p)} .

So $L$ grows only like $\log\log(1/\varepsilon)$ . Each level multiplies the qubit and gate count by a constant factor, so the total overhead is $\big(\text{const}\big)^{L} = \mathrm{polylog}(1/\varepsilon)$ — exactly the claim. If instead $p > p_{\text{th}}$ the ratio exceeds $1$ , concatenation makes things worse, and there is no escape: the threshold is a genuine phase boundary.

What the threshold is not

The threshold is a property of a scheme plus a noise model, not a single universal number. Quoted values range from below $10^{-4}$ for some concatenated proofs with adversarial noise to around $1\%$ for the surface code under circuit-level depolarizing noise. The theorem guarantees only that some positive constant exists; computing a good one for a given code and noise model is its own craft, taken up in the next lessons.

What to take away

A constant error threshold exists; below it, concatenation (or a growing topological code) suppresses logical errors doubly exponentially in the depth of protection while costing only polylogarithmic overhead. This converts the seemingly hopeless accumulation of $pN$ errors from the opening lesson into a controllable, scalable resource budget.