The Threshold Theorem
If the physical error rate is below a threshold, arbitrarily long quantum computation is possible with only polylogarithmic overhead.
The central promise
The threshold theorem states that there exists a constant error rate p_th such that, if every physical component fails with probability below p_th, then any quantum computation can be run to any desired accuracy using fault-tolerant encoding, with overhead growing only polylogarithmically in the size of the computation. Below threshold, adding more error correction makes the logical error rate fall; above threshold, it makes things worse.
Why a threshold exists
Consider encoding, then encoding the encoding, and so on. At each level, a logical error requires two or more errors at the level below to conspire. If the level-below error rate is p, the level-above rate is roughly (p / p_th) times p_th, so a single level of concatenation squares the ratio p/p_th. When p < p_th this ratio drives the error rate doubly exponentially toward zero with each level; when p > p_th it explodes. The crossover point is the threshold.
- Below p_th: logical error rate falls as code distance or concatenation grows.
- Above p_th: more encoding amplifies errors instead of suppressing them.
- Overhead to reach target accuracy grows only as a polynomial in log(1/error).
- Threshold value depends on the code, noise model, and decoder.
Numbers and caveats
The threshold is not universal; it depends on the code, the noise model, and the decoder. Concatenated codes give thresholds around 10^-4 to 10^-3. The surface code reaches roughly 10^-2 under circuit-level depolarizing noise with a good matching decoder, which is why it is favored: current hardware error rates are approaching that regime. Being below threshold is necessary but not sufficient for a useful machine; the required overhead still depends strongly on how far below threshold you operate.
The theorem, proved in various forms by Aharonov and Ben-Or, Kitaev, Knill, Laflamme, and others, is the theoretical justification that fault-tolerant quantum computing is possible at all. It rests on fault-tolerant gadget design so that errors do not cascade uncontrollably.