The Exercise

A quantum code on $n$ qubits can be built from two classical codes, one inside the other, by the construction of Calderbank, Shor and Steane (CSS). Problem 10.2 is the bound of Gilbert and Varshamov for these codes: when $4t \le n$, there is a CSS code on $n$ qubits that corrects arbitrary errors on up to $t$ qubits and encodes $k$ qubits, for every natural number $k$ with $$k + 4 \le n\,\bigl[1 - 2H(2t/n)\bigr],$$(1) where $H$ is the binary entropy, $$H(p) = -p\log_2 p - (1-p)\log_2 (1-p).$$(2)

The library states the existence of the pair of classical codes from which such a quantum code is built.

Classical Linear Codes

A linear code $C$ of length $n$ over a field $K$ is a subspace of $K^n$; its elements are its codewords. A binary linear code $C$ is a linear code over the field $\mathbb{Z}_2 = \{0,1\}$ of integers modulo 2; its dimension $\dim C$ is its dimension as a vector space over $\mathbb{Z}_2$.

The weight $\mathrm{wt}(x)$ of a word $x \in K^n$ is the number of its nonzero entries. The minimum distance $d(C)$ of a linear code $C$ is the least weight of a nonzero codeword, $$d(C) = \min\,\{\mathrm{wt}(c) : c \in C,\ c \neq 0\},$$(3)^✦ and is infinite for the zero code, the linear code $\{0\}$ with no nonzero codeword. A linear code $C$ corrects $t$ errors if its minimum distance satisfies $$d(C) \ge 2t + 1.$$(4)^✦

The dual code $C^\perp$ of a linear code $C$ of length $n$ over $K$ is the set of words orthogonal to every codeword, $$C^\perp = \Bigl\{x \in K^n : \sum_{i=1}^{n} x_i c_i = 0 \text{ for every } c \in C\Bigr\}.$$(5)^✦

The Claim

The CSS code built from such a pair corrects the two basic single-qubit errors, a bit flip and a phase flip: $C_1$ corrects the bit flips and $C_2^\perp$ the phase flips, and the code encodes $\dim C_1 - \dim C_2$ qubits, so this is the exercise.

What Is Checked

The claim is stated over binary linear codes of length $n$ and their dimensions, the dual code (5), the minimum distance (3) and the condition (4) for correcting $t$ errors, with the binary entropy (2) in the bound on $k$.

The dual of a linear code is again a linear code of the same length over the same field, a subspace of $K^n$.