13 Quantum Hamming Bound
13.1 Overview
This chapter proves the quantum Hamming bound for non-degenerate qubit stabilizer codes. Working in the Pauli-string formalism, it shows that if a quantum code \(C \le \mathcal{H}_n\) satisfies the Knill–Laflamme conditions for \(t\)-error correction and is non-degenerate, then
13.2 Pauli strings
The four Pauli basis elements \(\{ I,X,Y,Z\} \), represented as an inductive type.
A Pauli string of length \(n\) is a function \(p : \mathrm{Fin}\, n \to \mathrm{PauliBasis}\).
The support \(\mathrm{supp}(p) \subseteq \mathrm{Fin}\, n\) consists of coordinates where \(p(i) \neq I\); the weight is \(\mathrm{wt}(p) = |\mathrm{supp}(p)|\).
The set of all Pauli strings of weight at most \(t\):
Partition by weight \(j\) and exact support \(S\): each of the \(\binom {n}{j}\) supports of size \(j\) carries \(3^{j}\) strings (card_pauliStringsExactSupport, via the mkWithSupport bijection), and the cells are disjoint. This volume-of-ball count is used implicitly by the sphere-packing arguments of the source papers (Calderbank–Rains–Shor–Sloane cite it as a black box attributed to Gottesman; Ekert–Macchiavello and Knill–Laflamme use it implicitly) but is stated in none of them; full note: references/informalized/QuantumHamming.card_pauliErrorsLe.md.
13.3 \(n\)-qubit Hilbert space
The \(n\)-qubit Hilbert space \(\mathcal{H}_n = \ell ^2\! \bigl(\{ 0,1\} ^n,\mathbb {C}\bigr)\), implemented as EuclideanSpace ℂ (Fin n → Fin 2).
\(\dim _{\mathbb {C}}(\mathcal{H}_n) = 2^n\).
For \(p \in \mathrm{PauliString}\, n\), the associated Pauli operator \(\hat{p} : \mathcal{H}_n \to \mathcal{H}_n\).
13.4 Knill–Laflamme conditions
A subspace \(C \le \mathcal{H}_n\) satisfies the Knill–Laflamme condition for \(t\)-error correction if for all Pauli strings \(E,F\) with \(\mathrm{wt}(E),\mathrm{wt}(F) \le t\) there exists \(\lambda _{EF}\in \mathbb {C}\) such that \(P_C\, E^\dagger F\, P_C = \lambda _{EF}\, P_C\), where \(P_C\) is the orthogonal projection onto \(C\).
A code is non-degenerate if it satisfies the Knill–Laflamme condition and additionally \(P_C E^\dagger F P_C = 0\) whenever \(E \neq F\).
13.5 Error sphere and sphere-packing
The error sphere \(\mathrm{ES}(C,t)\) is the subspace \(\bigvee _{\mathrm{wt}(p)\le t} \hat{p}(C)\), i.e. the supremum of the Pauli images of \(C\) over all \(t\)-errors.
If \(C\) is non-degenerate and \(E \neq F\) both have weight \(\le t\), then \(\hat{E}(C) \perp \hat{F}(C)\).
If \(C\) is non-degenerate,
13.6 Quantum Hamming bound
If \(C \le \mathcal{H}_n\) is non-degenerate, then
13.7 Additional declarations
The \(2\times 2\) identity matrix over \(\mathbb {C}\), i.e. the Pauli operator \(I\).
The bit-flip Pauli matrix \(X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\) over \(\mathbb {C}\).
The bit-phase-flip Pauli matrix \(Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}\) over \(\mathbb {C}\).
The phase-flip Pauli matrix \(Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\) over \(\mathbb {C}\).
Maps each Pauli basis element \(\{ I,X,Y,Z\} \) to its corresponding \(2\times 2\) matrix \(\{ \sigma _I,\sigma _X,\sigma _Y,\sigma _Z\} \).
For a Pauli string \(p\) on \(n\) qubits, the \(2^n\times 2^n\) matrix obtained as the tensor product of the single-qubit Pauli matrices \(\sigma _{p(i)}\) over all coordinates \(i\).
Embeds a non-identity Pauli (\(X\), \(Y\), or \(Z\)) from the three-element type \(\mathrm{PauliNZ}\) into the full Pauli basis \(\{ I,X,Y,Z\} \).
Given a finset \(S \subseteq \mathrm{Fin}\, n\) and an assignment \(f : S \to \mathrm{PauliNZ}\), constructs the Pauli string that equals \(f(i).\mathrm{toBasis}\) on each \(i \in S\) and equals \(I\) elsewhere.
The Pauli string \(\mathrm{mkWithSupport}\, S\, f\) has support exactly \(S\).
The finset of all Pauli strings on \(n\) qubits whose support equals exactly the given finset \(S\).
The number of Pauli strings with support exactly \(S\) is \(3^{|S|}\), since each coordinate in \(S\) is assigned one of the three non-identity Paulis.
An \(n\)-qubit quantum code is a subspace of the \(n\)-qubit Hilbert space \(\mathcal{H}_n\).
The adjoint (Hermitian conjugate) \(\hat{p}^\dagger : \mathcal{H}_n \to \mathcal{H}_n\) of the Pauli operator associated with a Pauli string \(p\).
The orthogonal projection of \(\mathcal{H}_n\) onto a subspace \(C\), viewed as an endomorphism \(P_C : \mathcal{H}_n \to \mathcal{H}_n\).
For any \(x \in \mathcal{H}_n\), the value \(P_C\, x\) coincides with the orthogonal projection \(\Pi _C(x)\) of \(x\) onto \(C\).
For any \(x \in \mathcal{H}_n\), the projected vector \(P_C\, x\) belongs to the code subspace \(C\).
If \(x \in C\), then \(P_C\, x = x\).
The code projection is idempotent: \(P_C(P_C\, x) = P_C\, x\) for all \(x \in \mathcal{H}_n\).
For a non-degenerate \([[n,k]]\) quantum code \(C \le \mathcal{H}_n\) correcting \(t\) errors, with \(\dim _{\mathbb {C}}(C) = 2^k\), the dimension of the error sphere does not exceed the ambient dimension:
For every \(a \in \mathrm{PauliNZ}\), its image \(a.\mathrm{toBasis}\) in the Pauli basis differs from \(I\); that is, the embedding of \(\{ X,Y,Z\} \) never hits the identity element.