The Exercise

Two classical binary linear codes $C_2 \subseteq C_1$ of length $n$ give a quantum code on $n$ qubits, the code of Calderbank, Shor and Steane (CSS), written $\mathrm{CSS}(C_1, C_2)$ and built from the cosets of $C_2$ in $C_1$. A binary linear code $C$ of length $n$ is a subspace of $\mathbb{Z}_2^n$, the strings of $n$ bits added modulo 2, and its dual code $C^\perp$ consists of the strings $u$ with $u \cdot v = \sum_k u_k v_k = 0$ modulo 2 for every $v \in C$.^✦

The exercise asks first for the stabilizer: $\mathrm{CSS}(C_1, C_2)$ is the stabilizer code whose stabilizer is generated by the operators applying the Pauli matrix $X$ (bit flip) to the qubits where a codeword of $C_2$ has a 1 and those applying the Pauli matrix $Z$ (phase flip) to the qubits where a codeword of $C_1^\perp$ has a 1. It then asks to show that, when $C_1$ and $C_2^\perp$ both correct errors on up to $t$ bits, the quantum code corrects arbitrary errors on up to $t$ qubits.^✦

In the second part, the errors are the tensor products of the Pauli matrices $I$, $X$, $Y$, $Z$ on the individual qubits, with a phase, that act other than as the identity on at most $t$ qubits.

Qubits and the Pauli Group

A quantum system is a physical object whose state space is a finite dimensional complex Hilbert space.^✦ A pure state $|\psi\rangle$ of a system $A$ is a unit vector in the state space of $A$^✦, and a unitary $U$ of $A$ is an operator on that space with $U^\dagger U = U U^\dagger = I$.^✦ The register of $n$ qubits is the system whose state space has the computational basis $\{|w\rangle\}$ as an orthonormal basis, one vector for each bit string $w \in \mathbb{Z}_2^n$.^✦

The Pauli matrices are the four complex $2 \times 2$ matrices $\sigma_0 = I$ and $$\sigma_1 = X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad \sigma_2 = Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \qquad \sigma_3 = Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}.$$(1)^✦ Given indices $a_1, \dots, a_n$ in $\{0, 1, 2, 3\}$, one for each qubit, the Pauli string $\sigma_{a_1} \otimes \cdots \otimes \sigma_{a_n}$ is the operator on $n$ qubits whose matrix element between the basis states $|w\rangle$ and $|w'\rangle$ is the product $\prod_k (\sigma_{a_k})_{w_k w'_k}$ over the qubits.^✦ The support of a Pauli string $\sigma_{a_1} \otimes \cdots \otimes \sigma_{a_n}$ is the set of qubits $k$ with $a_k \neq 0$.^✦

The Pauli group $G_n$ on $n$ qubits consists of the elements $p$ given by a phase power $s \in \mathbb{Z}_4$ and a Pauli string.^✦ The matrix of $p$, a $2^n \times 2^n$ complex matrix with rows and columns labelled by bit strings, is the string multiplied by the phase $i^s$, one of the four fourth roots of unity: $$p = i^s \, \sigma_{a_1} \otimes \cdots \otimes \sigma_{a_n}.$$(2)^✦ The weight $\mathrm{wt}(p)$ of an element $p$ of $G_n$ is the number of qubits in the support of its Pauli string, whatever its phase.^✦

The CSS Code

For a bit string $v$, the element $X^v$ of $G_n$ has phase $1$ and the Pauli string with $X$ on each qubit $k$ where $v_k = 1$ and $I$ on the others^✦; for a bit string $u$, the element $Z^u$ has phase $1$ and the Pauli string with $Z$ where $u_k = 1$.^✦ On the register, $X^v$ and $Z^u$ are the bit flip and phase flip strings, the unitaries with $$X^v |w\rangle = |w + v\rangle, \qquad Z^u |w\rangle = (-1)^{u \cdot w} |w\rangle$$(3) for every bit string $w$.

The CSS stabilizer $S$ of binary linear codes $C_1$ and $C_2$ of length $n$ is the subgroup of $G_n$ generated by the elements $X^v$ with $v \in C_2$ and $Z^u$ with $u \in C_1^\perp$.^✦ For a finite subgroup $S$ of $G_n$, the stabilizer sum $Q$ is the sum of the matrices of its elements^✦, and the code projector $P_S$ is their average over the group, $$P_S = \frac{Q}{|S|} = \frac{1}{|S|} \sum_{s \in S} s,$$(4)^✦ the projector onto the code space of the stabilizer code with stabilizer $S$.

The check operators of $C_1$ and $C_2$ are the generators of the CSS stabilizer, taken as operators on the register’s state space. The stabilized subspace $V_S$ of $C_1$ and $C_2$ is the subspace of the register’s state space made of the vectors that every check operator leaves fixed, $$V_S = \{\, |\psi\rangle : X^v |\psi\rangle = Z^u |\psi\rangle = |\psi\rangle \text{ for all } v \in C_2,\ u \in C_1^\perp \,\}.$$(5)^✦

Given a binary linear code $C_2$ and a bit string $x$, the coset state $|x + C_2\rangle$ is the pure state of the register with equal amplitudes on the basis states $|x + y\rangle$, one for each codeword $y$ of $C_2$: $$|x + C_2\rangle = \frac{1}{\sqrt{|C_2|}} \sum_{y \in C_2} |x + y\rangle.$$(6)^✦ The CSS code space $\mathrm{CSS}(C_1, C_2)$ is the subspace of the register spanned by the coset states $|x + C_2\rangle$ with $x \in C_1$.^✦

The Claim

The second part concerns recovery. A recovery $\mathcal{R}$ on the $n$ qubits is a quantum operation, a map taking every operator $\rho$ on the register to $\mathcal{R}(\rho) = \sum_o R_o \, \rho \, R_o^\dagger$ with finitely many operation elements $R_o$. A recovery $\mathcal{R}$ corrects a set of errors on a projector $P$ when, after any error of the set, it restores every state in the range of $P$ up to normalization.

What Is Checked

The claim (7) is stated over the register of $n$ qubits and its computational basis, the check operators (3), the stabilized subspace (5) and the span of the coset states (6). The claim (8) is stated over the Pauli group $G_n$, with the matrices and the weights of its elements, and over the CSS stabilizer $S$ and its code projector (4).

The library proves that each coset state $|x + C_2\rangle$ has unit norm, and that the bit flip strings $X^v$ and the phase flip strings $Z^u$ are unitaries of the register.