Concatenation & the Threshold Theorem
Why errors below a threshold can be suppressed arbitrarily.
How can a machine built entirely from faulty parts run a billion-step computation? The threshold theorem answers quantitatively: below a constant physical error rate, recursive simulation suppresses logical errors doubly exponentially, at a cost that grows only polylogarithmically with the size of the computation.
What you’ll learn
- State the threshold theorem precisely, including the local stochastic noise model and the architectural assumptions.
- Define rectangles and extended rectangles, and prove that good exRecs are correct (Aliferis–Gottesman–Preskill).
- Derive and the overhead.
- Explain which assumptions are essential, how thresholds are estimated, and how the theorem extends to correlated noise.
The theorem, precisely
Model a circuit as a set of locations: preparations, one- and two-qubit gates, measurements and waits (idle steps). All qubits are acted on in parallel at every time step, and fresh ancillas are available whenever needed.
The assumptions matter. Parallelism: idle qubits accumulate errors, so error correction must run everywhere at once. Fresh ancillas: error correction pumps entropy out of the computer, and without a supply of fresh qubits noisy reversible computation cannot run beyond logarithmic depth (Aharonov, Ben-Or, Impagliazzo & Nisan, 1996). Fast, reliable classical processing of syndromes. Weak correlations: noise must not act coherently on many qubits at once with large amplitude.
Rectangles and the AGP proof
Fix a distance-3 code (it corrects error), fault-tolerant gadgets for every location type, and an error-correction gadget EC. The level-1 simulation replaces each location by a 1-Rec: its gadget followed by EC on every output block. The extended rectangle (exRec) also includes the ECs that precede the gadget: leading EC, gadget, trailing EC. Consecutive exRecs overlap in their shared ECs.
EC properties (guaranteed by a fault-tolerant EC design). (EC-1) For any input, an EC with faults outputs a state within errors of a codeword. (EC-2) If the input is within errors of a codeword and the EC has faults with , the output decodes to the same logical state as the input.
Gadget property. A gadget with faults, acting on inputs within errors per block of codewords with , outputs blocks within errors that decode to the ideal gate applied to the decoded inputs.
Let count the faults in the leading EC, the gadget and the trailing EC, with . By EC-1 the leading EC's output is within errors of a codeword. By the gadget property the gadget's output is within errors and decodes correctly. By EC-2 the trailing EC preserves that decoded value.
on the output of the leading EC, which is the definition of a correct 1-Rec.
Now sweep the ideal decoder through the level-1 circuit from the end to the beginning. Each correct 1-Rec lets pass through, turning into an ideal gate. A 1-Rec whose exRec is bad may fail, leaving an ideal circuit in which those locations are faulty. (Overlapping exRecs need care: AGP truncate exRecs so that each fault is charged to only one bad exRec.) So the level-1 simulation is equivalent to the ideal circuit with effective faults at the bad exRecs, and
A level- simulation is a level-1 simulation of the level- circuit.
Union bound over the logical locations; choose the smallest such .
Each level multiplies the size by at most , and , so the overhead is polylogarithmic with exponent .
What sets the threshold
The proof gives , but most pairs of faults are harmless. Only malignant pairs, which actually cause a logical failure, need to be counted: . Counting them by computer for a Steane-code scheme gave Aliferis, Gottesman and Preskill their rigorous . Numerical simulations of concatenated codes typically give to , and schemes built on heavy postselection (Knill, 2005) estimate thresholds of order a percent.
| Approach | Threshold (approx.) | Nature of the number |
|---|---|---|
| Concatenated distance-3 code, malignant-pair counting | rigorous lower bound, adversarial local stochastic noise | |
| Concatenated Steane or Bacon–Shor codes | – | numerical, depolarizing noise |
| Knill's postselected scheme | of order | numerical, very large overhead |
| Surface code with matching | – | numerical, circuit-level depolarizing noise |
An exRec has locations, and you pessimistically treat every pair of faults as malignant. What threshold lower bound does the counting argument give?
Show the answer
B.
: a level-1 failure needs two faults among locations. In reality only malignant pairs count, which is why careful counting raises the bound.
Beyond the idealized model
Real noise is not local stochastic. Three extensions are known:
- Non-Markovian Hamiltonian noise. If system–bath couplings acting on each location have bounded norm , thresholds exist in terms of , with the duration of a location (Terhal & Burkard, 2005; Aliferis, Gottesman & Preskill, 2006).
- Long-range correlations. Pairwise system–bath interactions that decay fast enough with distance still allow a threshold (Aharonov, Kitaev & Preskill, 2006).
- Coherent errors. Small unitary over-rotations add up in amplitude rather than probability; twirling (randomized compiling) converts them into stochastic Pauli noise of comparable infidelity.
Some failure modes lie outside every version: leakage out of the qubit subspace, and rare bursts that hit many qubits at once (seen in superconducting chips after high-energy impacts). Engineering against them, with leakage-reduction units, erasure conversion and gap engineering, matters as much as the theorem.
Key takeaways
- Threshold theorem: for local stochastic noise below a constant , any -location circuit can be simulated to accuracy with locations.
- AGP proof: good exRecs (at most one fault) are correct; bad ones occur with probability at most , so the level-1 simulation is an ideal circuit under weaker local stochastic noise, and the argument recurses.
- with overhead exponent .
- Rigorous thresholds (around ) are conservative; simulated ones range from to about . Fresh ancillas, parallelism and weak correlations are essential assumptions.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
In the local stochastic noise model of strength , which statement holds?
- Each location fails independently with probability exactly
- Faults can only be Pauli or errors
- At most one location fails per time step
- Any given set of locations is simultaneously faulty with probability at most , and faulty locations may act arbitrarily
Show the answer
D. Any given set of locations is simultaneously faulty with probability at most , and faulty locations may act arbitrarily
The model bounds the probability of every pattern of faults, allowing correlations and adversarial faulty operations, as long as specified faults have probability at most .
In the AGP proof for a distance-3 code, an extended rectangle is good when…
- it contains at most one fault
- it contains no faults
- its trailing EC sees a trivial syndrome
- its gadget is transversal
Show the answer
A. it contains at most one fault
A distance-3 code with fault-tolerant gadgets tolerates any single fault in an exRec; failure requires two. Bad exRecs therefore have probability at most .
With locations per exRec, how does the size overhead scale with the target accuracy?
- , independent of
Show the answer
C.
. The exponent is large, one reason practical schemes favor codes with better constants, but the scaling is polylogarithmic.
Which ingredient is essential, in the sense that without it no threshold can exist?
- All-to-all qubit connectivity
- A steady supply of fresh ancilla qubits to remove entropy
- Perfect syndrome measurements
- Purely Pauli noise
Show the answer
B. A steady supply of fresh ancilla qubits to remove entropy
Error correction is entropy removal. Without fresh qubits, noisy computation loses all information after logarithmic depth (Aharonov, Ben-Or, Impagliazzo & Nisan). The others are conveniences: 2D nearest-neighbor layouts suffice, measurements may be noisy, and arbitrary local noise is allowed.
Further reading
- D. Aharonov & M. Ben-Or, "Fault-tolerant quantum computation with constant error rate", SIAM J. Comput. (2008); conference version STOC 1997.
- E. Knill, R. Laflamme & W. H. Zurek, "Resilient quantum computation", Science 279, 342 (1998).
- A. Yu. Kitaev, "Quantum computations: algorithms and error correction", Russian Math. Surveys 52 (1997).
- P. Aliferis, D. Gottesman & J. Preskill, "Quantum accuracy threshold for concatenated distance-3 codes", Quantum Inf. Comput. 6, 97 (2006).
- D. Gottesman, "An introduction to quantum error correction and fault-tolerant quantum computation" (2009), arXiv:0904.2557.