Bounds on Code Parameters

The three parameters of an $[[n,k,d]]$ code cannot be chosen freely: protecting more information (large $k$ ) and tolerating more errors (large $d$ ) both cost physical qubits ( $n$ ). Several inequalities make the trade-offs precise and tell us how close a given code is to optimal.

The quantum Singleton bound

The cleanest universal bound, holding for every code (degenerate or not), is the quantum Singleton bound (the quantum analogue of the classical Singleton bound):

\boxed{\; k \le n - 2(d-1) \;} \qquad \text{equivalently} \qquad n - k \ge 2(d-1).

Each unit of distance beyond 1 costs two qubits of redundancy — twice the classical price — because quantum errors come in two independent flavours ( $X$ and $Z$ ) that must both be corrected. A code meeting this bound with equality is called an MDS (maximum-distance-separable) code; the $[[5,1,3]]$ code saturates it: $1 = 5 - 2(2)$ .

The quantum Hamming bound (non-degenerate only)

For non-degenerate codes the packing argument from the earlier lesson gives

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

Unlike the Singleton bound this can be violated by degenerate codes, which is precisely what makes degeneracy interesting.

The quantum Gilbert–Varshamov bound

Bounds so far are upper limits on how good a code can be. The Gilbert–Varshamov bound is a matching existence (lower) bound: a non-degenerate $[[n,k,d]]$ stabilizer code is guaranteed to exist whenever

2^{\,n-k} > \sum_{j=1}^{d-1} \binom{n}{j}\, 3^{\,j}.

Together, Hamming/Singleton (codes can be no better than this) and Gilbert–Varshamov (codes at least this good exist) bracket the achievable region, and in the asymptotic limit they yield nonzero rate $k/n$ at finite relative distance $d/n$ — good quantum codes exist.

Why two qubits per unit of distance

The factor of 2 in the Singleton bound traces to the symplectic structure. A logical operator must both commute with $n-k$ stabilizer generators and have weight $\ge d$ ; the $X$ - and $Z$ -type constraints are independent, so each step of distance consumes redundancy in two conjugate sectors at once. This is the quantitative shadow of "quantum errors are $X$ and $Z$ ."

The takeaway

Code parameters obey the quantum Singleton bound $n - k \ge 2(d-1)$ (always) and, for non-degenerate codes, the quantum Hamming bound; the Gilbert–Varshamov bound guarantees good codes exist below those ceilings. The recurring factor of two reflects that quantum noise has two independent error types, making quantum redundancy twice as expensive as classical.