The Exercise

An $[n,k,d]$ stabilizer code stores $k$ qubits in $n$ and has distance $d$. Suppose the noise acts only on a known set $L$ of qubits, at most $d-1$ of them, while the error it leaves there is unknown: any tensor product of Pauli matrices on the qubits of $L$, with any overall phase. The exercise is to show that the code corrects every such error.

The Pauli Group

The Pauli matrices are the four complex $2 \times 2$ matrices $\sigma_0 = I$, $\sigma_1 = X$, $\sigma_2 = Y$ and $\sigma_3 = Z$, where $I$ is the identity and $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \qquad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}.$$(1)^✦

The state space of $n$ qubits is $\mathbb{C}^{2^n}$, with its basis labelled by the bit strings $x \in \{0,1\}^n$. A Pauli string on $n$ qubits is an operator $\sigma_{a_1} \otimes \cdots \otimes \sigma_{a_n}$ on this space, fixed by a choice $a_k \in \{0,1,2,3\}$ of one Pauli matrix for each qubit $k$; its entry in row $x$ and column $y$ is $\prod_k (\sigma_{a_k})_{x_k y_k}$.^✦ The support of a Pauli string $a$ is the set of qubits $k$ with $a_k \neq 0$, those on which its factor is not the identity.^✦

The Pauli group $G_n$ on $n$ qubits consists of the elements $p$ given by a phase power $s$, an integer modulo $4$, and a Pauli string $a = a(p)$.^✦ The matrix of $p$ is its Pauli string times 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 element $-I$ of $G_n$ is the identity string with phase power $s = 2$, whose matrix is $i^2 I = -I$.^✦ The weight $\operatorname{wt}(p)$ of an element $p$ of $G_n$ is the number of qubits in the support of its string: $$\operatorname{wt}(p) = \bigl|\{\, k : a_k(p) \neq 0 \,\}\bigr|.$$(3)^✦

A Stabilizer Code

The code is fixed by its stabilizer $S$, a finite subgroup of $G_n$ that does not contain $-I$. The code projector $P_S$ of $S$ is the sum of the matrices of its elements divided by the order of $S$, $$P_S = \frac{1}{|S|} \sum_{s \in S} s.$$(4)^✦ The code space $V_S$ of $S$ is the subspace of $\mathbb{C}^{2^n}$ onto which $P_S$ projects.

The normalizer $N(S)$ of $S$ is the set of elements $g$ of $G_n$ with $g S g^{-1} = S$. The distance $d(S)$ of the code is the smallest weight of an element of $N(S)$ whose Pauli string differs from that of every element of $S$, and $d(S) = \infty$ when there is none: $$d(S) = \min \bigl\{\, \operatorname{wt}(p) : p \in N(S),\ a(p) \neq a(s) \text{ for every } s \in S \,\bigr\}.$$(5)^✦

The Claim

Each element of $G_n$ is an error on the $n$ qubits. An element of $G_n$ is located on a set $L$ of qubits when the support of its string lies in $L$.

A quantum operation $\mathcal{R}$ on $\mathbb{C}^{2^n}$ corrects an error $E$ on a code when, for every state of the code, applying $\mathcal{R}$ after $E$ returns that state. A set of errors is correctable on the code with stabilizer $S$ when there is a quantum operation with finitely many operation elements $R_o$ on $\mathbb{C}^{2^n}$, $\sum_o R_o^\dagger R_o = I$, that corrects every error of the set on the code with projector $P_S$.

Taking for $d$ the distance of an $[n,k,d]$ code, the second theorem is the exercise.

What Is Checked

Both theorems are stated over the Pauli group $G_n$ with its phases and strings, the matrix (2) of each element as an operator on $\mathbb{C}^{2^n}$, the code projector (4), and the distance (5), built on the normalizer of $S$ and on the weight (3).