Code Concatenation

A single quantum error-correcting code of distance $d$ corrects up to $t=\lfloor(d-1)/2\rfloor$ faults, converting a physical error probability $p$ into a logical failure rate of order $c\,p^{t+1}$ . That is a one-shot bargain: it pays only when $p$ is already small enough that $c\,p^{t+1}<p$ , and it stops there. No fixed code, however good, drives the logical error rate to zero — the ratio improves once and then sits still. To keep improving you must repeat the trick on the output of the last trick. Code concatenation is exactly that repetition: take the logical qubit a code produces, treat it as a fresh "physical" qubit, and encode it again inside another code, iterating $L$ times to build a hierarchy of codes nested one inside the next. The bookkeeping is clean. Level-0 is a bare physical qubit; level-1 is one logical qubit encoded in $n$ physical qubits; level-2 re-encodes each of those $n$ qubits in $n$ more, spending $n^2$ physical qubits; after $L$ levels a single logical qubit occupies $n^L$ of them. The effective error rate obeys a level recursion $p_{\ell+1}=c\,p_\ell^{\,t+1}$ , and whether that recursion converges is decided entirely by one dimensionless ratio, $p/p_{\mathrm{th}}$ , where the threshold $p_{\mathrm{th}}=c^{-1/t}$ is the unstable fixed point of the map. Below it the cascade collapses to zero; above it the cascade runs away. The payoff is the threshold theorem — the constructive promise that if physical errors sit below $p_{\mathrm{th}}$ and every gadget (gates, measurement, preparation) is fault-tolerant, then any target logical error $\varepsilon$ is reachable with only $\mathrm{polylog}(1/\varepsilon)$ overhead. This is the theorem that licenses building large quantum computers out of imperfect parts. Concatenation is its oldest and most transparent proof, and its recursive skeleton reappears in magic-state distillation, biased-noise architectures, and the very definition of what "fault-tolerant" must mean.

Key takeaways

Code concatenation nests one quantum code inside another: each physical qubit of a code is itself replaced by a logical qubit of the same or another code, recursively to $L$ levels, so one logical qubit occupies $n^L$ physical qubits.
One level of a distance-3 code maps the error $p\mapsto c\,p^2$ ; iterating gives a doubly-exponential collapse $p_L\le c^{-1}\,(p/p_{\mathrm{th}})^{2^L}$ .
The threshold $p_{\mathrm{th}}=c^{-1/t}$ is the unstable fixed point of the level recursion — below it errors vanish, above it concatenation actively hurts.
Reaching logical error $\varepsilon$ needs only $L=O(\log\log(1/\varepsilon))$ levels and $N=n^L=\mathrm{polylog}(1/\varepsilon)$ physical qubits: the quantitative threshold theorem.
Distances multiply, $d_L\ge d^{\,L}$ ; the Shor $[[9,1,3]]$ code is the prototypical concatenation of a phase-flip with a bit-flip code.
The threshold belongs to the whole fault-tolerant scheme — code, decoder, and especially the syndrome-extraction gadgets — not to the bare code distance; non-fault-tolerant gadgets destroy it.
Key idea: Concatenation turns a single quadratic-suppression step $p\mapsto c\,p^2$ into a doubly-exponential one $p\mapsto(p/p_{\mathrm{th}})^{2^L}$ , so any fixed physical error rate below the fixed-point threshold $p_{\mathrm{th}}$ can be driven to arbitrarily small logical error with overhead growing only polylogarithmically in the target precision.

The core insight

Concatenation turns a single quadratic-suppression step $p\mapsto c\,p^2$ into a doubly-exponential one $p\mapsto(p/p_{\mathrm{th}})^{2^L}$ , so that any fixed physical error rate below the fixed-point threshold $p_{\mathrm{th}}$ can be driven to an arbitrarily small logical error rate with overhead growing only polylogarithmically in the target precision.

Where this lives today

Concatenation is having a second life. For two decades the topological surface code dominated fault-tolerant architecture — its ~1% circuit-level threshold and purely two-dimensional, nearest-neighbour layout suited superconducting hardware — and concatenated codes were treated as the pedagogical route to the threshold theorem rather than a competitive design. That balance is shifting. High-rate concatenated constructions such as Hayato Goto's "many-hypercube" codes (2024) reach thresholds comparable to the surface code while encoding many logical qubits per block, reviving concatenation as a serious low-overhead option. Biased-noise architectures concatenate an inner bosonic cat code, which exponentially suppresses bit flips, with an outer repetition or surface code that only has to mop up the residual phase flips — the level structure letting each layer specialize to the noise it is best against. Trapped-ion and neutral-atom platforms, with their long-range connectivity, are natural homes for concatenated and non-local codes that superconducting grids cannot easily host, and small concatenated codes (including the Bacon–Shor family) have been run fault-tolerantly on ions. And the recursive skeleton itself is inescapable: magic-state distillation, which supplies the non-Clifford resources no transversal CSS gate can produce, is literally concatenation applied to states rather than qubits, iterating a map $p\mapsto c\,p^k$ with its own threshold. Whichever code ultimately wins the hardware race, the doubly-exponential logic Aharonov and Ben-Or made rigorous is the yardstick every scheme is measured against.

The physical picture

Think of one level of encoding as a noise-cleaning amplifier. A distance-3 code is a circuit that, handed inputs each wrong with probability $p$ , returns an output wrong with probability only $\sim c\,p^2$ — because defeating a code that corrects one error takes at least two errors, and two independent rare events are quadratically rarer than one. Now feed that cleaner output into an identical cleaner. It squares the smallness again. Stack $L$ of them and the badness is $p^{2^L}$ up to constants: a doubly-exponential collapse, not a mere exponential one. This is the whole engine of fault tolerance in a sentence, and the first figure draws the nested hierarchy that produces it. The threshold is simply the break-even point of the amplifier. Each stage multiplies the input by roughly $c\,p$ , so it helps only while $c\,p<1$ , i.e. $p<1/c$ . Sharpening this for a general distance, the map $f(x)=c\,x^{t+1}$ has a nonzero fixed point at $p_{\mathrm{th}}=c^{-1/t}$ : below it every stage genuinely improves things and the cascade flows to zero; above it every stage makes things worse and the cascade flows to maximal error. That single unstable fixed point cleanly partitions the world of noisy hardware into "can be made arbitrarily reliable" and "cannot." The second figure shows the recursion as exactly this amplifier map, with the sub-threshold cascade squaring an error of $0.1$ down through $10^{-2}$ , $10^{-4}$ , $10^{-8}$ .

Figure

Concatenation builds a tree of encodings: level 0 is one bare qubit, level 1 encodes it in n = 3 qubits, level 2 re-encodes each of those in 3 more, so after L levels one logical qubit occupies nᴸ physical qubits (1 → 3 → 9 → 27 …)

A useful sharper image: a logical error at level $L$ is not one big failure but a whole tree of aligned small failures — at least $t+1$ faults inside some block, and inside $t+1$ of those blocks another $t+1$ faults, all the way down. The probability of such a coordinated tree is the product of the per-level failure probabilities, and coordinated trees are combinatorially scarce. That scarcity, compounding level by level, is the microscopic origin of the doubly-exponential suppression. Overhead is its dual: to reach error $\varepsilon$ you need only $L\sim\log\log(1/\varepsilon)$ levels, hence $n^L=\mathrm{poly}(\log(1/\varepsilon))$ physical qubits — cheap in $\varepsilon$ , but carrying a stiff prefactor, which is why concatenation is analytically supreme yet in practice heavier than the topological surface code.

Figure

The recursion pₗ₊₁ = c pₗ² as a noise amplifier with c = 4, so the unstable fixed point sits at p_th = 1 c = 0.25: below it each level squares the error downward (green cobweb, 0.1 → 10⁻² → 10⁻⁴ → 10⁻⁸ in units of p_th), above it the error runs away toward 1 (red)

The core equations

Everything quantitative about concatenation flows from one recursion. A distance- $(2t{+}1)$ code equipped with fault-tolerant gadgets fails only when at least $t+1$ independent faults land in a block; the leading small- $p$ probability of that is $\binom{n}{t+1}p^{t+1}$ . Promoting the physical rate to the effective rate at each level gives the map that all the later results iterate.

p_{\ell+1} \;=\; c\,p_\ell^{\,t+1} \qquad (1)

where: $p_\ell$ — effective logical error probability at concatenation level $\ell$ (with $p_0=p$ ); $c$ — combinatorial constant counting the malignant sets of $t+1$ fault locations, $c\approx\binom{n}{t+1}$ at the code-capacity level; $t=\lfloor(d-1)/2\rfloor$ — number of correctable faults for distance $d$ . Reading: the exponent $t+1$ , not the prefactor, is what makes concatenation work — it guarantees each level shrinks a small error super-linearly. The recursion has two fixed points, $p=0$ and a nonzero one obtained by setting $p_{\ell+1}=p_\ell$ . That nonzero fixed point is the threshold: the error rate at which encoding neither helps nor hurts.

p_{\mathrm{th}} \;=\; c^{-1/t} \qquad (2)

where: $p_{\mathrm{th}}$ — fault-tolerance threshold, the physical error rate separating convergence from divergence; for a distance-3 base code ( $t=1$ ) it collapses to the memorable $p_{\mathrm{th}}=1/c$ . Reading: $p_{\mathrm{th}}$ is a property of the scheme (code, decoder, gadgets), computed once; the hardware then only has to beat this fixed number. Iterating (1) in the normalized variable $x_\ell=p_\ell/p_{\mathrm{th}}$ turns the map into pure exponentiation $x_{\ell+1}=x_\ell^{\,t+1}$ , whose $L$ -fold iterate is a tower of exponents. Undoing the normalization gives the headline suppression law.

p_L \;\le\; c^{-1/t}\left(\frac{p}{p_{\mathrm{th}}}\right)^{(t+1)^{L}} \qquad (3)

where: $L$ — number of concatenation levels; the exponent $(t+1)^L$ grows doubly-exponentially in $L$ . Reading: as long as $p<p_{\mathrm{th}}$ the base $p/p_{\mathrm{th}}$ is less than 1, so raising it to an exploding power crushes the logical error toward zero; a single extra level squares (for $t=1$ ) the already-tiny number. The dual of that suppression is the resource cost. Inverting the double exponential to hit a target $\varepsilon$ needs $L=O(\log\log(1/\varepsilon))$ levels, and each level multiplies the qubit count by $n$ .

N(L)=n^{L},\qquad N\sim\big(\log(1/\varepsilon)\big)^{\log_{t+1} n} \qquad (4)

where: $n$ — block length of the base code (e.g. $n=7$ for Steane, $n=9$ for Shor); $N$ — physical qubits per logical qubit after $L$ levels; $\varepsilon$ — target logical error rate. Reading: the overhead is only polylogarithmic in $1/\varepsilon$ — the precise quantitative content of the threshold theorem, and the reason arbitrarily reliable computation is affordable in principle. Concatenation also sharpens the code itself: to fool the whole hierarchy an error must fool every level in turn, so the minimum weight of a logical operator multiplies from one level to the next.

d_L \;\ge\; d^{\,L} \qquad (5)

where: $d_L$ — distance of the $L$ -level self-concatenated code; $d$ — distance of the identical base code. Reading: distance grows geometrically while qubit count grows as $n^L$ ; since typically $d<n$ , the code's rate falls, which is concatenation's structural price — magnificent distance bought with many qubits. The oldest quantum code is already a concatenation, which is why it is the cleanest worked example of the whole idea.

[[9,1,3]] \;=\; [[3,1,3]]_{Z}\;\circ\;[[3,1,3]]_{X} \qquad (6)

where: $\circ$ — concatenation (outer code $\circ$ inner code); $[[3,1,3]]_Z$ — the three-qubit phase-flip code (outer), $[[3,1,3]]_X$ — the three-qubit bit-flip code (inner). Reading: the outer code kills $Z$ errors, the inner code kills $X$ errors, and their composition corrects an arbitrary single-qubit Pauli error — the dual structure is what promotes two one-sided distance-3 codes into a genuinely universal single-error-correcting code.

Derivation AThe level recursion and the threshold as a fixed point

The goal is to pin down, from first principles, why one level of encoding maps the error rate as $p\mapsto c\,p^{t+1}$ rather than linearly, and then to locate the exact error rate — the threshold — at which iterating that map is neither profitable nor ruinous. We start from the combinatorics of block failure, extract the leading power of $p$ , and solve the fixed-point condition of the resulting recursion, so that the number $p_{\mathrm{th}}=c^{-1/t}$ emerges as the boundary between two qualitatively different fates of the cascade.

Step 1. A distance- $(2t{+}1)$ code corrects any pattern of up to $t$ faults in its block of $n$ components, so its decoder fails precisely when the number of faulty components exceeds $t$ . If components fail independently with probability $p$ , the exact block-failure probability is $P_{\mathrm{fail}}=\sum_{k=t+1}^{n}\binom{n}{k}p^k(1-p)^{n-k}$ . Why: fault tolerance is engineered so that fewer than $t+1$ faults are always corrected — failure is a tail event of the binomial.

Step 2. For small $p$ the sum is dominated by its smallest surviving power, $P_{\mathrm{fail}}\approx\binom{n}{t+1}p^{\,t+1}\equiv c\,p^{\,t+1}$ , which defines the recursion $p_{\ell+1}=c\,p_\ell^{\,t+1}$ once the level- $\ell$ error is fed in as the component error at level $\ell+1$ . Why: the leading term is the whole story near threshold, and its exponent $t+1\ge2$ is the mathematical fingerprint of error correction — a single fault can never be the leading failure.

Step 3. A fixed point $p_\star$ satisfies $p_\star=c\,p_\star^{\,t+1}$ . Discarding the trivial root $p_\star=0$ and dividing by $p_\star$ gives $1=c\,p_\star^{\,t}$ , hence $p_{\mathrm{th}}=c^{-1/t}$ ; for $t=1$ this is simply $1/c$ . Why: this is the crossover error rate, the one input the amplifier reproduces unchanged.

Step 4. Linearize the map near the fixed point: $f'(x)=c(t+1)x^{t}$ , so $f'(p_{\mathrm{th}})=c(t+1)p_{\mathrm{th}}^{\,t}=(t+1)>1$ . The slope exceeds one, so the fixed point is unstable — inputs just below it flow to $0$ , inputs just above it flow away toward maximal error. Why: instability is exactly what a threshold should be — it is a watershed, not an attractor, so being on the good side by any margin is enough. *The key checks: the leading binomial term is $c=\binom{n}{t+1}$ ; the fixed point $p_{\mathrm{th}}=c^{-1/t}$ satisfies $x=cx^{t+1}$ ; and the derivative $f'(p_{\mathrm{th}})=t+1>1$ confirms the fixed point is unstable.*

Go deeper · Derivation B · 1 minThe threshold theorem: doubly-exponential suppression at polylogarithmic cost

Derivation BThe threshold theorem: doubly-exponential suppression at polylogarithmic cost

The goal is to convert the one-step recursion into the central guarantee of fault tolerance — that below threshold any target logical error $\varepsilon$ is reachable, and to compute the price in levels and in qubits. The strategy is to change to a normalized variable in which the recursion loses its constant and becomes pure exponentiation, iterate it in closed form, invert for the number of levels, and finally propagate that level count into the physical-qubit overhead. We specialize to the distance-3 case $t=1$ for concreteness; the general $t$ only replaces squaring by raising to the $(t+1)$ -th power.

Step 1. Define $x_\ell=p_\ell/p_{\mathrm{th}}=c^{1/t}p_\ell$ . Substituting the recursion, $x_{\ell+1}=c^{1/t}\,c\,p_\ell^{\,t+1}=\big(c^{1/t}p_\ell\big)^{t+1}=x_\ell^{\,t+1}$ , and for $t=1$ this is the pure squaring $x_{\ell+1}=x_\ell^2$ . Why: normalizing by the fixed point is what erases the awkward constant $c$ and exposes the bare doubly-exponential engine underneath.

Step 2. Iterate: $x_L=x_0^{\,(t+1)^L}=(p/p_{\mathrm{th}})^{(t+1)^L}$ , and undoing the normalization gives $p_L=c^{-1/t}(p/p_{\mathrm{th}})^{(t+1)^L}$ . Because $p<p_{\mathrm{th}}$ makes the base less than one, the logical error falls doubly-exponentially in $L$ . Why: each level does not add a fixed decrement — it raises the whole small number to a higher power, so progress accelerates catastrophically in the right direction.

Step 3. Demand $p_L\le\varepsilon$ . For $t=1$ this reads $p_{\mathrm{th}}(p/p_{\mathrm{th}})^{2^L}\le\varepsilon$ , i.e. $2^L\ge\dfrac{\log(p_{\mathrm{th}}/\varepsilon)}{\log(p_{\mathrm{th}}/p)}$ , so $L=O\big(\log\log(1/\varepsilon)\big)$ . Why: the target sits under a double exponential, so undoing it costs only a double logarithm — vanishingly few levels are ever needed.

Step 4. Propagate to resources: $N=n^L=2^{L\log_2 n}=\big(\log(1/\varepsilon)\big)^{\log_2 n}=\mathrm{polylog}(1/\varepsilon)$ , and the time (circuit-depth) overhead scales the same way up to constants. Why: this is the theorem's punchline — the cost of arbitrary reliability is polylogarithmic in the reliability demanded, which is what makes scalable quantum computation possible at all. *The key results: the normalized map is $x_{\ell+1}=x_\ell^{t+1}$ ; iterating gives the closed form $x_L=x_0^{(t+1)^L}$ ; the required level count is $L=O(\log\log(1/\varepsilon))$ ; and the physical-qubit overhead is $N=(\log(1/\varepsilon))^{\log_2 n}$ , confirming the polylogarithmic scaling.*

Go deeper · Derivation C · 2 minWhy the threshold demands fault-tolerant gadgets

Derivation CWhy the threshold demands fault-tolerant gadgets

The goal is to show that the quadratic recursion — and therefore the entire threshold — is not a property of the code alone but of the circuits that operate it, and that a carelessly built syndrome-extraction gadget silently destroys the threshold even for an excellent code. The strategy is to exhibit a concrete non-fault-tolerant gadget in which a single fault propagates into an uncorrectable error, watch a linear term reappear in the recursion, and show that this linear term has no useful fixed point. This is the precise reason cat-state (Shor), transversal (Steane), and teleportation-based (Knill) extraction schemes are mandatory rather than optional.

Step 1. Consider extracting a stabilizer with one ancilla coupled by a chain of CNOTs to all $n$ data qubits in the block. A single $X$ fault on that shared ancilla after the $k$ -th CNOT back-propagates through the remaining controlled gates onto multiple data qubits at once. Why: shared control lines are conduits — one fault at the hub spreads to every spoke it still has to touch.

Step 2. The result is a weight- $\ge 2$ error in the data from a single physical fault, which a distance-3 code cannot correct. So there now exists a failure mode that is first-order in $p$ , not second-order. Why: fault tolerance is exactly the demand that no single fault cause a logical error; this gadget breaks that demand outright.

Step 3. The recursion acquires a linear term, $p_{\ell+1}=a\,p_\ell+c\,p_\ell^2$ with $a>0$ . Near $p_\ell\to0$ the linear term dominates, giving $p_{\ell+1}\approx a\,p_\ell$ and hence $p_\ell\approx a^\ell p_0$ . Why: a linear map has no nontrivial suppressing fixed point — it can only scale errors by a constant per level, never square them down.

Step 4. If $a\ge1$ errors never shrink; even if $a<1$ the improvement is merely geometric (a fixed factor per level, a single-shot gain repeated), with none of the doubly-exponential collapse. There is no threshold below 1. Why: this is the formal statement that "a good code is not enough" — the gadgets carry the threshold, and fault-tolerant syndrome extraction is what removes the poisonous linear term. *The key points: single-ancilla-chain extraction propagates one fault to a weight- $\ge2$ error; the resulting linear term $a\,p_\ell$ with $a>0$ yields $p_\ell\sim a^\ell p_0$ , which has no sub-unit suppressing fixed point — the formal reason fault-tolerant extraction schemes (Shor, Steane, Knill) are essential.*

Limiting cases

Behaviour of the level recursion $p_{\ell+1}=c\,p_\ell^{\,t+1}$ with $p_0=p$ , read across the regimes of the initial physical error rate and the number of levels:

Case	Result	Meaning
Sub-threshold, $p<p_{\mathrm{th}}$	$p_L\le c^{-1/t}\,(p/p_{\mathrm{th}})^{(t+1)^L}$	logical error falls doubly-exponentially in $L$ ; arbitrarily small error at finite resources — the useful regime
At threshold, $p=p_{\mathrm{th}}$	$p_\ell=c^{-1/t}$ for all $\ell$	the unstable fixed point of $f(x)=c\,x^{t+1}$ ; encoding neither helps nor hurts, defining $p_{\mathrm{th}}$
Super-threshold, $p>p_{\mathrm{th}}$	$p_L\to\text{(maximal)}$ as $L\to\infty$	every level amplifies error; more encoding makes the logical qubit strictly worse
Distance-3 base, $t=1$	$p_{\ell+1}=c\,p_\ell^2,\;p_{\mathrm{th}}=1/c$	the canonical quadratic case — Steane $[[7,1,3]]$ or Shor $[[9,1,3]]$ self-concatenated
Overhead to precision $\varepsilon$	$L\sim\log_{t+1}\!\dfrac{\log(1/\varepsilon)}{\log(p_{\mathrm{th}}/p)},\;N\sim n^L$	polylogarithmic qubit cost in $1/\varepsilon$ — the quantitative threshold theorem

Common trapThe threshold is a property of the bare code distance.

It is not. The threshold belongs to the entire fault-tolerant scheme — base code, decoder, and above all the syndrome-extraction, gate, preparation, and measurement gadgets — never to the code distance alone. A distance-3 code guarantees the quadratic recursion $p_{\ell+1}=c\,p_\ell^2$ only if every gadget is built so that no single fault produces a logical error; if a lone ancilla can serially corrupt a whole block, a linear term $a\,p_\ell$ reappears and the threshold vanishes outright, however large the distance. Two codes with identical $[[n,k,d]]$ can have thresholds differing by orders of magnitude purely because of their gadget design and decoder. Always verify the "one fault, at most one error per block" condition before writing down the quadratic recursion.

Worked examples

1 · The Shor code read as a concatenation (confidence builder)

Show explicitly that the nine-qubit Shor code is the three-qubit phase-flip code with each qubit re-encoded in the three-qubit bit-flip code, and confirm it corrects an arbitrary single-qubit error.

Step 1. Outer (phase-flip) code. Encode the logical qubit against $Z$ errors by $|0\rangle\mapsto|{+}{+}{+}\rangle$ , $|1\rangle\mapsto|{-}{-}{-}\rangle$ , with $|\pm\rangle=(|0\rangle\pm|1\rangle)/\sqrt2$ . This code has distance 3 against phase flips but cannot see a bit flip at all. The three "qubits" it produces are not yet physical — they are slots to be filled by an inner code.

Step 2. Inner (bit-flip) code. Encode each slot against $X$ errors by $|0\rangle\mapsto|000\rangle$ , $|1\rangle\mapsto|111\rangle$ , so $|{+}\rangle\mapsto(|000\rangle+|111\rangle)/\sqrt2$ and $|{-}\rangle\mapsto(|000\rangle-|111\rangle)/\sqrt2$ . Substituting into Step 1 gives the logical codeword

|0_L\rangle=\frac{1}{2\sqrt2}\big(|000\rangle+|111\rangle\big)^{\otimes 3},\qquad |1_L\rangle=\frac{1}{2\sqrt2}\big(|000\rangle-|111\rangle\big)^{\otimes 3}.

The prefactor is $(1/\sqrt2)^3=1/(2\sqrt2)$ , one factor per inner block — a quick normalization check that the concatenation was assembled correctly.

Step 3. Error correction. A single $X$ on any physical qubit is caught by the inner bit-flip code of its block; a single $Z$ acts within a block as a sign flip of that block's $|{\pm}\rangle$ value and is caught by the outer phase-flip code; a $Y=iXZ$ is caught as both at once. So every single-qubit Pauli error is corrected. The Shor code is $[[3,1,3]]_Z\circ[[3,1,3]]_X$ , its distance is $3$ , and the dual inner/outer structure upgrades two one-sided codes into full single-error correction.

2 · How many levels, how many qubits (fully worked, with numbers)

A fault-tolerant scheme built on the Steane $[[7,1,3]]$ code ( $n=7$ , $t=1$ ) has an effective gadget threshold $p_{\mathrm{th}}=10^{-2}$ . The hardware runs at $p=10^{-3}$ . How many concatenation levels are needed to reach a logical error $\varepsilon=10^{-15}$ , and how many physical qubits does one logical qubit then cost?

Step 1. Normalize the starting error: $x_0=p/p_{\mathrm{th}}=10^{-3}/10^{-2}=0.1$ . Each level squares it (since $t=1$ ), and undoing the normalization gives $p_\ell=p_{\mathrm{th}}\,x_0^{2^\ell}=10^{-2}\cdot(0.1)^{2^\ell}$ .

Step 2. Tabulate the cascade — each level roughly doubles the number of nines:

level $\ell$	$x_\ell=(0.1)^{2^\ell}$	$p_\ell=10^{-2}x_\ell$
0	$10^{-1}$	$10^{-3}$
1	$10^{-2}$	$10^{-4}$
2	$10^{-4}$	$10^{-6}$
3	$10^{-8}$	$10^{-10}$
4	$10^{-16}$	$10^{-18}$

Step 3. Read off the level count. Level 3 gives $p_3=10^{-10}>\varepsilon$ ; level 4 gives $p_4=10^{-18}\le10^{-15}$ . So $L=4$ levels suffice. Equivalently $2^L\ge\log(p_{\mathrm{th}}/\varepsilon)/\log(p_{\mathrm{th}}/p)=13/1=13$ , and $2^4=16\ge13$ while $2^3=8<13$ — the same answer from the inversion formula.

Step 4. Count the qubits: $N=n^L=7^4=\mathbf{2401}$ physical qubits per logical qubit, and the code distance is $d_L\ge3^4=81$ . Four levels, 2401 physical qubits, buy a fifteen-orders-of-magnitude logical error — a vivid illustration of doubly-exponential return: the qubit count grew by a factor of 7 per level while the error was squared each time.

Physics of the portrait

Code concatenation is where an engineering worry — "won't the errors in the error-correction circuitry just add up?" — was answered by a theorem. The person most identified with that answer, the constructive threshold theorem built on concatenated codes, is Dorit Aharonov, whose work with Michael Ben-Or turned a plausibility argument into a proof that a constant physical error rate is enough.

Origins · 1 minDorit Aharonov and how this was discovered

Dorit Aharonov

born 1970, Israeli computer scientist · fault-tolerant quantum computation and the threshold theorem

Dorit Aharonov, working with Michael Ben-Or at the Hebrew University of Jerusalem, proved in 1997 the result that made quantum error correction into quantum fault tolerance: if the physical error rate per gate is below a fixed constant, then arbitrarily long quantum computations can be carried out reliably, with only polylogarithmic overhead — the threshold theorem. Their vehicle was code concatenation. Peter Shor had shown a year earlier that error correction survives noisy recovery operations, but the crucial and unobvious step was to iterate: encode the physical qubits, then treat each encoded block as a physical qubit and encode again, recursively, so that the failure probability of a level- $L$ gadget is the square of the level- $(L-1)$ probability. Aharonov and Ben-Or made rigorous the accounting that a single fault in a well-designed gadget can propagate to at most one error per block, so that the recursion is genuinely quadratic and the doubly-exponential suppression is real — closing the loophole that noisy syndrome extraction might destroy the very thing it protects. The theorem was proved independently and almost simultaneously by Emanuel Knill, Raymond Laflamme, and Wojciech Zurek, by Alexei Kitaev, and by John Preskill, a convergence that gave the community confidence the result was fundamental rather than an artifact of one construction. Aharonov, later a professor at the Hebrew University, went on to shape quantum complexity theory — adiabatic quantum computation, quantum walks, and the computational-hardness underpinnings of quantum supremacy experiments — but the threshold theorem remains the load-bearing result on which the entire enterprise of scalable quantum computing rests: it is the reason building a quantum computer is an engineering problem and not a fantasy.

History

1995

— Shor's nine-qubit code exhibits the first concatenated quantum code

1996

— Knill and Laflamme develop the general theory of concatenated codes and thresholds

1997

— Aharonov and Ben-Or prove fault-tolerant computation at a constant error rate

1998

— Kitaev, Knill–Laflamme–Zurek, and Preskill give independent threshold proofs

2005

— Knill's postselected concatenation scheme pushes estimated thresholds toward one percent

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §10.6 (fault-tolerant quantum computation and the threshold theorem) · Preskill, Lecture Notes on Quantum Computation, Ch. 7 (quantum error correction) · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, §§14–15 · Gottesman, An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation (2009) · Aharonov & Ben-Or, Fault-Tolerant Quantum Computation with Constant Error Rate, SIAM J. Comput. 38 (2008) · Knill, Laflamme & Zurek, Resilient Quantum Computation, Science 279 (1998). All relations here are standard and scheme-independent in form: the level recursion $p_{\ell+1}=c\,p_\ell^{t+1}$ , the fixed point $p_{\mathrm{th}}=c^{-1/t}$ , the doubly-exponential bound $p_L\le c^{-1/t}(p/p_{\mathrm{th}})^{(t+1)^L}$ , distance multiplication $d_L\ge d^L$ , and overhead $N=n^L$ . The leading binomial term is $c=\binom{n}{t+1}$ ; the fixed point solves $x=cx^{t+1}$ and satisfies $f'(p_{\mathrm{th}})=t+1>1$ ; the normalized map collapses to $x\mapsto x^{t+1}$ ; and the level count is $L=O(\log\log(1/\varepsilon))$ with polylog overhead. No universal numerical threshold is quoted because $p_{\mathrm{th}}$ is scheme-dependent; the worked example's $p_{\mathrm{th}}=10^{-2}$ is illustrative. The Shor codeword normalization $1/(2\sqrt2)$ and the concatenation $[[9,1,3]]=[[3,1,3]]_Z\circ[[3,1,3]]_X$ are verified in the worked example.

Prerequisites. Discretization of Errors · Code Distance and Logical Operators · Stabilizer Formalism · Syndrome Measurement and Decoding · Shor Nine-Qubit Code. Leads to. CSS Codes · Quantum Hamming and Singleton Bounds · Knill–Laflamme Conditions.

Ask the tutor: Ask me to walk through the doubly-exponential cascade for your own $p$ and $p_{\mathrm{th}}$ , or to show exactly how a single ancilla fault turns the quadratic recursion linear.

Why does concatenation give doubly-exponential suppression, not just exponential?

Because each level does not add protection — it composes it. An exponential suppression would come from a map like $p\mapsto p/2$ repeated $L$ times, giving $p\,2^{-L}$ : linear in $1/p$ per level. Concatenation's map is $p\mapsto c\,p^2$ , which squares the (normalized) error each level, so after $L$ levels the exponent is $2^L$ , not $L$ . Squaring a number below one and then squaring the result races to zero far faster than halving it repeatedly. That is why only $L\sim\log\log(1/\varepsilon)$ levels are needed: the double logarithm is the inverse of the double exponential.

What actually determines the value of the threshold p_th?

Everything about the fault-tolerant scheme except the raw hardware rate $p$ : the base code and its distance, the decoder, and — most sensitively — the design of the gadgets that perform gates, state preparation, measurement, and especially syndrome extraction. The constant $c$ that sets $p_{\mathrm{th}}=c^{-1/t}$ counts the malignant sets of fault locations that conspire to cause a logical error, and a cleverer gadget with fewer malignant pairs has a smaller $c$ and hence a higher threshold. This is why two schemes using the same code can quote thresholds differing by orders of magnitude, and why $p_{\mathrm{th}}$ must be established by a careful (often numerical) fault-counting analysis, not read off the code parameters.

Is the code-capacity estimate p_th ≈ 1 over C(n, t+1) the real threshold?

No — it is an optimistic upper bound. Taking $c=\binom{n}{t+1}$ gives, for the Steane code, $c=\binom{7}{2}=21$ and $p_{\mathrm{th}}\approx0.05$ , but that counts only faults on the data qubits under a perfect decoder and perfect gadgets ("code capacity"). The realistic circuit-level threshold, which counts faults in every gate, ancilla, and measurement of the actual syndrome-extraction circuit, is far lower — historically estimated around $10^{-4}$ to $10^{-5}$ for concatenated Steane, later pushed toward $10^{-3}$ – $10^{-2}$ with better gadgets and postselection. The gap between the two numbers is precisely the cost of doing error correction with faulty hardware, and closing it is what fault-tolerant gadget design is about.

Does concatenation require using the same code at every level?

Not at all — and the most important codes do not. The definition only needs the outer code's physical qubits to be the inner code's logical qubits; the two codes can differ. The Shor code concatenates a phase-flip code with a bit-flip code. Biased-noise architectures concatenate an inner cat code (killing bit flips) with an outer surface code (handling the rest). Magic-state distillation concatenates a distillation routine with itself on states. Self-concatenation — the same code at every level — is the cleanest case for proving the threshold theorem and gives the tidy $d_L\ge d^L$ and $N=n^L$ , but heterogeneous concatenation, tailoring each layer to the job it does best, is usually the better engineering.

If concatenation proves the threshold theorem, why is everyone building surface codes?

Because the threshold theorem is an existence proof, not an efficiency claim. Concatenated codes have relatively low thresholds and require long-range connectivity between blocks at higher levels, which is awkward for planar superconducting hardware. The surface code trades the analytic elegance for a ~1% threshold, a strictly two-dimensional nearest-neighbour layout, and a simple decoder — enormous practical advantages even though its overhead is polynomial in $1/\varepsilon$ rather than polylogarithmic. Concatenation remains the cleanest proof of the threshold and, with modern high-rate constructions and biased-noise cat concatenations, is re-emerging as a competitive design. The two are complementary: one is how you prove reliability is possible, the other is how many groups currently pursue it.

How does concatenation interact with performing gates, not just storing qubits?

It has to, or it would only protect memory. The key is transversal gates: a logical gate implemented as one physical gate per qubit, $\bar U=U^{\otimes n}$ , so that a fault in one physical gate causes at most one error per block — exactly the fault-tolerance condition the recursion needs. Transversality is inherited under concatenation: if $\bar U$ is transversal at level 1, applying it transversally on the level-1 blocks makes it transversal at level 2, and so on up the hierarchy. The catch is the Eastin–Knill theorem: no code has a transversal universal gate set, so at least one gate (usually the non-Clifford $T$ ) must be supplied another way — which is where magic-state distillation, itself a concatenation, re-enters to complete the universal fault-tolerant toolbox.