Case Study: Rate, Distance, and Why Repetition Codes Lose
Executive Summary
Every introduction to error correction starts with the repetition code, and every serious application abandons it. Understanding why — in terms of the rate-distance trade-off — explains the central problem in quantum error correction today: the surface code is, in this precise sense, a repetition code, and the field's most active research area is escaping its overhead.
This case study quantifies the trade-off classically, then shows that the quantum situation is structurally identical, and finishes with what quantum LDPC codes change.
Skills applied
- Computing rate and distance trade-offs for code families (§23.13).
- Understanding asymptotically good codes.
- Applying the analysis to surface-code overhead.
- Evaluating qLDPC codes against surface codes on the right axes.
Phase 1: The repetition code's problem
The $n$-bit repetition code is $[n, 1, n]$:
| $n$ | Rate $k/n$ | Distance | Errors corrected |
|---|---|---|---|
| 3 | 0.333 | 3 | 1 |
| 5 | 0.200 | 5 | 2 |
| 11 | 0.091 | 11 | 5 |
| 101 | 0.0099 | 101 | 50 |
| 1,001 | 0.001 | 1,001 | 500 |
Distance grows linearly, which is good. Rate falls as $1/n$, which is fatal. To correct 500 errors you transmit 1,001 bits per useful bit.
Shannon's theorem says this is unnecessary. Reliable communication is achievable at any rate below capacity, and for a binary symmetric channel at 1% error, capacity is about 0.92 bits per channel use. The repetition code achieves 0.001. It is off the theoretical optimum by nearly three orders of magnitude.
Phase 2: Asymptotically good codes
A family is asymptotically good if, as $n \to \infty$, both
$$\frac{k}{n} \to R > 0 \qquad\text{and}\qquad \frac{d}{n} \to \delta > 0$$
Rate stays bounded away from zero and distance grows linearly in block length.
| Family | Rate | Distance | Asymptotically good? |
|---|---|---|---|
| Repetition | $1/n \to 0$ | $n$ | No |
| Hamming | $\to 1$ | 3 (constant) | No |
| Reed–Solomon | Tunable | $n-k+1$ | Yes (over large alphabets) |
| Random linear | $\to 1-h(p)$ | Linear | Yes |
| LDPC | Near capacity | Linear | Yes |
Repetition fails on rate; Hamming fails on distance. Good codes need both, and the existence of such families is Shannon's theorem made constructive.
Phase 3: The quantum situation is the same shape
Quantum codes are described by $[[n,k,d]]$ and face the same trade-off — plus the extra constraint that stabilizers must commute.
| Quantum code | Parameters | Rate | Asymptotically good? |
|---|---|---|---|
| Shor | $[[9,1,3]]$ | 0.111 | — |
| Steane | $[[7,1,3]]$ | 0.143 | — |
| Surface code | $[[d^2, 1, d]]$ | $1/d^2 \to 0$ | No |
| Colour code | $\sim[[d^2,1,d]]$ | $\to 0$ | No |
| qLDPC (e.g. gross code) | $[[144,12,12]]$ | 0.083 | Yes (some families) |
The surface code has rate $1/d^2$. To reach distance 27 — roughly what RSA-2048 factoring needs at $10^{-3}$ physical error — you spend $2d^2 \approx 1{,}458$ physical qubits per logical qubit.
That is the repetition code's problem, in quantum form: distance grows, rate collapses quadratically. The surface code is not asymptotically good, and every headline resource estimate in this book inherits its overhead.
Phase 4: Why the surface code is used anyway
If it is so inefficient, why is it the default?
1. Locality. Stabilizers act on 4 neighbouring qubits on a 2D grid. Superconducting and neutral-atom hardware are 2D with nearest-neighbour coupling. A code requiring long-range checks cannot be laid out.
2. High threshold. ~1%, among the best known. A code with better rate but a 0.1% threshold is useless if hardware sits at 0.5%.
3. Efficient decoding. Minimum-weight perfect matching decodes in near-linear time with excellent accuracy.
4. It works. Below-threshold operation has been demonstrated experimentally.
The engineering reality. Rate is one axis. Threshold, locality, and decodability are equally binding, and the surface code wins on the others decisively. Choosing a code is a multi-objective problem, and rate-optimal codes have historically lost on the other three.
Phase 5: What qLDPC changes
Quantum LDPC codes — sparse parity checks, quantum analogues of classical LDPC — offer asymptotically good families. The breakthrough results (Panteleev–Kalachev and successors) proved that good qLDPC codes exist, resolving a long-standing open question.
Concretely, IBM's $[[144,12,12]]$ "gross code":
| Surface code, $d=12$ | Gross code $[[144,12,12]]$ | |
|---|---|---|
| Physical qubits | $12 \times 2\times12^2 = 3{,}456$ | 144 |
| Logical qubits | 12 | 12 |
| Distance | 12 | 12 |
| Overhead per logical qubit | 288 | 12 |
A 24× reduction at equal distance and logical count. In a resource estimate, that turns 20 million physical qubits into something closer to a million.
The costs, which are real:
- Non-local checks. Stabilizers act on qubits that are not nearest neighbours, requiring long-range couplers or qubit shuttling. This is a hardware demand, not a software one.
- Harder decoding. Matching does not apply; belief propagation with post-processing is used, and decoder performance is an active research area.
- Logical gates are harder. The surface code's clean lattice-surgery operations do not carry over directly.
- Lower threshold in some families, though the gross code's is competitive.
Phase 6: Where this leaves the field
The surface code is a repetition code in the sense that matters: it buys distance by spending rate quadratically. It dominates today because threshold, locality, and decodability outweigh rate on current hardware.
qLDPC codes are the escape route, and the trade they demand — non-local connectivity — is precisely what hardware roadmaps are now being redesigned around. That is why "long-range couplers" and "qubit shuttling" appear on roadmaps that a few years ago listed only qubit counts.
The forecasting implication: a 24× overhead reduction is worth more than several years of qubit-count growth. Following code development is at least as informative as following hardware announcements — the same lesson as the Shor resource-estimate case study (Chapter 15), arriving from a different direction.
Discussion Questions
- Repetition fails on rate, Hamming on distance. Explain why a good code must achieve both and why that is non-trivial.
- The surface code has rate $1/d^2$ and dominates practice. Under what hardware assumptions would that change?
- qLDPC codes need non-local checks. What hardware architectures make that feasible, and what does it cost?
- A 24× overhead reduction versus several years of qubit growth — which would you rather have, and why?
Your Turn: Extensions
- Plot rate against distance for repetition, Hamming, surface, and gross codes on log axes.
- Compute the physical qubits for 1,000 logical qubits at distance 15 under surface and gross codes.
- Read a qLDPC threshold result and compare it against the surface code's ~1%.
- Estimate how a 24× reduction changes the Chapter 15 RSA-2048 estimate.
Key Takeaways
- Repetition codes trade rate for distance at the worst possible exchange: rate $1/n$ for distance $n$.
- Asymptotically good codes keep both rate and relative distance bounded away from zero; repetition and Hamming each fail one condition.
- The surface code has rate $1/d^2$ and is not asymptotically good — it is the repetition code's problem in quantum form.
- It dominates anyway because threshold, 2D locality, and efficient matching decoding outweigh rate on current hardware.
- qLDPC codes offer ~24× overhead reductions at the cost of non-local connectivity, and code progress may move timelines more than qubit-count growth.