The threshold theorem: below a critical error rate p_th ≈ 1%, arbitrary quantum computation can be made reliable by concatenation.
0.010
5
3
0.010
Fault-Tolerant Threshold Theorem (Aharonov-Ben-Or 1997, Knill-Laflamme-Zurek 1996):
If each physical gate fails with probability p < p_th, then by using concatenated error-correcting codes (e.g., [[7,1,3]] Steane code or surface codes),
the logical error rate after L levels is p_L ≈ p_th · (p/p_th)^(d^L).
The overhead grows as O(polylog(1/ε)) gates to achieve target logical error ε.
Surface codes have p_th ≈ 1% (Fowler et al 2012). The [[7,1,3]] code corrects all 1-qubit errors; d qubits needed ≈ d² for surface code.
Key insight: below threshold, each level of concatenation squares the error rate (exponential suppression).