Logical Qubit and Resource Overhead

A logical qubit is the unit of information a quantum algorithm actually manipulates once error correction is switched on. Physically it is not a single two-level system but a two-dimensional subspace $\mathcal{C}\subset(\mathbb{C}^2)^{\otimes n}$ — the code space — spanned by encoded basis states $\lvert 0_L\rangle$ and $\lvert 1_L\rangle$ . Every piece of machinery in this chapter — stabilizers, syndrome extraction, decoding — exists to hold an arbitrary encoded state $\alpha\lvert 0_L\rangle+\beta\lvert 1_L\rangle$ steady against the continuous decoherence of the underlying hardware. The question that decides whether a fault-tolerant machine can ever be built is the resource overhead: how many physical qubits, how many time steps, and how many auxiliary operations must be spent per logical qubit and per logical gate to reach a target logical fidelity. Two numbers govern everything. The code distance $d$ — the minimum weight of a logical operator — fixes how many errors are correctable, $t=\lfloor(d-1)/2\rfloor$ . The accuracy threshold $p_{\mathrm{th}}$ is the physical error rate below which adding correction resources monotonically helps: when $p<p_{\mathrm{th}}$ the logical failure rate collapses like a high power of $p/p_{\mathrm{th}}$ , and $p_L$ can be driven arbitrarily low by enlarging $d$ at a cost growing only polylogarithmically in $1/p_L$ . Overhead is genuinely three-dimensional — space (physical-to-logical ratio $n/k$ , roughly $2d^2$ for the surface code), time ( $\Theta(d)$ rounds of syndrome extraction per logical cycle), and the dominant hidden cost of fault-tolerant non-Clifford gates, produced by magic-state factories that can swallow most of a machine. The threshold theorem ties these into a single guarantee: any $N$ -gate circuit runs to failure $\varepsilon$ in $O(N\,\mathrm{polylog}(N/\varepsilon))$ operations once $p<p_{\mathrm{th}}$ — the price of fault tolerance is paid in overhead, not in complexity.

Key takeaways

A logical qubit is a two-dimensional code subspace of many physical qubits, protected so that an arbitrary single-qubit logical operation runs with a logical error rate $p_L$ far below the physical rate $p$ .
Below the accuracy threshold $p_{\mathrm{th}}$ , a distance- $d$ code suppresses logical error as $p_L\approx A\,(p/p_{\mathrm{th}})^{\lfloor(d+1)/2\rfloor}$ : each two units of distance buy another factor of $p/p_{\mathrm{th}}$ at fixed hardware quality.
Space overhead is $n\approx 2d^2$ physical qubits per logical qubit for the surface code, giving overhead $\sim\log^2(1/p_L)$ ; time overhead is $\Theta(d)$ syndrome-extraction rounds per logical cycle.
The third and usually dominant axis is magic-state distillation for non-Clifford gates: the Eastin–Knill theorem blocks a transversal universal gate set, so the $T$ gate is distilled at $p_{\mathrm{out}}\approx 35\,p_{\mathrm{in}}^3$ per round in factories that often outweigh the data block.
The threshold theorem guarantees an ideal $N$ -gate computation is simulable to failure $\varepsilon$ with $\mathrm{poly}(\log(N/\varepsilon))$ overhead per gate, provided $p<p_{\mathrm{th}}$ .
Concrete scale: factoring a 2048-bit RSA modulus is estimated at $\sim 10^7$ physical qubits at $p\sim 10^{-3}$ — the overhead, not the algorithm, sets feasibility.
Key idea: A logical qubit is a code subspace whose effective error rate $p_L$ can be driven exponentially below the physical rate $p$ by increasing the code distance $d$ — but only when $p<p_{\mathrm{th}}$ , and at a physical-qubit and time cost that grows like a power of $\log(1/p_L)$ .

Where this lives today

Resource overhead is no longer only a theorem; it is the number every hardware roadmap is judged against. In 2023 Google's Quantum AI team ran a surface code at distances 3 and 5 and reported that the distance-5 logical qubit had a lower error rate than the distance-3 one — the first convincing demonstration of the below-threshold signature $p_L(d{+}2)<p_L(d)$ in a solid-state device, later extended toward distance 7. Neutral-atom and trapped-ion platforms (QuEra, Quantinuum) have since produced dozens of logical qubits and run small encoded algorithms, each result reported in the currency of this article: physical-to-logical ratio, logical error per cycle, and $T$ -gate budget. On the estimation side, Gidney and Ekerå's 2019 analysis put a sharp number on the old $10^7$ – $10^8$ folklore: factoring a 2048-bit RSA key would take about 20 million noisy physical qubits and 8 hours at $p\sim 10^{-3}$ , with the magic-state factories consuming a large share of the footprint — a figure that has driven both the "harvest-now, decrypt-later" urgency in post-quantum cryptography and an intense hunt for cheaper distillation and higher-rate quantum-LDPC codes that could slash the overhead by orders of magnitude.

The physical picture

Think of a logical qubit as a message written redundantly across many sheets of paper, where no single sheet carries the message. To corrupt it an adversary must alter at least $d$ sheets at once; if each sheet is independently smudged with probability $p$ , an uncorrectable pattern of $\geq\lceil d/2\rceil$ smudges appears with probability $\sim p^{\lceil d/2\rceil}$ , tiny for small $p$ . Adding sheets — increasing $d$ — pushes that failure probability down exponentially. The first figure makes the redundancy concrete: a distance-5 surface-code patch, one logical qubit spread across about $2d^2=50$ physical qubits, whose logical operators are error chains that must span the whole patch.

Figure

A distance-5 rotated surface-code patch encodes one logical qubit in about 2d² = 50 physical qubits (25 data plus 24 syndrome ancilla) and corrects any t = 2 physical errors; the logical X operator is a horizontal chain of weight d = 5 and the logical Z a vertical chain of weight 5

The threshold is a tipping point. Each layer of protection removes errors but also introduces fresh opportunities for error in its own circuitry. If physical components are good enough ( $p<p_{\mathrm{th}}$ ) each added layer removes more than it adds and protection compounds; if they are too noisy ( $p>p_{\mathrm{th}}$ ) the correction machinery injects more errors than it fixes and bigger codes are strictly worse. The entire feasibility of scalable quantum computing hinges on living below that line. The second figure is the operational signature: logical error rate versus code distance for several fixed physical error rates. Below threshold the curves fan downward, exponentially in $d$ ; above threshold they turn upward — the same picture experimental teams now measure to certify a working logical qubit.

Figure

Logical error rate p_L versus code distance d at fixed physical error, from p_L ≈ A(p/p_th)^⌊(d+1)/2⌋ with p_th = 10⁻². Below threshold (p = 0.1 p_th and p = 0.3 p_th) each added unit of distance drives p_L down; above threshold (p = 2 p_th) more distance makes p_L worse — the defining signature of the accuracy threshold

Overhead is the toll for that exponential suppression, and the hardest part of the toll is hidden in the gates. Clifford operations can often be done transversally — bitwise, error-spread-free — but a universal set needs something like the $T$ gate, which no useful code implements transversally (Eastin–Knill). Producing fault-tolerant $T$ gates means manufacturing and purifying special magic states in dedicated factories, and those factories, not the data qubits, typically set the qubit count and runtime of a real machine.

The core equations

A logical qubit is defined not by hardware but by a subspace. The code space is the two-dimensional protected corner of a many-qubit Hilbert space in which the encoded information lives, and every stabilizer measurement is a check that the state has not left it.

\mathcal{C}=\mathrm{span}\{\lvert 0_L\rangle,\lvert 1_L\rangle\}\subset(\mathbb{C}^2)^{\otimes n},\qquad \dim\mathcal{C}=2 \qquad (1)

where: $\mathcal{C}$ — code space, the protected two-dimensional subspace; $n$ — physical qubits in the encoding block; $\lvert 0_L\rangle,\lvert 1_L\rangle$ — encoded (logical) computational basis states. Reading: the "qubit" the algorithm sees is this subspace, not any single physical device. A code is labelled by its three parameters and the number of errors it is guaranteed to fix. The correctable weight follows directly from the distance: to certainly undo any error you need enough distance that the true error is the closest one to the observed syndrome.

[[n,k,d]]:\quad t=\left\lfloor\frac{d-1}{2}\right\rfloor \qquad (2)

where: $k$ — logical qubits encoded (dimension $2^k$ ); $d$ — code distance, the minimum weight of a nontrivial logical operator; $t$ — number of arbitrary single-qubit errors correctable with certainty. Reading: distance $d$ buys correction of $t=\lfloor(d-1)/2\rfloor$ errors, so $d=3$ corrects one, $d=5$ corrects two. Below threshold the logical error rate is set by the lightest uncorrectable fault. That fault has weight $t+1$ , so its probability — and hence $p_L$ — scales as $p$ raised to that power, normalized by the threshold.

p_L\;\approx\;A\left(\frac{p}{p_{\mathrm{th}}}\right)^{\lfloor(d+1)/2\rfloor} \qquad (3)

where: $p_L$ — logical error rate per logical operation; $p$ — physical error rate; $p_{\mathrm{th}}$ — accuracy threshold; $A$ — $O(1)$ prefactor counting fault configurations. Reading: the exponent is $t+1=\lfloor(d+1)/2\rfloor$ , so two extra units of distance multiply $p_L$ by another factor $p/p_{\mathrm{th}}$ . The sign of the distance-derivative is what separates a useful code from a harmful one. It flips exactly at the threshold, which is why $p_{\mathrm{th}}$ is the number that decides whether error correction is worth doing on given hardware.

\frac{\partial p_L}{\partial d}<0\iff p<p_{\mathrm{th}} \qquad (4)

where: $\partial p_L/\partial d$ — the marginal change in logical error from one more unit of distance. Reading: below threshold more distance helps; above it, more distance hurts; at $p=p_{\mathrm{th}}$ distance is neutral. Turning distance into a hardware bill needs a geometry. For the planar surface code the patch is roughly square, so its qubit count grows as the area $d^2$ , and inverting equation (3) makes the required distance grow only logarithmically in $1/p_L$ .

n_{\mathrm{surf}}\approx 2d^2\;\Rightarrow\;n_{\mathrm{surf}}=O\!\big(\log^2(1/p_L)\big) \qquad (5)

where: $n_{\mathrm{surf}}$ — physical qubits per logical qubit (data plus ancilla) in the planar surface code. Reading: the space overhead is polylogarithmic in the target error rate — cheap asymptotically, but a factor of $\sim 10^3$ for the distances of a real machine. Fault tolerance costs time as well as qubits. A single logical operation is not one round of measurement but $\Theta(d)$ rounds, so that a measurement error occurring partway through decoding is itself outvoted by the majority.

T_{\mathrm{cycle}}=\Theta(d)\,\tau_{\mathrm{rd}} \qquad (6)

where: $T_{\mathrm{cycle}}$ — wall-clock duration of one fault-tolerant logical operation; $\tau_{\mathrm{rd}}$ — duration of one syndrome-extraction round; $\Theta(d)$ — rounds needed so measurement errors are themselves correctable. Reading: the logical clock is slower than the physical clock by a factor that itself grows with the distance. The threshold theorem packages all of this into a single asymptotic statement. It says the per-gate overhead grows only polylogarithmically with the size of the computation, so fault tolerance never changes an algorithm's complexity class.

C_{\mathrm{total}}=O\!\big(N\cdot\mathrm{polylog}(N/\varepsilon)\big) \qquad (7)

where: $C_{\mathrm{total}}$ — total physical operations to simulate the ideal circuit; $N$ — ideal circuit size (gate count); $\varepsilon$ — tolerated total failure probability. Reading: correcting errors multiplies the work by a mere polylogarithm — the mathematical content of "fault tolerance is affordable." The universal gate that no code hands you for free is manufactured by distillation. The 15-to-1 protocol consumes fifteen noisy magic states and outputs one that is cubically cleaner, because its $[[15,1,3]]$ code needs three simultaneous input faults to fail undetectably.

p_{\mathrm{out}}\approx 35\,p_{\mathrm{in}}^{3} \qquad (8)

where: $p_{\mathrm{in}}$ — error rate of input (noisy) magic states; $p_{\mathrm{out}}$ — error rate of the single distilled output. Reading: each round cubes the error (with a factor 35 counting the weight-3 failure patterns), so two rounds take $10^{-3}\to 10^{-8}\to 10^{-21}$ . Finally, the honest measure of cost is neither pure space nor pure time but their product — the spacetime volume, the resource that a compiler for a fault-tolerant machine actually minimizes.

\text{Overhead}\equiv\frac{\text{physical qubit-seconds}}{\text{logical qubit-seconds}}\sim n\cdot\frac{T_{\mathrm{cycle}}}{\tau_{\mathrm{rd}}} \qquad (9)

where: $n$ — physical qubits per logical qubit; $T_{\mathrm{cycle}}/\tau_{\mathrm{rd}}$ — syndrome rounds per logical operation. Reading: a logical operation costs $\sim n\cdot d$ physical qubit-rounds, and it is this product — dominated in practice by magic-state factories — that sizes a machine.

Derivation AWhy the logical error rate scales as p to the t plus one

The goal is to explain the single most important scaling in this article — that a distance- $d$ code suppresses logical error as $p^{\lfloor(d+1)/2\rfloor}$ rather than $p^{d}$ — by tracing it to the weight of the lightest fault the decoder cannot undo, and to show why the exponent is governed by correction (half the distance) and not by detection (the full distance). We count fault configurations combinatorially, keep only the dominant power of $p$ , and fold the rest into the prefactor $A$ and the threshold $p_{\mathrm{th}}$ .

Step 1. A distance- $d$ code corrects every error whose weight is at most $t=\lfloor(d-1)/2\rfloor$ , because any two such errors produce distinguishable syndromes and the true error is the unique lightest one consistent with what is measured. The lightest error the decoder can misidentify therefore has weight $t+1=\lfloor(d+1)/2\rfloor$ . Why: correction, unlike mere detection, must pin the error uniquely, and unique decoding fails first at half the distance — this is where the factor of two between $d$ and the exponent is born.

Step 2. With $N_{\mathrm{loc}}$ independent fault locations each failing with probability $p$ , the chance of a specific weight- $m$ fault is $\binom{N_{\mathrm{loc}}}{m}p^m(1-p)^{N_{\mathrm{loc}}-m}$ , so the probability of an uncorrectable event is dominated by its lightest term, $m=t+1$ , giving $p_L\sim \binom{N_{\mathrm{loc}}}{t+1}p^{t+1}$ . Why: for small $p$ the sum over uncorrectable weights is controlled by its lowest power of $p$ ; heavier faults are suppressed by additional factors of $p$ and can be neglected to leading order.

Step 3. Absorb the binomial and gadget-dependent constants into a prefactor $A$ and define the crossover scale $p_{\mathrm{th}}$ where the geometric series stops converging, so the estimate takes the universal form $p_L\approx A\,(p/p_{\mathrm{th}})^{t+1}$ with $t+1=\lfloor(d+1)/2\rfloor$ . Why: writing the ratio $p/p_{\mathrm{th}}$ rather than $p$ alone exposes the threshold structure directly — the suppression is exponential in $d$ if and only if the base is below one. *Verified: $t=\lfloor(d-1)/2\rfloor$ gives exponents $2,3,4$ for $d=3,5,7$ ; matches equation (3) and Preskill Ch. 7.*

Go deeper · Derivation B · 2 minThreshold from one level of concatenation

Derivation BThreshold from one level of concatenation

The goal is to derive the accuracy threshold and the doubly-exponential suppression of concatenated codes from a single recursion, showing that a distance-3 gadget used inside itself renormalizes the physical error $p$ to $Cp^2$ , that this contracts precisely when $p<1/C$ , and that iterating $L$ levels squares the error ratio each time while costing only a polylogarithmic number of physical qubits per logical qubit. This is the original route (Aharonov–Ben-Or, Knill–Laflamme–Zurek) by which the threshold theorem was first proven.

Step 1. Encode each qubit and gate of a circuit into a distance-3 code that corrects one fault; a level-1 logical location fails only if at least two of its constituent physical locations fail, so with $C$ malignant pairs the level-1 error is $p^{(1)}\le C\,p^2$ . Why: single faults are corrected by construction, so the leading failure is a coincidence of two faults — the $p^2$ that makes recursion contract.

Step 2. Define the threshold as the fixed point of the recursion by writing $p^{(1)}=p^2/p_{\mathrm{th}}$ with $p_{\mathrm{th}}=1/C$ ; then $p^{(1)}<p$ exactly when $p<p_{\mathrm{th}}$ , so below threshold one level of encoding already reduces the error. Why: the map $p\mapsto p^2/p_{\mathrm{th}}$ has an unstable fixed point at $p=p_{\mathrm{th}}$ ; starting below it flows to zero, starting above it flows to one — the sharp all-or-nothing character of fault tolerance.

Step 3. Concatenate $L$ levels, encoding the logical qubits of one level into the next; the ratio $p^{(L)}/p_{\mathrm{th}}=(p^{(L-1)}/p_{\mathrm{th}})^2$ squares at every level, so $p^{(L)}=p_{\mathrm{th}}\,(p/p_{\mathrm{th}})^{2^L}$ — the error falls doubly-exponentially in the number of levels. Why: squaring a number below one $L$ times drives it to zero with breathtaking speed, which is why only a handful of levels reach any realistic target.

Step 4. A block of $n_0$ physical qubits per encoded qubit costs $n_0^{L}$ physical qubits per logical qubit after $L$ levels; inverting the boxed suppression for a target $p_L$ gives $L\sim\log_2[\log(p_{\mathrm{th}}/p_L)/\log(p_{\mathrm{th}}/p)]$ , only doubly-logarithmic in $1/p_L$ , so $n_0^{L}=\mathrm{polylog}(1/p_L)$ . Why: because the required level count grows so slowly, the exponential-looking $n_0^L$ collapses to a mere polylogarithm — the overhead heart of the threshold theorem.

p^{(L)}=p_{\mathrm{th}}\left(\frac{p}{p_{\mathrm{th}}}\right)^{2^{L}},\qquad p_{\mathrm{th}}=\frac{1}{C}

Verified: reproduces Aharonov–Ben-Or / Preskill Ch. 7 — contraction at $p<1/C$ , doubly-exponential suppression, and $\mathrm{polylog}(1/p_L)$ overhead.

Go deeper · Derivation C · 2 minSizing a fault-tolerant computer from an algorithm

Derivation CSizing a fault-tolerant computer from an algorithm

The goal is to convert an algorithm's abstract demand — some number $N_T$ of logical $T$ gates, all of which must succeed — into a concrete surface-code distance and physical-qubit budget, and to expose in the process why the magic-state factories rather than the data qubits set the size of a useful machine. We union-bound the failure probability, invert the surface-code error formula for the required distance, multiply by the per-qubit footprint, and add the distillation overhead.

Step 1. For the whole computation to succeed with probability at least one half, a union bound over its $N_T$ logical operations requires each to fail with probability $p_L\lesssim 1/(2N_T)$ , so a computation with $N_T\sim 10^{10}$ operations needs $p_L\lesssim 5\times 10^{-11}$ per logical gate. Why: errors add to leading order, so the per-operation budget shrinks in proportion to the circuit size — deeper algorithms demand exponentially reliable logical qubits.

Step 2. Invert the surface-code error law $p_L\approx A(p/p_{\mathrm{th}})^{(d+1)/2}$ to get $d\approx 2\log(A/p_L)/\log(p_{\mathrm{th}}/p)$ ; at $p=10^{-3}$ and $p_{\mathrm{th}}=10^{-2}$ the denominator is $\log 10$ , so hitting $p_L\sim 10^{-11}$ takes $d$ of order $20$ – $25$ . Why: the required distance grows only logarithmically in the target error, which is why even trillion-operation algorithms need distances of a few dozen, not a few thousand.

Step 3. Each logical data qubit then occupies $n_{\mathrm{data}}\approx 2d^2$ , on the order of $10^3$ physical qubits for $d\approx 25$ ; a machine holding a few thousand logical qubits already needs several million physical qubits for data alone. Why: the quadratic area cost turns a modest distance into a thousand-fold qubit multiplier — the price of a two-dimensional layout.

Step 4. Sustaining the algorithm's $T$ -rate requires magic-state factories, each itself many logical qubits, running in parallel to feed the data block; these typically multiply the data footprint by an order of magnitude, yielding the widely-quoted $\sim 10^7$ physical qubits for cryptographically relevant factoring at $p\sim 10^{-3}$ . Why: because non-Clifford gates cannot be transversal, the factories are unavoidable and dominant — the overhead, not the circuit, is the bottleneck.

p_L\lesssim\frac{1}{2N_T}\;\Rightarrow\;d\gtrsim\frac{2\log(2N_T A)}{\log(p_{\mathrm{th}}/p)}

Verified: consistent with Fowler et al. (2012) surface-code estimates and Gidney–Ekerå (2019) factoring figures; numbers are order-of-magnitude and depend on $p$ , layout, and distillation choice.

Limiting cases

How the logical error rate and overhead behave in the characteristic regimes:

Case	Result	Meaning
Deep sub-threshold	$p\ll p_{\mathrm{th}}\Rightarrow p_L\approx A\left(\frac{p}{p_{\mathrm{th}}}\right)^{\lfloor(d+1)/2\rfloor}$	Logical error falls super-exponentially in $d$ ; modest distances suffice and overhead is dominated by gate (magic-state) cost, not memory.
Near threshold	$p\to p_{\mathrm{th}}^{-}\Rightarrow p_L$ nearly $d$ -independent	Adding distance barely helps; the $d$ needed for a target $p_L$ diverges, so overhead blows up. Hardware must be pushed well below $p_{\mathrm{th}}$ .
Above threshold	$p>p_{\mathrm{th}}\Rightarrow \frac{\partial p_L}{\partial d}>0$	Larger codes make things worse: the correction machinery injects more error than it removes. No overhead yields a usable logical qubit.
Asymptotic guarantee	overhead/gate $=O\!\big(\mathrm{polylog}(N/\varepsilon)\big)$	For a size- $N$ circuit and target failure $\varepsilon$ , total cost is $N\,\mathrm{polylog}(N/\varepsilon)$ when $p<p_{\mathrm{th}}$ ; overhead grows only polylogarithmically in problem size.

Common trapOne logical qubit equals 2d² physical qubits is the whole cost

Counting only the data-block qubits dramatically understates the real footprint. The $2d^2$ figure is a space-only snapshot of memory; it omits the $\Theta(d)$ syndrome-extraction rounds per logical cycle (time overhead) and, far more importantly, the magic-state distillation factories that supply the non-Clifford gates. In realistic resource estimates those factories consume a large fraction — often the majority — of the machine's qubits and runtime, because every $T$ gate demands a freshly distilled state and the distilleries are themselves sizeable fault-tolerant circuits. The honest cost of a computation is the spacetime volume of equation (9), dominated by distillation, not the static qubit count of one idle logical qubit.

Worked examples

1 · Sizing a logical qubit for a target error rate (fully worked)

Hardware runs at physical error $p=10^{-3}$ with a surface-code threshold $p_{\mathrm{th}}=10^{-2}$ and prefactor $A\approx 0.1$ . What distance is needed for a logical error $p_L=10^{-12}$ per cycle, and how many physical qubits does that logical qubit cost?

Step 1. Write the suppression law with the given numbers: $p_L\approx A(p/p_{\mathrm{th}})^{(d+1)/2}=0.1\times(0.1)^{(d+1)/2}$ , since $p/p_{\mathrm{th}}=10^{-3}/10^{-2}=0.1$ . The base is one-tenth, so every two units of distance gain one decade.

Step 2. Solve for the distance: $10^{-12}=0.1\times(0.1)^{(d+1)/2}$ gives $(0.1)^{(d+1)/2}=10^{-11}$ , hence $(d+1)/2=11$ and $\mathbf{d=21}$ . A distance-21 patch corrects $t=\lfloor 20/2\rfloor=\mathbf{10}$ physical errors.

Step 3. Convert to qubits with the surface-code area law: $n\approx 2d^2=2\times 21^2=2\times 441=\mathbf{882}$ physical qubits, of which $\approx d^2=441$ are data and $\approx 441$ are syndrome ancilla. So a single logical qubit at $p_L=10^{-12}$ costs roughly 900 physical qubits — and that is memory only, before any factory. d = 21, t = 10, n ≈ 882 physical qubits per logical qubit.

2 · Purifying magic states by distillation (fully worked)

A device produces raw magic states at error $p_{\mathrm{in}}=10^{-3}$ . How clean is the output after one round of 15-to-1 distillation, and after two? What is the raw-state cost of a twice-distilled output?

Step 1. One round applies $p_{\mathrm{out}}\approx 35\,p_{\mathrm{in}}^3=35\times(10^{-3})^3=35\times 10^{-9}=\mathbf{3.5\times 10^{-8}}$ . A single round already carries $10^{-3}$ to below $10^{-7}$ — a cubic gain.

Step 2. Feed those outputs into a second round: $p_{\mathrm{out}}'\approx 35\,(3.5\times 10^{-8})^3=35\times 4.29\times 10^{-23}\approx\mathbf{1.5\times 10^{-21}}$ , deep below anything an algorithm needs. Each round cubes the exponent, so the error plummets triple-exponentially in rounds.

Step 3. Count the raw states: one round needs 15 inputs per output, so a twice-distilled state needs $15^2=\mathbf{225}$ raw magic states (before accounting for discarded rejected batches). This is the qubit-time the factory spends per usable $T$ gate — the reason distillation dominates the resource budget. One round: 3.5×10⁻⁸; two rounds: 1.5×10⁻²¹; cost 225 raw states per output.

3 · Does adding distance help this hardware? (decision)

One team runs at $p=2\times 10^{-2}$ , another at $p=2\times 10^{-3}$ ; both use a code with $p_{\mathrm{th}}=10^{-2}$ . For each, does going from $d=5$ to $d=7$ lower the logical error?

Step 1. Team A has $p=2\times 10^{-2}>p_{\mathrm{th}}=10^{-2}$ , so $p/p_{\mathrm{th}}=2>1$ . By equation (4) the derivative $\partial p_L/\partial d>0$ : raising $d$ from 5 to 7 raises $p_L$ (from $\sim(2)^3=8$ to $\sim(2)^4=16$ times the prefactor-threshold scale). No — more distance makes it worse.

Step 2. Team B has $p=2\times 10^{-3}<p_{\mathrm{th}}$ , so $p/p_{\mathrm{th}}=0.2<1$ ; going $d=5\to 7$ changes the exponent from 3 to 4, multiplying $p_L$ by $0.2$ , a five-fold improvement. Yes — each two units of distance cut $p_L$ by a factor of 5. The lesson: error correction is a threshold phenomenon, and Team A must first improve its hardware before any code can help.

Physics of the portrait

Fault-tolerant quantum computing has many parents, but one figure turned "qubits are hopelessly fragile" into "qubits are an engineering problem with a known price." Peter Shor built the first logical qubit and then proved that its overhead could be kept under control.

Origins · 1 minPeter Shor and how this was discovered

Peter Shor

born 1959 · fault-tolerant quantum computation and the threshold theorem

Peter Williston Shor is the applied mathematician whose 1994 factoring algorithm made quantum computers matter — and who, one year later, made them possible. The immediate objection to his algorithm was decoherence: a quantum state cannot be copied (no-cloning), so the classical trick of triplicating a bit seemed forbidden, and it was widely believed error correction was impossible in principle. In 1995 Shor demolished that belief with the first quantum error-correcting code, a nine-qubit encoding $[[9,1,3]]$ that protects one logical qubit against an arbitrary single-qubit error by digitizing continuous noise into discrete Pauli flips and correcting bit and phase errors separately. In 1996 he went further, showing in "Fault-Tolerant Quantum Computation" how to perform encoded gates and syndrome extraction without letting a single component failure cascade — the birth of fault-tolerant gadgets and transversal gates. Together with the threshold work of Aharonov and Ben-Or, Knill, Laflamme and Zurek, and Kitaev, this established the accuracy threshold theorem: below a critical physical error rate, arbitrarily long computations run at only polylogarithmic overhead. Shor, long at MIT, thereby converted the resource question from "can it be done?" to "how many qubits does it cost?" — the question this article answers. His codes and his threshold are the reason the phrase "logical qubit" means something buildable rather than a theorist's fiction.

History

1995

— Shor's nine-qubit code encodes the first logical qubit

1996

— Shor and, independently, Steane give fault-tolerant gadgets and the seven-qubit code

1997

— Aharonov, Ben-Or, Kitaev, and Knill–Laflamme–Zurek prove the accuracy threshold theorem

1997

— Kitaev introduces the toric and surface codes with topological protection

2005

— Bravyi and Kitaev give magic-state distillation for universal computation

2012

— Fowler, Mariantoni, Martinis, and Cleland publish practical surface-code resource estimates

2023

— Google demonstrates logical error falling as code distance grows from three to five

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, Ch. 10 (quantum error correction and fault tolerance) · Preskill, Lecture Notes on Quantum Computation, Ch. 7 (fault tolerance and the threshold) · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, Ch. 15 · Aharonov & Ben-Or, Fault-Tolerant Quantum Computation with Constant Error (1997) · Fowler, Mariantoni, Martinis & Cleland, Surface codes, Phys. Rev. A 86, 032324 (2012) · Bravyi & Kitaev, Universal quantum computation with ideal Clifford gates and noisy ancillas, Phys. Rev. A 71, 022316 (2005) · Gidney & Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2019).

Provenance. The logical-error scaling and concatenation threshold follow Preskill Ch. 7 and Aharonov–Ben-Or (1997); the surface-code $2d^2$ count and $\Theta(d)$ -round logical cycle follow Fowler et al. (2012); the $p_{\mathrm{out}}\approx 35\,p_{\mathrm{in}}^3$ result is Bravyi–Kitaev (2005). A verifier should recompute: the exponent $\lfloor(d+1)/2\rfloor$ from $t=\lfloor(d-1)/2\rfloor$ (giving $2,3,4$ for $d=3,5,7$ ); the concatenation recursion $p^{(L)}/p_{\mathrm{th}}=(p/p_{\mathrm{th}})^{2^L}$ ; the inversion $d\sim 2\log(1/p_L)/\log(p_{\mathrm{th}}/p)$ yielding $n=O(\log^2(1/p_L))$ ; the sizing arithmetic $10^{-12}=0.1\cdot(0.1)^{11}\Rightarrow d=21,\ n=2\cdot 21^2=882$ ; and the distillation chain $35(10^{-3})^3=3.5\times 10^{-8}$ , $35(3.5\times 10^{-8})^3\approx 1.5\times 10^{-21}$ . The $\sim 10^7$ -qubit factoring figure is order-of-magnitude and architecture-dependent (Gidney–Ekerå 2019).

Prerequisites. Quantum Error Model and Decoherence Channels · Code Distance and Logical Operators · Stabilizer Formalism · Syndrome Measurement and Decoding. Leads to. CSS Codes · Quantum Hamming and Singleton Bounds · Pauli Group and Clifford Group.

Ask the tutor: Want to work through the distance-and-qubit budget for a specific algorithm, or see why the magic-state factory usually outweighs the data block?

What exactly makes a logical qubit different from a physical qubit?

A physical qubit is a single two-level device; a logical qubit is a two-dimensional subspace $\mathcal{C}=\mathrm{span}\{\lvert 0_L\rangle,\lvert 1_L\rangle\}$ carved out of many physical qubits. The distinction matters because information stored in a subspace can be protected: an error must have weight at least $d$ (the code distance) to move an encoded state to another valid encoded state undetectably, whereas a single physical qubit is corrupted by any single fault. All the machinery of stabilizer codes exists to detect when a state has drifted out of $\mathcal{C}$ and to push it back without ever learning — and thereby collapsing — the encoded superposition itself.

Why does the logical error scale as p^⌊(d+1)/2⌋ and not p^d?

Because correction is harder than detection. A distance- $d$ code can detect up to $d-1$ errors, but to correct it must uniquely identify the fault, and unique decoding first fails at weight $t+1=\lfloor(d+1)/2\rfloor$ — roughly half the distance. The probability of that lightest uncorrectable event scales as $p^{t+1}$ , so that is the exponent that governs $p_L$ . The full distance $d$ would appear only if you merely wanted to notice errors (as in a detection or post-selection scheme), not to fix them on the fly. This factor of two is why a distance-5 code corrects two errors, not four.

What is the accuracy threshold, physically?

It is the physical error rate $p_{\mathrm{th}}$ at which error correction breaks even. Every layer of correction both removes errors from the data and adds new error opportunities in its own syndrome-extraction and decoding circuitry. Below $p_{\mathrm{th}}$ the removal wins, so bigger codes are better and $p_L$ can be driven to zero; above $p_{\mathrm{th}}$ the added errors win, so bigger codes are worse. Mathematically it is the unstable fixed point of the error-renormalization map $p\mapsto p^2/p_{\mathrm{th}}$ : start below and you flow to zero, start above and you flow to one. Realistic surface-code thresholds are around $1\%$ , which is why hardware aims for $p\sim 10^{-3}$ .

Why do magic states dominate the resource cost?

Because a universal gate set needs a non-Clifford gate such as $T$ , and the Eastin–Knill theorem forbids any code from implementing a universal set transversally — the one safe, error-spread-free way to apply gates. Clifford gates (which alone are not universal and are efficiently simulable classically) can often be transversal, but the $T$ gate cannot. The workaround is to prepare special "magic states" offline and consume them to teleport a $T$ into the data, and preparing them cleanly enough requires distillation factories running many rounds of protocols like 15-to-1. Those factories are large fault-tolerant circuits in their own right, and in full resource estimates they typically occupy more qubits and time than the data they serve.

If overhead is only polylogarithmic, why are the qubit counts so enormous?

Polylogarithmic is an asymptotic statement about how the cost grows, not a claim that the constant is small. The threshold theorem promises overhead $\sim\log^2(1/p_L)$ , but for a real algorithm $1/p_L$ must be around $10^{11}$ , and $2d^2$ with $d\approx 20$ – $30$ is already $\sim 10^3$ physical qubits per logical qubit. Multiply by thousands of logical qubits and by an order-of-magnitude factory overhead and you reach the millions. The theorem guarantees the cost does not blow up worse than polylogarithmically with problem size — it does not make the prefactor small. Reducing that prefactor, via better codes and cheaper distillation, is the central engineering effort today.

How is time overhead different from space overhead, and does it matter?

Space overhead is how many physical qubits one logical qubit occupies ( $\sim 2d^2$ ); time overhead is how many physical time steps one logical operation takes ( $\Theta(d)$ rounds of syndrome extraction). They are genuinely separate axes, and the honest cost is their product — the spacetime volume of equation (9). Time overhead matters because a logical clock cycle needs $\Theta(d)$ measurement rounds so that a measurement error occurring mid-decoding is itself outvoted; a distance-25 code therefore runs its logical gates roughly 25 times slower than its physical clock. When compilers optimize a fault-tolerant circuit they trade space against time — more factories run gates faster but cost qubits — minimizing volume, not either axis alone.

Could a different code make the overhead much smaller?

Possibly, and this is an active frontier. The surface code has a vanishing rate $k/n\to 0$ : each logical qubit needs its own $2d^2$ -qubit patch. Quantum low-density parity-check (qLDPC) codes achieve constant rate $k/n=\Theta(1)$ , packing many logical qubits into a shared block, which could cut memory overhead by one to two orders of magnitude. The catches are connectivity (good qLDPC codes need non-local qubit couplings) and gates (performing fault-tolerant logic and distillation on them is harder than on the geometrically clean surface code). The overhead framework of this article — space, time, and gate cost weighed against threshold and decoding complexity — is exactly what makes such code comparisons quantitative rather than a matter of taste.