Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 32 / 1 / Solution

Over a finite field ${\mathbb{F}}_q$, a linear code of length $N$ and dimension $k$ is a $k$-dimensional subspace $C\subseteq {\mathbb{F}}_q^N$. A full-row-rank generator matrix $G\in {\mathbb{F}}_q^{k\times N}$ gives $C=\{mG:m\in {\mathbb{F}}_q^k\}$, using row-vector messages. A full-row-rank parity-check matrix $H\in {\mathbb{F}}_q^{(N-k)\times N}$ gives $C=\{x:H{x}^T=0\}$. The dual code is $C^{\perp }=\{y:x\cdot y=0\text{ for all }x\in C\}$, of dimension $N-k$. Thus the rows of $H$ span $C^{\perp }$, andConversely the rank conditions and $H{G}^T=0$ imply that the row space of $G$ equals the kernel of $H$, by inclusion and equality of dimensions.

For a CSS code, specialize to binary linear codes $C_2\subseteq C_1\subseteq {\mathbb{F}}_2^N$, of dimensions $k_2,k_1$. Define orthonormal encoded statesDifferent cosets have disjoint computational-basis support. Their span has dimension $2^{k_1-k_2}$, so it encodes $K=k_1-k_2$ logical qubits. For binary vectors write $X(u)={⨂}_j{X}_j^{u_j}$ and $Z(v)={⨂}_j{Z}_j^{v_j}$. The stabilizer generators are $X(u)$ for a basis of $C_2$, and $Z(v)$ for a basis of $C_1^{\perp }$. They fix each encoded state: the former permute its coset terms and the latter contribute phases $(-1{)}^{v\cdot (x+y)}=1$. Their commutation relation is $X(u)Z(v)=(-1{)}^{u\cdot v}Z(v)X(u)$, so the classical dual inclusion $C_1^{\perp }\subseteq C_2^{\perp }$ makes them commute. There are $k_2+N-k_1=N-K$ independent checks, giving precisely this encoded space.

For a Pauli error $X(e)Z(f)$, the Z checks give bit-error syndrome $H_1{e}^T$, where $H_1$ checks $C_1$, and the X checks give phase-error syndrome $G_2{f}^T$, where $G_2$ generates $C_2$ and hence checks $C_2^{\perp }$. Classical decoders therefore correct up to $t_X$ bit flips and $t_Z$ phase flips if $d(C_1)>2t_X$ and $d(C_2^{\perp })>2t_Z$. A Y error has both components; it is not omitted from this correction scheme.

For the precise quantum code distance, harmless stabilizer errors must be excluded. A pure-X error preserves the code exactly when $e\in C_1$, and is a stabilizer when $e\in C_2$; a pure-Z error preserves it when $f\in C_2^{\perp }$, and is a stabilizer when $f\in C_1^{\perp }$. Consequently, for $K>0$,A mixed Pauli error has weight equal to the size of the union of its X and Z supports. If it is a nontrivial logical operator, at least one component is nontrivial, so its weight is at least $\min (d_X,d_Z)$; pure-X or pure-Z operators attain that minimum. Thus $t=\lfloor (d-1)/2\rfloor$ arbitrary-qubit errors are correctable: products of two such Pauli errors have weight below $d$ and act scalarly on the code, or take it to an orthogonal syndrome sector. This is the Knill--Laflamme condition. Expanding arbitrary errors in the Pauli basis extends correction to their coherent linear span.

An explicit example is the Steane code. Take $C_1$ to be the binary Hamming code withThe distinct nonzero columns show that $C_1$ has no weight-one or weight-two word, while three dependent columns give a weight-three word. Hence its classical distance is three. Direct multiplication gives $H{H}^T=0$, proving $C_2\subseteq C_1$. Every nonzero word of $C_2$ has weight four, so the logical X and Z distances are both three. Its six stabilizer checks are the X and Z strings given by the three rows of $H$. A logical basis is the uniform superposition over $C_2$ and over $1+C_2$, since $1=(1,\dots ,1)\in C_1\setminus C_2$. The resulting $[[7,1,3]]$ CSS code corrects every single-qubit error.