Simple Algorithm
Quantum Computing · Rydberg State · 32 min

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 p(k)≤pth(p/pth)2kp^{(k)}\le p_{\mathrm{th}}(p/p_{\mathrm{th}})^{2^k} and the polylog⁡(L/ε)\operatorname{polylog}(L/\varepsilon) 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 ∣0⟩\ket{0} 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 t=1t=1 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.

DerivationProof sketch
  1. EC properties (guaranteed by a fault-tolerant EC design). (EC-1) For any input, an EC with s≤ts\le t faults outputs a state within ss errors of a codeword. (EC-2) If the input is within rr errors of a codeword and the EC has ss faults with r+s≤tr+s\le t, the output decodes to the same logical state as the input.

  2. Gadget property. A gadget with ss faults, acting on inputs within rr errors per block of codewords with r+s≤tr+s\le t, outputs blocks within r+sr+s errors that decode to the ideal gate applied to the decoded inputs.

  3. Let sℓ,sg,sts_\ell,s_g,s_t count the faults in the leading EC, the gadget and the trailing EC, with sℓ+sg+st≤1s_\ell+s_g+s_t\le1. By EC-1 the leading EC's output is within sℓs_\ell errors of a codeword. By the gadget property the gadget's output is within sℓ+sg≤1s_\ell+s_g\le1 errors and decodes correctly. By EC-2 the trailing EC preserves that decoded value.

  4. D∘(trailing EC)∘(gadget)=(ideal gate)∘D\mathcal{D}\circ(\text{trailing EC})\circ(\text{gadget}) = (\text{ideal gate})\circ\mathcal{D}

    on the output of the leading EC, which is the definition of a correct 1-Rec. □\square

Now sweep the ideal decoder through the level-1 circuit from the end to the beginning. Each correct 1-Rec lets D\mathcal{D} 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

Pr⁡[exRec bad] ≤ (A2)p2=:p(1)\Pr[\text{exRec bad}]\ \le\ \binom{A}{2}p^2 =: p^{(1)}
AA is the maximum number of locations in an exRec. The effective noise is again local stochastic, now of strength p(1)p^{(1)}, so the argument applies to itself.
DerivationRecursion and overhead
  1. p(k) ≤ (A2)(p(k−1))2 ⟹ p(k) ≤ pth(ppth)2k,pth=(A2)−1p^{(k)}\ \le\ \binom{A}{2}\big(p^{(k-1)}\big)^2\ \Longrightarrow\ p^{(k)}\ \le\ p_{\mathrm{th}}\Big(\frac{p}{p_{\mathrm{th}}}\Big)^{2^k},\qquad p_{\mathrm{th}}=\binom{A}{2}^{-1}

    A level-kk simulation is a level-1 simulation of the level-(k−1)(k-1) circuit.

  2. L p(k)≤ε⟸2k≥log⁡(L pth/ε)log⁡(pth/p)L\,p^{(k)}\le\varepsilon\quad\Longleftarrow\quad 2^k \ge \frac{\log(L\,p_{\mathrm{th}}/\varepsilon)}{\log(p_{\mathrm{th}}/p)}

    Union bound over the LL logical locations; choose the smallest such kk.

  3. L′ ≤ L Ak=L (2k)log⁡2A=O(L log⁡log⁡2A(L/ε))L'\ \le\ L\,A^k = L\,(2^k)^{\log_2 A} = \order{L\,\log^{\log_2 A}(L/\varepsilon)}

    Each level multiplies the size by at most AA, and 2k=O(log⁡(L/ε))2^k=\order{\log(L/\varepsilon)}, so the overhead is polylogarithmic with exponent a=log⁡2Aa=\log_2A. □\square

What sets the threshold

The proof gives pth≥1/(A2)p_{\mathrm{th}}\ge1/\binom{A}{2}, but most pairs of faults are harmless. Only malignant pairs, which actually cause a logical failure, need to be counted: p(1)≤Nmal p2p^{(1)}\le N_{\mathrm{mal}}\,p^2. Counting them by computer for a Steane-code scheme gave Aliferis, Gottesman and Preskill their rigorous 2.73×10−52.73\times10^{-5}. Numerical simulations of concatenated codes typically give 10−410^{-4} to 10−310^{-3}, and schemes built on heavy postselection (Knill, 2005) estimate thresholds of order a percent.

ApproachThreshold (approx.)Nature of the number
Concatenated distance-3 code, malignant-pair counting≥2.7×10−5\ge2.7\times10^{-5}rigorous lower bound, adversarial local stochastic noise
Concatenated Steane or Bacon–Shor codes∼10−4\sim10^{-4}–10−310^{-3}numerical, depolarizing noise
Knill's postselected C4/C6C_4/C_6 schemeof order 1%1\%numerical, very large overhead
Surface code with matching≈0.5\approx0.5–1%1\%numerical, circuit-level depolarizing noise
Numbers depend strongly on the noise model, the gate set and how locations are counted. A rigorous bound and a simulated threshold answer different questions.
Check your understanding

An exRec has A=150A=150 locations, and you pessimistically treat every pair of faults as malignant. What threshold lower bound does the counting argument give?

  1. 1/150≈7×10−31/150\approx7\times10^{-3}
  2. 1/(1502)≈9×10−51/\binom{150}{2}\approx9\times10^{-5}
  3. 1/1502≈4.4×10−51/150^2\approx4.4\times10^{-5}
  4. 1/(1503)≈1.8×10−61/\binom{150}{3}\approx1.8\times10^{-6}
Show the answer

B. 1/(1502)≈9×10−51/\binom{150}{2}\approx9\times10^{-5}

pth≥1/(A2)=1/11175≈9×10−5p_{\mathrm{th}}\ge1/\binom{A}{2}=1/11175\approx9\times10^{-5}: a level-1 failure needs two faults among AA 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 λ\lambda, thresholds exist in terms of λt0\lambda t_0, with t0t_0 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 pthp_{\mathrm{th}}, any LL-location circuit can be simulated to accuracy ε\varepsilon with O(Llog⁡a(L/ε))\order{L\log^{a}(L/\varepsilon)} locations.
  • AGP proof: good exRecs (at most one fault) are correct; bad ones occur with probability at most (A2)p2\binom{A}{2}p^2, so the level-1 simulation is an ideal circuit under weaker local stochastic noise, and the argument recurses.
  • p(k)≤pth(p/pth)2kp^{(k)}\le p_{\mathrm{th}}(p/p_{\mathrm{th}})^{2^k} with overhead exponent a=log⁡2Aa=\log_2A.
  • Rigorous thresholds (around 10−510^{-5}) are conservative; simulated ones range from 10−410^{-4} to about 1%1\%. 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.

Question 1

In the local stochastic noise model of strength pp, which statement holds?

  1. Each location fails independently with probability exactly pp
  2. Faults can only be Pauli XX or ZZ errors
  3. At most one location fails per time step
  4. Any given set of rr locations is simultaneously faulty with probability at most prp^r, and faulty locations may act arbitrarily
Show the answer

D. Any given set of rr locations is simultaneously faulty with probability at most prp^r, 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 rr specified faults have probability at most prp^r.

Question 2

In the AGP proof for a distance-3 code, an extended rectangle is good when…

  1. it contains at most one fault
  2. it contains no faults
  3. its trailing EC sees a trivial syndrome
  4. 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 (A2)p2\binom{A}{2}p^2.

Question 3

With A=100A=100 locations per exRec, how does the size overhead scale with the target accuracy?

  1. O(L/ε)\order{L/\varepsilon}
  2. O(eL)\order{e^{L}}
  3. O(Llog⁡6.64(L/ε))\order{L\log^{6.64}(L/\varepsilon)}
  4. O(1)\order{1}, independent of ε\varepsilon
Show the answer

C. O(Llog⁡6.64(L/ε))\order{L\log^{6.64}(L/\varepsilon)}

a=log⁡2A=log⁡2100≈6.64a=\log_2A=\log_2100\approx6.64. The exponent is large, one reason practical schemes favor codes with better constants, but the scaling is polylogarithmic.

Question 4

Which ingredient is essential, in the sense that without it no threshold can exist?

  1. All-to-all qubit connectivity
  2. A steady supply of fresh ancilla qubits to remove entropy
  3. Perfect syndrome measurements
  4. 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.