# Fault-tolerance overhead for a quantum host

Thread: T3 fault-tolerance overhead, adversarial.  
Date: 2026-09-15.  
Scope: surface-code overhead, constant-overhead FT, lower bounds, and whether this term can carry a resource argument against a quantum host.

## 0. Bottom line first

The naive surface-code version of the argument is true but weak asymptotically: for fixed physical error rate below threshold, the code distance needed for a computation with G logical fault locations grows as O(log G), physical qubits per logical qubit grow as O((log G)^2), and surface-code spacetime overhead is polylogarithmic, not proportional to G or worse.

The stronger adversarial point is worse for the argument: constant-space-overhead FT is a real theorem under strong assumptions. It does not mean "no overhead". It means the physical/logical qubit ratio can be constant as the circuit width k goes to infinity, for circuit length bounded polynomially in k in the Gottesman/FGL theorem, with nonlocal LDPC-style connectivity and free/fast reliable classical computation. Later lower bounds show this cannot hold for arbitrary length at fixed width: any universal FT scheme against nonunitary iid noise needs at least max{Q(N)^(-1) n, alpha_N log T} physical qubits for width n and length T. But for a universe-scale computation whose width is enormous, log(10^183) is only about 608 bits, so that lower bound is swallowed immediately.

Verdict preview: fault-tolerance overhead is a real engineering term and a real constant/polylogarithmic multiplier. It is not a robust asymptotic resource obstruction to a quantum host unless you can independently constrain the host architecture, noise model, geometry, clock, and available width.

## 1. Surface code overhead

**VERIFIED.** Austin G. Fowler, Matteo Mariantoni, John M. Martinis, Andrew N. Cleland, "Surface codes: Towards practical large-scale quantum computation," *Physical Review A* 86, 032324 (2012), doi:10.1103/PhysRevA.86.032324, arXiv:1208.0928.

### 1.1 Exact logical-error formula in Fowler et al.

Fowler et al. simulate the surface-code stabilizer circuits including multiple error sources and state a threshold

```text
p_th = 0.57%
```

for the implementation in their Fig. 4. They define the error dimension for odd distance d as

```text
d_e = (d + 1)/2,
```

and for even d they round down, so `d_e = d/2`. Their empirical Eq. (11) is

```text
P_L ~= 0.03 (p / p_th)^(d_e).
```

This is a logical X error rate per surface-code cycle for the simulated array; their statistical model then gives a same-scaling data-qubit-only estimate

```text
P_L^s = d * d! / ((d_e - 1)! d_e!) * p_e^(d_e),
p_e ~= 8p,
```

where the factor d counts independent rows and `p_e` is the per-cycle individual error rate because there are eight steps per cycle. The formula to use for the requested p/p_th algebra is Eq. (11), not the rough folklore `0.1(100p)^((d+1)/2)` form.

### 1.2 Physical qubits per logical qubit

Fowler et al. plot the total number of data plus measurement qubits for a single logical array as

```text
n_q = (2d - 1)^2.
```

So physical qubits per protected logical qubit scale as

```text
n_q = 4d^2 - 4d + 1 = O(d^2).
```

They also give practical numbers: for p roughly at or below 10^-3, a logical qubit needs `10^3 - 10^4` physical qubits to reach logical error rates below `10^-14 - 10^-15`. In their factoring example, assuming an error rate about one-tenth threshold, they use about 14,500 physical qubits per logical qubit for a sufficiently low logical error rate, and most of the machine footprint is magic-state generation, not data qubits.

### 1.3 Distance as a function of total logical operations G

Use a union bound. If a computation has G logical fault locations and desired total failure probability at most epsilon, require

```text
G P_L <= epsilon,
P_L <= epsilon / G.
```

Plug Fowler Eq. (11), with `r = p/p_th < 1` and odd d:

```text
0.03 r^((d+1)/2) <= epsilon / G.
```

Rearrange carefully because `ln r < 0`:

```text
r^((d+1)/2) <= epsilon / (0.03 G)
((d+1)/2) ln r <= ln(epsilon / (0.03 G))
((d+1)/2) ln(p_th/p) >= ln(0.03 G / epsilon)
d >= 2 ln(0.03 G / epsilon) / ln(p_th/p) - 1.
```

Therefore, for fixed physical error p below threshold,

```text
d = O(log(G/epsilon)),
n_q = (2d - 1)^2 = O(log^2(G/epsilon)).
```

For the user's scale, take G = 10^183 and epsilon = 1. If `p = p_th/10`, then

```text
log10(0.03 * 10^183) = 181.477...
d >= 2 * 181.477 - 1 = 361.95,
```

so the next odd distance is about `d = 363`, giving

```text
n_q = (2*363 - 1)^2 = 525,625
```

data-plus-measurement physical qubits per logical array by Fowler's `(2d-1)^2` count. This is enormous engineering overhead, but it is not exponential in G. If `p = 10^-3` and `p_th = 0.0057`, the same algebra gives `d ~= 479` because p is only 5.7 times below threshold, not 10 times.

For total physical operations: surface-code logical operations have topological spacetime extent in d, and syndrome extraction repeats in code cycles. The safe asymptotic statement is that surface-code FT turns G logical operations into `G * polylog(G/epsilon)` physical fault locations for fixed p below threshold. It does not multiply G by another factor remotely comparable to G.

## 2. Constant-overhead fault tolerance: the thing that kills the strong version

### 2.1 Gottesman theorem

**VERIFIED.** Daniel Gottesman, "Fault-tolerant quantum computation with constant overhead," *Quantum Information & Computation* 14(15-16), 1338-1371 (2014), doi:10.26421/QIC14.15-16-5, arXiv:1310.2984. Venue/pages/DOI verified from the QIC publisher page; theorem text opened in the arXiv PDF.

Gottesman's abstract says exactly the dangerous sentence: "in the asymptotic limit of large circuits, the ratio of physical qubits to logical qubits can be a constant." The construction uses quantum LDPC codes; the overhead is asymptotically the inverse rate of the code family.

The main theorem, in operational terms:

- Let `Q_i` be a family of quantum LDPC codes `[[n_i, k_i]]` with bounded check degrees, `k_i/n_i -> R`, growing block sizes, and an error-correction procedure that reduces local stochastic noise below threshold.
- Choose parameters satisfying the theorem, and take any sequential logical circuit C using k qubits and `f(k)` locations, where `f(k) = o(g(k^alpha))`; in the intended case, f is polynomial.
- Then for every overhead slack `eta > 1` and accuracy epsilon, for all sufficiently large k, there is a threshold physical error rate `p_T(eta)` and a fault-tolerant simulation using at most

```text
eta k / R
```

physical qubits, with output distribution within statistical distance epsilon of C.

The fine print is load-bearing. Gottesman explicitly assumes long-range gates between arbitrary pairs of qubits and fast reliable classical computation. He says both assumptions are critical to the constant-overhead result, even though threshold theorems with polylog overhead exist without them. He also notes that codes whose syndrome bits can all be measured locally do not seem capable of encoding qubits without growing overhead.

Time/gate overhead in Gottesman is not zero. The theorem gives total physical locations

```text
O(f(k) T(2 k^alpha') k^alpha'/(eta - 1) + f(k) k^alpha' polylog(k/epsilon))
```

and classical computation depth per logical time step

```text
O(h(2 k^alpha') + log log(k/epsilon)).
```

So the theorem is "constant qubit ratio" under a model that does not charge realistic geometry or classical reliability. It is not "constant number of physical operations per logical gate" in a hardware-neutral sense.

### 2.2 Fawzi-Grospellier-Leverrier theorem

**VERIFIED.** Omar Fawzi, Antoine Grospellier, Anthony Leverrier, "Constant overhead quantum fault-tolerance with quantum expander codes," *Proceedings of the 59th IEEE Symposium on Foundations of Computer Science* (FOCS 2018), doi:10.1109/FOCS.2018.00076, arXiv:1808.03821.

FGL instantiate Gottesman's framework using quantum expander codes and prove:

```text
For any eta > 1 and epsilon > 0, there exists p_T(eta) > 0 such that, for sufficiently large k, any quantum circuit C acting on k qubits and consisting of f(k) locations for f an arbitrary polynomial has a noisy circuit C~ using eta k physical qubits, depth O(f(k)), and number of locations O(k f(k)), whose output distribution is within total variation distance epsilon of C, for local stochastic noise p < p_T.
```

What "constant" quantifies over:

- It is constant in k and in the polynomial circuit length f(k), once eta and epsilon are fixed and k is sufficiently large.
- It is a space overhead: physical qubits/logical qubits <= eta.
- It can be made arbitrarily close to 1 only in the limit of sufficiently small physical error rate.
- It is not a statement about a fixed-width computation of arbitrary length.

Time overhead:

- The theorem states depth `O(f(k))` for a sequentialized circuit. That is asymptotically constant time overhead relative to the sequential circuit length, under their model.
- The physical circuit has `O(k f(k))` locations. Compared to a sparse logical gate count f(k), that is an O(k) location count; compared to a model that already counts wait/storage locations on k wires at every time step, it is constant overhead.
- Their decoder can be parallelized to logarithmic depth and is single-shot. But in the theorem's circuit model, classical computation is error-free and fast; they explicitly say they assume the logarithmic-depth decoding algorithm can be performed in constant time. If you charge classical decoding as physical computation, the time overhead is at least logarithmic in block size, not literally zero.

Limitations opened in the paper:

- They need expander graphs with large vertex expansion; no known efficient deterministic construction/checking of the required graphs is available in the form their proof needs.
- They need large constant degree, implying large finite-size codes.
- They expect the threshold value from the proof to be several orders of magnitude smaller than standard concatenated-code thresholds because the bounds are crude.
- Their quantum LDPC checks are not geometrically local in Euclidean space. They explicitly distinguish this from surface-code spatial locality.

### 2.3 Recent qLDPC practical result

**VERIFIED.** Sergey Bravyi, Andrew W. Cross, Jay M. Gambetta, Dmitri Maslov, Patrick Rall, Theodore J. Yoder, "High-threshold and low-overhead fault-tolerant quantum memory," *Nature* 627, 778-782 (2024), doi:10.1038/s41586-024-07107-7, arXiv:2308.07915.

This is not a universal FT computation theorem; it is a fault-tolerant memory protocol. But it matters practically because it shows qLDPC-style overhead is not merely asymptotic fantasy.

The opened text states:

- The LDPC memory family has threshold `0.8%` for the standard circuit-based noise model, on par with the surface code.
- A length-n code uses n data qubits plus n ancillary check qubits, so `2n` physical qubits total.
- Syndrome measurement uses a depth-7 circuit of nearest-neighbor CNOT gates on a degree-6 graph consisting of two edge-disjoint planar subgraphs.
- Example: the `[[144,12,12]]` BB code uses 288 physical qubits total, has pseudo-threshold 0.0065, and at p = 10^-3 has `p_L = 2*10^-7`, enough to preserve 12 logical qubits for nearly one million syndrome cycles.
- The `[[288,12,18]]` code uses 576 physical qubits total, pseudo-threshold 0.0069, and at p = 10^-3 has `p_L = 2*10^-12`.
- Their surface-code comparison: 12 separate distance-d surface-code patches have length `n = 12 d^2`; encoding 12 logical qubits in surface-code patches would require nearly 3000 physical qubits to suppress p = 10^-3 to 10^-6. The BB example gives more than 10x qubit savings.

Adversarial relevance: this severely weakens any argument that prices a quantum host using surface-code constants. Surface code is a good current architecture, not a lower bound on quantum physics.

## 3. Lower bounds: FT cannot be literally free, but the lower bound is small

### 3.1 General space lower bound

**VERIFIED.** Omar Fawzi, Alexander Mueller-Hermes, Ala Shayeghi, "A lower bound on the space overhead of fault-tolerant quantum computation," *13th Innovations in Theoretical Computer Science Conference* (ITCS 2022), LIPIcs 215, 68:1-68:22, doi:10.4230/LIPIcs.ITCS.2022.68, arXiv:2202.00119.

The arXiv abstract and opened PDF state the key result. For any nonunitary qubit channel N and any FT scheme against iid noise modeled by N, the number of physical qubits is at least

```text
max{ Q(N)^(-1) n, alpha_N log T }
```

for circuits of length T and width n, at constant accuracy epsilon <= 1/128. Here `Q(N)` is the quantum capacity of the noise channel and `alpha_N > 0` depends only on N. They allow fresh qubits and free/perfect classical computation.

The paper explicitly draws the conclusion:

```text
fault-tolerant quantum computation with constant space overhead is not achievable beyond exponential computations for any noise channel N.
```

This is the cleanest answer to "is there a lower bound?" Yes. For fixed-width computations, space must grow at least logarithmically with time/length. For constant space overhead m = O(n), the computation length can be at most exponential in n before the `alpha_N log T` term wins.

Adversarial implication for G = 10^183:

```text
log_2(10^183) = 183 log_2 10 ~= 607.9.
ln(10^183) ~= 421.4.
```

So the universal lower bound says, up to the channel-dependent alpha, "you need hundreds or thousands of qubits because the computation is that long." If the simulated universe has anywhere near holographic-width logical degrees of freedom, this is negligible. It only bites a narrow, fixed-width host trying to run an absurdly long computation.

### 3.2 Low-dimensional / local lower bounds

**VERIFIED.** Sergey Bravyi, David Poulin, Barbara Terhal, "Tradeoffs for reliable quantum information storage in 2D systems," *Physical Review Letters* 104, 050503 (2010), doi:10.1103/PhysRevLett.104.050503, arXiv:0909.5200.

The arXiv metadata states the 2D local-code tradeoff:

```text
k d^2 = O(n)
```

for codes specified by geometrically local commuting constraints on a 2D lattice. Equivalently,

```text
n/k = Omega(d^2).
```

This is the formal reason the surface code's quadratic distance overhead is not an accident in 2D local stabilizer architectures.

**VERIFIED.** Nouedyn Baspin, Omar Fawzi, Ala Shayeghi, "A lower bound on the overhead of quantum error correction in low dimensions," arXiv:2302.04317 (2023); QIP 2023 presentation metadata found, no journal venue found in this pass.

They prove a low-dimensional operational lower bound. Informal theorem opened in the PDF: for a 2D-local circuit W on m physical qubits, with nonlocal error-free classical computation, subject to depolarizing noise strength p every O(1) steps, achieving target logical error `delta = p^f` for a code encoding k qubits requires

```text
m/k in Omega(sqrt(f)).
```

Formal theorem for D-dimensional O(1)-local circuits:

```text
m/k in Omega( min{ (1/Delta) * (log(1/delta)/log(1/p))^(1/D), 1/delta^(1/8) } ).
```

For constant p, constant Delta, and delta -> 0, this becomes

```text
m/k in Omega( log(1/delta)^(1/D) ).
```

They explicitly say this shows the nonlocal operations in Gottesman/FGL constant-overhead schemes are necessary.

Adversarial implication: lower bounds can support "surface-code-like overhead is unavoidable" only if you assume low-dimensional geometric locality. A quantum host of unknown physics is not bound to our 2D chip layout.

## 4. Does fault tolerance apply to a host that is simulating?

Short answer: only after you specify that the host is an imperfect information processor running a reliable computation whose errors are not part of the simulated law.

**VERIFIED.** John Preskill, "Quantum Computing in the NISQ era and beyond," *Quantum* 2, 79 (2018), doi:10.22331/q-2018-08-06-79, arXiv:1801.00862. The arXiv abstract states the ordinary simulation-computing point: noise limits the size of quantum circuits executable reliably; NISQ devices are useful for many-body quantum physics, but scalable useful quantum technologies ultimately require fully fault-tolerant quantum computing.

**VERIFIED.** Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, Ryan Babbush, "Even more efficient quantum computations of chemistry through tensor hypercontraction," *PRX Quantum* 2, 030305 (2021), doi:10.1103/PRXQuantum.2.030305, arXiv:2011.03494. The arXiv metadata states a concrete fault-tolerant quantum simulation resource estimate: FeMoCo can be simulated using about four million physical qubits and under four days runtime, assuming 1 microsecond surface-code cycle times and physical gate error rates no worse than 0.1%. This is evidence that practical quantum simulation papers do price FT overhead when the simulator is a noisy quantum computer.

**VERIFIED.** Seth Lloyd, Benjamin Rahn, Charlene Ahn, "Robust quantum computation by simulation," arXiv:quant-ph/9912040 (1999). The opened arXiv abstract gives the counterexample shape: simulating quantum systems that provide intrinsically fault-tolerant quantum computation preserves fault tolerance; errors committed during simulation can be eliminated by the natural error-correcting features of the systems simulated; examples include toric codes and nonabelian anyons.

Interpretation for the host argument:

- If the host is a noisy digital quantum computer implementing a circuit or Hamiltonian-simulation algorithm, FT applies exactly as in the literature. Long circuits need error correction or they fail with probability approaching one.
- If the host is an analog quantum system whose native physics simply evolves into something isomorphic to our universe, then "fault tolerance overhead" is not automatically a separate term. Deviations may just be part of the simulated physics, or the physical law may be naturally stable/topological/thermalizing in the relevant variables.
- If the simulated system itself contains error-correcting structure, the boundary between host-level correction and simulated-dynamics correction can blur. Lloyd-Rahn-Ahn is not a universe-simulation paper, but it is enough to kill the universal claim "simulation implies external surface-code-like FT overhead."

## 5. Plain adversarial verdict

Fault-tolerance overhead can carry weight as an engineering estimate only after host assumptions are fixed: architecture, noise model, locality, target accuracy, logical width, and whether classical decoding is charged. Under our current surface-code hardware assumptions it is large in practice and polylogarithmic in computation length. Under qLDPC/nonlocal constant-overhead assumptions it can be constant in space for polynomial-length computations in the circuit width, with time/decode caveats but no length-dependent qubit explosion.

The lower-bound literature proves FT is not literally free: at minimum, for nonunitary iid noise, physical qubits scale like `alpha_N log T` at fixed width, and in 2D-local architectures the overhead grows as a power of log(1/error). But for `T = 10^183`, `log T` is only hundreds in bits, and any universe-scale quantum host has width so large that this bound is inert unless you independently impose a tiny-width host.

So: fault-tolerance overhead is a real term, but it is asymptotically negligible for the resource argument as currently framed. It is a constant factor or a polylogarithmic factor, and constant factors cannot constrain anything when the host's physics is unknown. Do not build the quantum-host impossibility argument on this term.