Quantum Hamming Bound

How many physical qubits does a code need in order to correct $t$ errors? The quantum Hamming bound gives a counting lower bound by demanding that every correctable error have its own orthogonal "room" inside the $2^n$ -dimensional Hilbert space — exactly the picture of distinct syndrome subspaces from the QEC conditions.

Counting correctable errors

Take a non-degenerate $[[n,k,d]]$ code that corrects all errors of weight up to $t = \lfloor (d-1)/2 \rfloor$ . On a single qubit there are $3$ non-trivial Pauli errors ( $X, Y, Z$ ). A weight- $j$ error chooses $j$ of the $n$ qubits and assigns one of $3$ Paulis to each, so the number of weight- $j$ Pauli errors is $\binom{n}{j} 3^j$ . Summing over all weights up to $t$ , the total number of distinct errors (including the identity, $j=0$ ) is

N_{\text{err}} = \sum_{j=0}^{t} \binom{n}{j}\, 3^{\,j}.

The packing argument

For a non-degenerate code, every one of these errors maps the codespace to a distinct, mutually orthogonal subspace — that is what "non-degenerate" means. Each such subspace has dimension $2^k$ (the dimension of the codespace). They must all fit, disjointly, inside the full $2^n$ -dimensional space:

\boxed{\;2^k \sum_{j=0}^{t} \binom{n}{j}\, 3^{\,j} \;\le\; 2^{n}\;}

This is the quantum Hamming bound. It is necessary for any non-degenerate code; degenerate codes can in principle pack more loosely and evade it (more on that in a later lesson).

A perfect code

A code that meets the bound with equality is called perfect — its syndrome subspaces tile the entire Hilbert space with no wasted dimension. The five-qubit code $[[5,1,3]]$ corrects $t=1$ error:

2^{1}\Big(\binom{5}{0}3^0 + \binom{5}{1}3^1\Big) = 2\,(1 + 15) = 32 = 2^{5}.

Equality holds, so $[[5,1,3]]$ is the smallest possible single-error-correcting code — there is literally no room to spare. Contrast the Steane $[[7,1,3]]$ code, for which $2(1+21)=44 < 128$ : it is correct but not perfect, leaving slack.

Try it

For the five-qubit code ( $n=5$ , $k=1$ , correcting $t=1$ error), compute the left-hand side of the quantum Hamming bound, $2^k \sum_{j=0}^{t}\binom{n}{j}3^j$ , from first principles and return it. It should equal $2^5 = 32$ , showing the code is perfect.

Run your code to see the quantum state.