Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 35 / 2 / Solution

For a classical error-correcting code of length $n$, alphabet size $q$, minimum Hamming distance $d$ and $M$ codewords, the Singleton bound isFor a linear $[n,k,d{]}_q$ code this is $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 isMore generally replace $k$ by ${\log }_{2}K$ 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$: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$: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 ⟩⟨\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 giveAdding 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 giveAdding and cancelling gives $k\le S(C)$. The Von Neumann entropy of $D$-dimensional states is at most ${\log }_{2}D$: 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 }_{2}D$. 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.