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\):
For natural numbers \(n\) and \(t\), the number of Pauli strings of length \(n\) whose weight is at most \(t\) is
Here a Pauli string is a function \(p : \mathrm{Fin}\, n \to \{ I,X,Y,Z\} \), and its weight \(\mathrm{wt}(p)\) is the number of coordinates \(i\) with \(p(i) \neq I\); the sum counts, for each \(j \le t\), the \(\binom {n}{j}\) choices of a weight-\(j\) support together with the \(3^{j}\) assignments of a non-identity Pauli to each chosen coordinate.
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).
For every natural number \(n\), the \(n\)-qubit Hilbert space \(\mathcal{H}_n\) has complex dimension \(\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.
Let \(C \le \mathcal{H}_n\) be a code that is non-degenerate for \(t\)-error correction, and let \(E, F\) be Pauli strings on \(n\) qubits with weights \(\mathrm{wt}(E) \le t\) and \(\mathrm{wt}(F) \le t\) and \(E \neq F\). Then the images \(\hat{E}(C)\) and \(\hat{F}(C)\) of \(C\) under the corresponding Pauli operators are orthogonal subspaces of \(\mathcal{H}_n\); that is, \(\langle \hat{E}\, u,\, \hat{F}\, v\rangle = 0\) for all \(u, v \in C\).
Let \(C \le \mathcal{H}_n\) be a code on \(n\) qubits that is non-degenerate for \(t\) errors, meaning it satisfies the Knill–Laflamme condition \(P_C E^\dagger F P_C = \lambda _{EF} P_C\) for all Pauli strings \(E,F\) of weight at most \(t\) and moreover \(P_C E^\dagger F P_C = 0\) whenever \(E \neq F\). Then the error sphere \(\mathrm{ES}(C,t) = \bigvee _{\mathrm{wt}(p)\le t} \hat{p}(C)\) has dimension
where \(\mathcal{E}(n,t)\) is the set of Pauli strings of weight at most \(t\).
13.6 Quantum Hamming bound
Let \(C \le \mathcal{H}_n\) be a subspace of the \(n\)-qubit Hilbert space whose complex dimension is \(\dim _{\mathbb {C}} C = 2^k\), and suppose \(k \le n\). If \(C\) is a non-degenerate code correcting \(t\) errors — meaning it satisfies the Knill–Laflamme condition \(P_C\, E^\dagger F\, P_C = \lambda _{EF}\, P_C\) for all Pauli strings \(E,F\) of weight at most \(t\), and moreover \(P_C\, E^\dagger F\, P_C = 0\) whenever \(E \ne F\), where \(P_C\) is the orthogonal projection onto \(C\) — 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.
Fix \(n\), a finset \(S \subseteq \mathrm{Fin}\, n\), and an assignment \(f : S \to \{ X,Y,Z\} \) of a non-identity Pauli to each coordinate in \(S\). Let \(p\) be the Pauli string of length \(n\) that equals \(f(i)\) at each \(i \in S\) and equals the identity \(I\) at every coordinate outside \(S\). Then the support of \(p\) — the set of coordinates where \(p\) differs from \(I\) — is exactly \(S\).
The finset of all Pauli strings on \(n\) qubits whose support equals exactly the given finset \(S\).
Let \(n\) be a natural number and let \(S \subseteq \mathrm{Fin}\, n\) be a set of coordinates. The number of Pauli strings \(p\) of length \(n\) whose support \(\mathrm{supp}(p)\) equals exactly \(S\) is \(3^{|S|}\).
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\).
Let \(C\) be a closed subspace of the \(n\)-qubit Hilbert space \(\mathcal{H}_n\), and let \(P_C : \mathcal{H}_n \to \mathcal{H}_n\) be the associated orthogonal projection onto \(C\). Then for every \(x \in \mathcal{H}_n\), the value \(P_C\, x\) is exactly the orthogonal projection of \(x\) onto \(C\).
Let \(C\) be a subspace of the \(n\)-qubit Hilbert space \(\mathcal{H}_n\), and let \(P_C : \mathcal{H}_n \to \mathcal{H}_n\) be the orthogonal projection onto \(C\). Then for every \(x \in \mathcal{H}_n\), the projected vector \(P_C\, x\) belongs to \(C\).
Let \(C\) be a subspace of the \(n\)-qubit Hilbert space \(\mathcal{H}_n\), and let \(P_C : \mathcal{H}_n \to \mathcal{H}_n\) be the orthogonal projection onto \(C\). If \(x \in C\), then \(P_C x = x\).
Let \(C\) be a closed subspace of the \(n\)-qubit Hilbert space \(\mathcal{H}_n = \ell ^2(\{ 0,1\} ^n, \mathbb {C})\), and let \(P_C : \mathcal{H}_n \to \mathcal{H}_n\) be the orthogonal projection onto \(C\). Then \(P_C\) is idempotent: for every \(x \in \mathcal{H}_n\),
Let \(C \le \mathcal{H}_n\) be a subspace of the \(n\)-qubit Hilbert space that is a non-degenerate quantum code correcting \(t\) errors, and suppose its complex dimension is \(\dim _{\mathbb {C}} C = 2^{k}\) for some natural number \(k\). Then
Write \(\{ X, Y, Z\} \) for the three non-identity Pauli labels, embedded in the natural way into the full Pauli basis \(\{ I, X, Y, Z\} \). Then the image of every such label differs from the identity element \(I\).
The three-element type \(\{ X, Y, Z\} \) of labels for the non-identity single-qubit Pauli operators. It serves as the index set in counting arguments that enumerate, for a fixed support, the \(3^{|S|}\) assignments of a non-identity Pauli to each supported coordinate.