= Solution
For a classical <error-correcting code> of length $n$, alphabet size $q$, minimum <Hamming distance> $d$ and $M$ codewords, the <Singleton bound> is
$$
M\le q^{n-d+1}.
$$
For a linear $[n,k,d]_q$ code this is \b[$n-k\ge d-1$]. Deleting any $d-1$ coordinates is injective on the codewords, since two words agreeing on the remaining coordinates would differ in fewer than $d$ positions; this also explains the classical bound.
For an n-<qubit> <quantum code> carrying $k>0$ <logical qubits> and having <quantum code distance> $d$, the <quantum Singleton bound> is
$$
\boxed{n-k\ge2(d-1).}
$$
More generally replace $k$ by $\log_2K$ for code dimension $K>1$. The proof applies to degenerate codes too.
Let $r=d-1$. Purify the maximally mixed encoded input by a reference $R$ of dimension $K$:
$$
|\Omega\rangle=K^{-1/2}\sum_{j=1}^K|j\rangle_R|j_L\rangle,\qquad S(R)=\log_2K=:k.
$$
Distance $d$ makes erasure of any subset of at most $r$ <qubits> correctable. The allowed <quantum erasure correction> condition says that a correctable erased set $A$ is decoupled from $R$:
$$
\rho_{RA}=\rho_R\otimes\rho_A,\qquad S(RA)=k+S(A).
$$
This is the <matrix>-element correction condition in another form: all operators on $A$ have constant diagonal <matrix> elements and zero off-diagonal <matrix> elements in the logical basis, so tracing the other physical <qubits> in $|\Omega\rangle\langle\Omega|$ yields the displayed product.
First justify the sizes needed for the partition. If $2r>n$, partition all physical <qubits> into $A,B$, both of size at most $r$. Both sets are correctable. Purity of $RAB$ and the <Schmidt decomposition> give
$$
k+S(A)=S(RA)=S(B),\qquad k+S(B)=S(RB)=S(A).
$$
Adding forces $k=0$, a contradiction. Thus $2r\le n$, without assuming the bound we aim to prove.
Choose disjoint sets $A,B$ of size $r$, and let $C$ contain the remaining $n-2r$ <qubits>. The joint state $RABC$ is pure, so decoupling and <Subadditivity of Von Neumann entropy> give
$$
k+S(A)=S(RA)=S(BC)\le S(B)+S(C),
$$
$$
k+S(B)=S(RB)=S(AC)\le S(A)+S(C).
$$
Adding and cancelling gives $k\le S(C)$. The <Von Neumann entropy> of $D$-dimensional states is at most $\log_2D$: for positive <eigenvalues> $p_i$, concavity of the <logarithm> gives $\sum_i p_i\log_2(1/p_i)\le\log_2\sum_i p_i/p_i\le\log_2D$. Here $D=2^{n-2r}$, so $k\le n-2r$, proving the quantum bound. The code is assumed to encode information ($K>1$); a one-dimensional code requires a separate distance convention, since simply re-preparing a known state makes its erasure-correction condition vacuous.
Back to article page
