Quantum Hamming and Singleton Bounds

Every quantum error-correcting code is a bargain: you spend physical qubits to buy protection, and the exchange rate is fixed by mathematics, not by cleverness. A code is labelled by three numbers $[[n,k,d]]$ — the count of physical qubits $n$ , the count of logical qubits $k$ it hides inside them, and the distance $d$ that measures how much damage it can survive. The central design question is brutally simple to state and surprisingly deep to answer: given $n$ and $k$ , how large can $d$ be? The quantum Hamming and Singleton bounds are the two foundational impossibility theorems that answer it, and they answer it in two completely different languages. The Hamming bound speaks the language of counting: discretize every error into a Pauli basis, demand that a nondegenerate code map each correctable error to its own orthogonal corner of Hilbert space, and the corners must fit inside a room of dimension $2^n$ . The Singleton bound speaks the language of information flow: if a code survives the erasure of any $d-1$ qubits, the logical information cannot hide in too few qubits, and no-cloning forbids copying it into too many — quantify that tension with von Neumann entropy and out drops $k \le n - 2(d-1)$ . The two bounds meet exactly once, at the five-qubit code $[[5,1,3]]$ : it saturates both at the same time, making it simultaneously the smallest perfect quantum code, the smallest quantum MDS code, and the provably shortest code that can correct an arbitrary single-qubit error.

Key takeaways

The quantum Hamming bound is a sphere-packing count: for a nondegenerate $[[n,k,d]]$ code correcting $t=\lfloor(d-1)/2\rfloor$ errors, the orthogonal error subspaces must fit inside Hilbert space, $2^{k}\sum_{j=0}^{t}\binom{n}{j}3^{j}\le 2^{n}$ .
The factor $3^{j}$ replaces the classical $1^{j}$ because each damaged qubit can suffer three distinct Pauli errors $X$ , $Y$ , or $Z$ — the single feature that makes the quantum theory quantum.
The quantum Singleton bound $k\le n-2(d-1)$ follows from erasure recovery and the subadditivity of entropy; it makes no nondegeneracy assumption and therefore constrains every code.
Degeneracy is the loophole in the Hamming count only: when distinct errors act identically on the codespace they need not claim separate subspaces, so degenerate codes can beat the counting bound but never the Singleton bound.
The five-qubit code $[[5,1,3]]$ saturates both bounds — $2(1+15)=32=2^{5}$ and $5-1=2(3-1)$ — making it the unique perfect, MDS, minimal single-error-correcting quantum code.
Key idea: two independent theorems fence in every $[[n,k,d]]$ code — the Hamming bound packs orthogonal error images into $2^{n}$ (nondegenerate codes only), while the entropic Singleton bound $k\le n-2(d-1)$ holds universally — and the five-qubit code is the single point where both fences touch.

The core insight

Two independent constraints bound every $[[n,k,d]]$ code: the Hamming bound packs $2^{k}$ -dimensional orthogonal error subspaces into $2^{n}$ and holds only for nondegenerate codes, while the Singleton bound $k\le n-2(d-1)$ follows from entropic monogamy and holds for all codes — and the $[[5,1,3]]$ code saturates both at once.

Where this lives today

The bounds are the first sanity check any code proposal must pass. When an architecture claims to protect $k$ logical qubits to distance $d$ , the Singleton floor $n\ge k+2(d-1)$ fixes the minimum qubit budget before a single gate is designed — any proposal beneath it is not ambitious, it is impossible. The five-qubit code, certified optimal by these bounds, is a favorite testbed: it has been realized in nuclear magnetic resonance, trapped ions, nitrogen-vacancy centers, and superconducting circuits precisely because it wastes no qubits, even though its lack of a transversal Clifford set makes it awkward for full fault tolerance. The surface code that anchors most large-scale roadmaps lives deliberately where the Hamming bound is silent: it is enormously degenerate, spending thousands of physical qubits per logical qubit and buying distance through geometry rather than counting-efficient packing. The open question the bounds sharpen is the quantum MDS frontier — for which $[[n,k,d]]$ does a Singleton-saturating code exist? — connecting small perfect codes to modern high-rate quantum LDPC codes chasing the best distance for a given overhead.

The physical picture

Picture the $2^{n}$ -dimensional Hilbert space of $n$ physical qubits as a warehouse, and picture error correction as a filing problem. The undamaged codespace is a room of dimension $2^{k}$ . Every error the code must fix has to be filed in its own separate room of the same size, because the only way a syndrome measurement can later read off which error occurred is if the errors have pushed the code into mutually distinguishable — that is, orthogonal — corners. A nondegenerate code demands one clean room per correctable error, and the Hamming bound is nothing more than the observation that the rooms must fit in the warehouse. When they fill it exactly, with no wasted floor space, the code is called perfect. The number of rooms is a Pauli count. A single qubit can be hit three ways — a bit flip $X$ , a phase flip $Z$ , or both together $Y=iXZ$ — so a weight- $j$ error carries a factor $3^{j}$ where a classical bit, which can only flip, would carry $1^{j}$ . That one factor of three is the whole quantum difference, and it is also why the Singleton overhead carries a factor of two: guarding against the full Pauli set is like guarding a bit-flip code and a phase-flip code simultaneously.

Figure

The five-qubit code packs 16 orthogonal error subspaces, each of dimension 2ᵏ = 2, into the 2⁵ = 32 dimensional Hilbert space with no floor space to spare — 16 × 2 = 32, the equality that makes it a perfect code

The escape hatch is degeneracy. Two physical errors that differ by a stabilizer element act identically on every codeword — they are the same error as far as the code can tell — so they can share a single room. Highly degenerate codes such as Shor's nine-qubit code and the topological surface codes exploit this so heavily that the naive room-count wildly overcounts, and the Hamming bound falls silent for them. The Singleton bound does not, because its proof never counts rooms at all: it tracks where quantum information can and cannot live. The second figure maps the small-code landscape against both fences at once.

Figure

The k = 1 code landscape: the quantum Singleton frontier d = (n−1)/2 + 1 is the amber line, and the five-qubit code at n = 5, d = 3 sits exactly on it (both MDS and perfect), while Steane at n = 7 and Shor at n = 9 correct the same single error at d = 3 well inside the allowed region

The core equations

The Hamming bound is the counting theorem. It fixes the largest distance a nondegenerate code of given size can reach by insisting the correctable-error subspaces fit inside Hilbert space. Here $t=\lfloor(d-1)/2\rfloor$ is the number of arbitrary single-qubit errors the code corrects, since a distance- $d$ code corrects up to $\lfloor(d-1)/2\rfloor$ general errors.

2^{k}\sum_{j=0}^{t}\binom{n}{j}\,3^{j}\le 2^{n},\qquad t=\left\lfloor\frac{d-1}{2}\right\rfloor \qquad (1)

where: $n$ — number of physical qubits; $k$ — number of logical (encoded) qubits; $d$ — code distance, the minimum weight of an undetectable logical error; $t$ — number of arbitrary single-qubit errors corrected; $\binom{n}{j}$ — ways to pick which $j$ of the $n$ qubits are hit; $3^{j}$ — the three nontrivial Paulis $X,Y,Z$ on each hit qubit. Reading it: the left side is (rooms) × (room size), and it may not exceed the warehouse dimension $2^{n}$ . The Singleton bound is the information theorem. It comes from a different world — erasure recovery and entropy — and crucially assumes nothing about the code's structure, so it fences in degenerate and nondegenerate codes alike. It is often called the Knill–Laflamme bound.

k\le n-2(d-1)\quad\Longleftrightarrow\quad n-k\ge 2(d-1) \qquad (2)

where: $n-k$ — number of redundant (parity) qubits spent; $d-1$ — number of qubits that can be erased with guaranteed recovery. Reading it: buying one more unit of distance costs at least two physical qubits per logical qubit — a hard doubling of the classical overhead. The five-qubit code is the equality case of equation (1). Plugging in $n=5,k=1,d=3$ (so $t=1$ ) makes the left side hit $2^{n}$ exactly, with no slack — the defining property of a perfect code.

[[5,1,3]]:\quad 2^{1}\Big(\tbinom{5}{0}3^{0}+\tbinom{5}{1}3^{1}\Big)=2\,(1+15)=32=2^{5} \qquad (3)

where: $\binom{5}{0}3^{0}=1$ — the identity (no-error) room; $\binom{5}{1}3^{1}=15$ — the five qubits times three Paulis, giving fifteen weight-1 error rooms. Reading it: $16$ rooms of dimension $2$ tile the $32$ -dimensional space perfectly. That code is not an abstraction; it is a concrete cyclic stabilizer code with four generators, one for each of the $n-k=4$ redundant qubits. Each generator is a cyclic shift of the same weight-4 pattern.

S=\langle\,XZZXI,\ IXZZX,\ XIXZZ,\ ZXIXZ\,\rangle \qquad (4)

where: $S$ — the stabilizer group, an abelian subgroup of the Pauli group whose $+1$ eigenspace is the codespace; the four listed operators — independent generators, $n-k=5-1=4$ of them, encoding one logical qubit. Reading it: the cyclic symmetry forces every weight-1 and weight-2 Pauli to anticommute with some generator, so the minimum logical weight is $3$ and $d=3$ . Both bounds generalize from qubits to $q$ -dimensional qudits by replacing the three Paulis per site with the $q^{2}-1$ nontrivial generalized Paulis, recovering equation (1) at $q=2$ .

2^{k}\sum_{j=0}^{t}\binom{n}{j}\,(q^{2}-1)^{j}\le q^{n},\qquad k\le n-2(d-1) \qquad (5)

where: $q$ — local Hilbert-space dimension of each physical system; $q^{2}-1$ — number of nontrivial generalized Paulis per qudit (three for $q=2$ ). Reading it: the structure is identical; only the per-site error multiplicity changes, and the Singleton form is dimension-independent. For contrast, the classical Singleton bound over any alphabet reads with a single factor, and the quantum doubling in equation (2) is the entire difference.

k\le n-(d-1)\qquad(\text{classical Singleton}) \qquad (6)

where: $d-1$ — classical erasures correctable, exactly half the quantum cost. Reading it: classically one parity symbol buys one unit of distance; quantum-mechanically it takes two, because amplitude and phase must both be guarded.

Derivation AQuantum Hamming bound from Knill–Laflamme orthogonality

The goal is to turn the requirement "distinct correctable errors must be distinguishable by a syndrome" into a hard inequality on $[[n,k,d]]$ . We count the correctable Pauli errors, use the Knill–Laflamme conditions in their nondegenerate diagonal form to show each error carries the codespace to its own orthogonal subspace of equal dimension, then invoke the fact that mutually orthogonal subspaces cannot overflow their ambient space. The result is the sphere-packing inequality, whose equality case is exactly what "perfect" means.

Step 1. Count the correctable errors. A Pauli error of weight $j$ acts nontrivially on exactly $j$ qubits; choosing them gives $\binom{n}{j}$ subsets, and on each chosen qubit the error is one of $X,Y,Z$ , giving $3^{j}$ patterns. Summing to $t=\lfloor(d-1)/2\rfloor$ counts all $N=\sum_{j=0}^{t}\binom{n}{j}3^{j}$ correctable Paulis, identity included. Why: a distance- $d$ code is guaranteed to correct every error of weight at most $t$ , so these are precisely the errors that must be filed separately.

Step 2. Invoke nondegeneracy. For a nondegenerate code the Knill–Laflamme conditions take the diagonal form $P\,E_{a}^{\dagger}E_{b}\,P=\delta_{ab}\,P$ , with $P$ the codespace projector:

\langle\psi_{m}|E_{a}^{\dagger}E_{b}|\psi_{n}\rangle=\delta_{ab}\,\delta_{mn}

so different errors send the codespace to orthogonal images, $E_{a}\mathcal{C}\perp E_{b}\mathcal{C}$ for $a\ne b$ . Why: orthogonal images are exactly the condition under which a syndrome measurement can tell the errors apart and undo them; degenerate codes relax the $\delta_{ab}$ and this step fails.

Step 3. Fix the room size. Each $E_{a}$ is a Pauli operator, hence unitary, so it preserves dimension: $\dim(E_{a}\mathcal{C})=\dim\mathcal{C}=2^{k}$ . The $N$ images are therefore $N$ mutually orthogonal subspaces each of dimension $2^{k}$ . Why: every correctable error costs the same $2^{k}$ of storage, so the total demand is simply $N\cdot 2^{k}$ .

Step 4. Pack into Hilbert space. Mutually orthogonal subspaces have total dimension at most that of the ambient space:

N\cdot 2^{k}=2^{k}\sum_{j=0}^{t}\binom{n}{j}3^{j}\le\dim\big((\mathbb{C}^{2})^{\otimes n}\big)=2^{n}

which is the quantum Hamming bound. Why: this is the whole content — the rooms fit in the warehouse — and equality is possible only when they tile it with zero slack, the definition of a perfect code. For $[[5,1,3]]$ : $t=1$ , $N=1+5\cdot 3=16$ , and $N\cdot 2^{k}=16\cdot 2=32=2^{5}$ — exact equality, confirming perfection. Cross-check against Nielsen and Chuang §10.5.6.

Go deeper · Derivation B · 2 minThe quantum Singleton bound from erasure and entropy

Derivation BThe quantum Singleton bound from erasure and entropy

The goal is to prove $k\le n-2(d-1)$ without assuming nondegeneracy, using only that a distance- $d$ code corrects the erasure of any $d-1$ qubits together with the subadditivity of von Neumann entropy. The strategy: entangle a reference with the logical qubits, split the physical qubits into two disjoint erasable blocks plus a remainder, use the fact that an erasable block carries no information about the reference, and let subadditivity force the remainder to be at least as large as the logical register. The factor of two appears because two disjoint blocks are quiet at once.

Step 1. Set up erasure and the reference. A distance- $d$ code corrects any $d-1$ erasures (errors at known locations). Introduce a reference $R$ of $k$ qubits maximally entangled with the logical register, so $S(R)=k$ and the global state on $R$ together with the physical qubits $Q$ is pure. Partition $Q$ into three disjoint sets $X$ , $Y$ , $Z$ with $|X|=|Y|=d-1$ and $|Z|=n-2(d-1)$ , which requires $n\ge 2(d-1)$ . Why: purity lets us convert entropies of one region into entropies of its complement, and the two erasable blocks $X,Y$ are the levers we will pull.

Step 2. An erased block carries no logical information. Correctability of the erasure of $X$ means $X$ holds nothing about $R$ : $I(R:X)=0$ , i.e. $\rho_{RX}=\rho_{R}\otimes\rho_{X}$ , so $S(RX)=S(R)+S(X)$ . Using purity, $S(RX)=S(YZ)$ , giving $S(YZ)=k+S(X)$ ; the identical argument for $Y$ gives $S(XZ)=k+S(Y)$ . Why: this is the quantum no-cloning heart of the proof — if the erased qubits knew anything about the logical state, that information would have been copied, which is forbidden.

Step 3. Add and apply subadditivity. Subadditivity gives $S(YZ)\le S(Y)+S(Z)$ and $S(XZ)\le S(X)+S(Z)$ . Summing the two identities from Step 2 and applying these:

2k+S(X)+S(Y)=S(YZ)+S(XZ)\le S(X)+S(Y)+2\,S(Z)

so $2k\le 2\,S(Z)$ , hence $k\le S(Z)\le|Z|=n-2(d-1)$ . Why: the two quiet blocks each cost the code $d-1$ qubits and together account for the factor $2(d-1)$ ; the remainder $Z$ must be at least as entropic as the logical register it is forced to protect. This bound used no counting of error images, so it survives degeneracy untouched. Cross-check against Preskill Chapter 7 and Nielsen and Chuang §12.4.3.

Go deeper · Derivation C · 1 minWhy five qubits is the minimum for one arbitrary error

Derivation CWhy five qubits is the minimum for one arbitrary error

The goal is to prove that no code with one logical qubit and distance three exists on fewer than five physical qubits, and that five is achievable — so the five-qubit code is length-optimal. We attack $n$ from below with the Singleton bound, confirm the verdict independently with the Hamming count, and then exhibit an explicit code at $n=5$ , so that both an impossibility argument and a construction pin the minimum exactly at five.

Step 1. Singleton forces $n\ge 5$ . With $k=1$ and $d=3$ , equation (2) reads $1\le n-2(3-1)=n-4$ , so $n\ge 5$ for any such code, degenerate or not:

1\le n-4\ \Rightarrow\ n\ge 5

Why: because Singleton is universal, this already rules out $n=4$ with no escape via degeneracy — the decisive constraint.

Step 2. Hamming confirms it for nondegenerate codes. With $t=1$ the counting bound is $2(1+3n)\le 2^{n}$ . At $n=4$ it gives $2(1+12)=26>16=2^{4}$ , violated; at $n=5$ it gives $2(1+15)=32=2^{5}$ , saturated. Why: an independent argument reaching the same $n\ge 5$ raises confidence, and the saturation at five foreshadows perfection.

Step 3. Construct a code at $n=5$ . The cyclic stabilizer code $S=\langle XZZXI,\,IXZZX,\,XIXZZ,\,ZXIXZ\rangle$ realizes $[[5,1,3]]$ explicitly, so the lower bound is achieved. Why: an impossibility bound plus a matching construction is what turns "at least five" into "exactly five".

Step 4. Conclude. Both bounds independently give $n\ge 5$ , and a code meets it, so five qubits is the unique minimum length for correcting one arbitrary single-qubit error. Why: this is the sense in which the five-qubit code is optimal — nothing smaller can do the job. Numbers reproduce Laflamme, Miquel, Paz, Zurek, PRL 77, 198 (1996) and Nielsen and Chuang Box 10.6.

Limiting cases

How the two bounds specialize across the regimes that matter:

Case	Result	Meaning
Single-error correction, $t=1$ , $d=3$	$2^{k}(1+3n)\le 2^{n}$	Hamming bound for one arbitrary error. With $k=1$ it first holds at $n=5$ (giving $32\le 32$ ), forcing $n\ge 5$ for nondegenerate single-error codes.
Singleton, distance $d$	$k\le n-2(d-1)$	Always valid, degenerate or not. For $d=3$ : $k\le n-4$ , so $n\ge 5$ at $k=1$ — the five-qubit minimum again, from a different proof.
Classical limit ( $Z$ -errors only)	$2^{k}\sum_{j=0}^{t}\binom{n}{j}\le 2^{n}$	Dropping the $3^{j}$ multiplicity recovers the binary classical Hamming bound; the factor $3^{j}$ is the sole structural quantum change.
Perfect and MDS saturation	$[[5,1,3]]$ : $2(1+15)=2^{5}$ and $5-1=2(3-1)$	The five-qubit code saturates Hamming (perfect) and Singleton (MDS) at once — a coincidence not shared by Steane $[[7,1,3]]$ or Shor $[[9,1,3]]$ .
Highly degenerate limit	Hamming silent, Singleton binding	Surface and Shor-type codes have $N\cdot 2^{k}\ll 2^{n}$ ; the counting bound imposes nothing and one must use Singleton and distance arguments.

Common trapThe Hamming bound is not a universal law

The most common error is to quote the quantum Hamming bound as if it constrained every code. It does not. Its derivation assumes nondegeneracy — that distinct correctable errors produce orthogonal images. Degenerate codes, where different errors act identically on the codespace (differing by a stabilizer element), need not obey the room-counting inequality, and highly degenerate codes routinely sit far inside it or, in principle, could beat the analogous rate bound. If you want a limit that never fails, reach for the Singleton bound $k\le n-2(d-1)$ : its entropic proof makes no orthogonality assumption and holds for all codes. Rule of thumb — Hamming certifies nondegenerate optimality and diagnoses degeneracy; Singleton certifies feasibility.

Worked examples

1 · The five-qubit code saturates both bounds (fully worked)

Verify that $[[5,1,3]]$ is simultaneously a perfect code and a quantum MDS code, and state what each saturation means.

Step 1. Fix the parameters. Here $n=5$ , $k=1$ , $d=3$ , so the number of correctable arbitrary errors is $t=\lfloor(d-1)/2\rfloor=\lfloor 1\rfloor=1$ . The code must handle the identity plus every weight-1 Pauli.

Step 2. Evaluate the Hamming left side. The correctable-error count is $N=\binom{5}{0}3^{0}+\binom{5}{1}3^{1}=1+15=16$ . Each error claims a room of dimension $2^{k}=2$ , so the demand is $N\cdot 2^{k}=16\times 2=\mathbf{32}$ . The warehouse has dimension $2^{n}=2^{5}=\mathbf{32}$ . Demand equals supply: the Hamming bound is saturated, so the code is perfect — its error subspaces tile Hilbert space with zero waste.

Step 3. Check Singleton. The bound is $k\le n-2(d-1)$ , i.e. $1\le 5-2(2)=5-4=1$ . Equality again: the Singleton bound is saturated, so the code is quantum MDS — it achieves the maximum distance allowed for $n=5,k=1$ .

Step 4. Interpret. Saturating both is rare: it makes $[[5,1,3]]$ the unique code that is at once perfect, MDS, and (by the minimum-length derivation) the shortest single-error-correcting quantum code. $16\times 2=32=2^{5}$ (perfect) and $5-1=2(3-1)$ (MDS) — both fences touch here.

2 · A bounds survey — which $[[n,1,d]]$ codes can exist?

Use the two bounds to decide the fate of four candidate codes.

Step 1. Rule out $[[4,1,3]]$ . Singleton: $1\le 4-4=0$ is false, so it cannot exist — and Hamming agrees, $2(1+3\cdot 4)=26>16=2^{4}$ , also violated. Two independent verdicts of impossibility.

Step 2. Rule out $[[7,1,5]]$ . Two arbitrary errors need $d=5$ . Singleton: $1\le 7-2(4)=-1$ is false, so no such code exists, degenerate or not. The Hamming count agrees loudly, $2(1+\binom{7}{1}3+\binom{7}{2}9)=2(1+21+189)=422>128=2^{7}$ .

Step 3. Confirm $[[7,1,3]]$ (Steane) is allowed. Singleton: $1\le 7-4=3$ , true with slack. Hamming: $2(1+21)=44\le 128$ , comfortable. Steane exists and is neither perfect nor MDS — it trades optimal size for a transversal Clifford gate set.

Step 4. Diagnose $[[9,1,3]]$ (Shor). Hamming: $2(1+27)=56\le 512=2^{9}$ — an enormous slack of $512-56$ . Singleton: $1\le 9-4=5$ , far from tight. The huge Hamming slack is not waste but degeneracy: many of Shor's weight-2 errors act identically on the codespace, so it needs far fewer than $56$ distinct rooms. $[[4,1,3]]$ and $[[7,1,5]]$ are impossible; $[[7,1,3]]$ and $[[9,1,3]]$ exist, the latter deeply degenerate.

Physics of the portrait

The bounds and the code that saturates them come from one short, extraordinary burst of work in the mid-1990s, and one physicist sits at the center of it — a cosmologist by training who turned to keeping quantum information alive.

Origins · 1 minRaymond Laflamme and how this was discovered

Raymond Laflamme

b. 1960, Québec City · the perfect five-qubit code and the error-correction conditions behind both bounds

Raymond Laflamme began not in information theory but in cosmology, completing his PhD under Stephen Hawking at Cambridge on the arrow of time — famously helping change Hawking's mind about whether time would reverse in a recollapsing universe. He moved to Los Alamos in the early 1990s, just as Peter Shor's factoring algorithm made the fragility of quantum information the field's central problem. In 1996, with César Miquel, Juan Pablo Paz, and Wojciech Zurek, he constructed the perfect five-qubit code $[[5,1,3]]$ — the smallest code correcting an arbitrary single-qubit error — found independently the same year by Bennett, DiVincenzo, Smolin, and Wootters. The next year, with Emanuel Knill, he formulated the Knill–Laflamme conditions, the exact criteria a subspace must satisfy to correct a given error set. Those conditions are the common root of this article: their diagonal (nondegenerate) form yields the Hamming bound, and their erasure-recovery reading yields the Singleton bound. Laflamme went on to lead the Institute for Quantum Computing at Waterloo.

History

1994

— Shor's factoring algorithm makes protecting quantum information urgent

1995

— Shor gives the first quantum code, the nine-qubit code, and Steane introduces CSS codes

1996

— Laflamme, Miquel, Paz, Zurek and, independently, Bennett, DiVincenzo, Smolin, Wootters find the perfect five-qubit code

1996

— Ekert and Macchiavello prove the quantum Hamming bound

1997

— Knill and Laflamme give the general error-correction conditions and the quantum Singleton bound

Going further

Texts. Nielsen and Chuang, Quantum Computation and Quantum Information (10th anniversary ed.), §10.3–10.5 and §12.4 · Preskill, Lecture Notes for Physics 219, Chapter 7 (Quantum Error Correction) · Wilde, Quantum Information Theory (2nd ed.), Chapter 24 · Watrous, The Theory of Quantum Information, error-correction chapter · Kitaev, Shen, Vyalyi, Classical and Quantum Computation · Gottesman, Stabilizer Codes and Quantum Error Correction (PhD thesis, 1997).

Provenance. Every number here is recomputable by hand: the Hamming saturation $2(1+15)=32=2^{5}$ , the Shor slack $2(1+27)=56\le 512$ , and the Singleton equality $5-1=2(3-1)$ . Verify the Hamming bound and the five-qubit saturation against Nielsen and Chuang §10.5.6 and Box 10.6; the Singleton bound $k\le n-2(d-1)$ and its entropic proof against Preskill Chapter 7 and Nielsen and Chuang §12.4.3; the five-qubit stabilizer generators and cyclic structure against Laflamme, Miquel, Paz, Zurek, PRL 77, 198 (1996) and Gottesman's 1997 thesis. The quantum Hamming bound is due to Ekert and Macchiavello (1996); the quantum Singleton bound to Knill and Laflamme (1997). No nonstandard values are introduced.

Builds on: Knill–Laflamme Conditions · Code Distance and Logical Operators · Discretization of Errors · Pauli Group and Clifford Group Leads to: Stabilizer Formalism · CSS Codes · Steane Seven-Qubit Code · Shor Nine-Qubit Code.

Ask the tutor: Ask me to walk through why the Hamming bound falls silent for the Shor code while the Singleton bound still bites, or to check the parameters of any $[[n,k,d]]$ code you have in mind against both fences.

Why is the quantum overhead double the classical one — the factor of two in the Singleton bound?

Classically one parity symbol buys one unit of distance, $k\le n-(d-1)$ ; quantum-mechanically the coefficient is two, $k\le n-2(d-1)$ . The extra factor is the price of guarding two complementary kinds of error at once: a qubit can suffer a bit flip and a phase flip, and by the discretization of errors, correcting these also corrects their product $Y$ and every continuous error between. In the entropic proof the two appears cleanly — two disjoint blocks of $d-1$ qubits can each be erased with full recovery and each carries zero logical information, so together they subtract $2(d-1)$ from the budget. Amplitude and phase are the two faces the factor counts.

Can a code really beat the Hamming bound?

It can beat the nondegenerate counting bound, yes — that is exactly what degeneracy means. The Hamming inequality counts distinct orthogonal error images and demands they fit in $2^{n}$ . But if two different errors act identically on every codeword — because they differ by a stabilizer element — they land in the same subspace and do not each need a room. A code with enough such coincidences needs fewer than the naive $N$ rooms, so the counting inequality is no longer a necessary condition for it. What no code can ever beat is the Singleton bound, whose proof counts information, not rooms. So "beating Hamming" is a signature of degeneracy, never a violation of physics.

What is the difference between a perfect code and an MDS code?

They saturate different bounds. A perfect code saturates the Hamming (sphere-packing) bound: its correctable-error subspaces tile Hilbert space exactly, with no dimension left over — every point in the space belongs to exactly one error's room. An MDS (maximum-distance-separable) code saturates the Singleton bound: it achieves the largest distance permitted for its $n$ and $k$ , i.e. $n-k=2(d-1)$ . These are logically independent properties — a code can be one, both, or neither. The five-qubit code is famously both; the Steane and Shor codes are neither. Most useful large codes, being degenerate, are far from perfect and not MDS, buying other virtues instead.

Why does the Singleton bound ignore degeneracy when the Hamming bound cannot?

Because they are proved by counting different things. The Hamming proof counts error images and needs them orthogonal and distinct — an assumption that degeneracy breaks, since coincident errors share an image. The Singleton proof never mentions error images. It sets up a reference system entangled with the logical qubits and tracks information: an erasable block of qubits must, by no-cloning, contain nothing about the logical state, and subadditivity of entropy then forces the remaining qubits to be numerous enough to hold it. Degeneracy changes which errors are distinct, but it changes nothing about where quantum information can live, so the entropic argument is untouched.

Is the five-qubit code actually used, given that it is optimal?

It is used as a benchmark far more than as a workhorse. Being the smallest single-error-correcting code, it is the cheapest way to demonstrate a full round of quantum error correction, and it has been realized in NMR, trapped ions, nitrogen-vacancy centers, and superconducting qubits for exactly that reason. But optimality in the counting sense is not the same as convenience for fault tolerance: the five-qubit code lacks a transversal set of Clifford gates, which the CSS-structured Steane code has, and it is not naturally suited to the local-connectivity, high-degeneracy layout that surface codes exploit for scalable operation. So it is the textbook proof of principle, while larger, "wasteful" codes dominate real roadmaps.

Where does the split between

d-1

and

(d-1)/2

come from?

It is the difference between located and unlocated errors. If you know which qubits were damaged — an erasure — a distance- $d$ code can recover from up to $d-1$ of them, because the surviving qubits still determine the logical state. That $d-1$ is what the Singleton bound uses. If you do not know where the errors are — a general Pauli error — you must both locate and fix them, which halves your budget to $t=\lfloor(d-1)/2\rfloor$ corrected errors, the quantity in the Hamming count. Same distance $d$ , two different operational guarantees: $d-1$ erasures or $\lfloor(d-1)/2\rfloor$ arbitrary errors.

Quantum Hamming and Singleton Bounds

Where this lives today

The physical picture

The core equations

Limiting cases

Worked examples

1 · The five-qubit code saturates both bounds (fully worked)

2 · A bounds survey — which $[[n,1,d]]$ codes can exist?

Physics of the portrait

Going further

Before this

Where this leads

Quantum Hamming and Singleton Bounds

Where this lives today

The physical picture

The core equations

Limiting cases

Worked examples

1 · The five-qubit code saturates both bounds (fully worked)

2 · A bounds survey — which [[n,1,d]][[n,1,d]][[n,1,d]] codes can exist?

Physics of the portrait

Going further

Before this

Where this leads

2 · A bounds survey — which $[[n,1,d]]$ codes can exist?