The Exercise

Take $n$ qubits and $n-k$ operators $g_1, \dots, g_{n-k}$ on them, each a tensor product of Pauli matrices, one on each qubit. Suppose they commute with one another and are independent: the bit vectors that record where each of them has an $X$ factor and where it has a $Z$ factor are linearly independent over $\mathbb{Z}_2$. The states that every $g_i$ leaves unchanged then form a subspace $V_S$, stabilized by $S = (g_1, \dots, g_{n-k})$, of dimension $2^k$: smaller than the $2^n$ dimensions of the $n$ qubits by one factor of two for each generator.

Pauli Strings

The Pauli matrices are the four complex $2 \times 2$ matrices $\sigma_0 = I$, $\sigma_1 = X$, $\sigma_2 = Y$ and $\sigma_3 = Z$, with rows and columns labelled by $0$ and $1$: $$\sigma_0 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad \sigma_1 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad \sigma_2 = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \quad \sigma_3 = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}.$$(1)^✦

A Pauli string $g$ on $n$ qubits is an operator on the state space $(\mathbb{C}^2)^{\otimes n}$ of the qubits of the form $g = \sigma_{a_1} \otimes \cdots \otimes \sigma_{a_n}$, with one Pauli matrix $\sigma_{a_k}$, $a_k \in \{0, 1, 2, 3\}$, on each qubit $k$ and no phase in front. In the computational basis $|i\rangle = |i_1 \cdots i_n\rangle$, labelled by bit strings $i \in \{0,1\}^n$, its matrix entries are products of the entries of its factors: $$\langle i | g | j \rangle = \prod_{k=1}^{n} (\sigma_{a_k})_{i_k j_k}.$$(2)^✦

Check Rows

The check bits $(x_a, z_a)$ of a single qubit Pauli $\sigma_a$ are its $X$ bit and its $Z$ bit in $\mathbb{Z}_2$, which mark an $X$ factor and a $Z$ factor: $$(x_0, z_0) = (0, 0), \quad (x_1, z_1) = (1, 0), \quad (x_2, z_2) = (1, 1), \quad (x_3, z_3) = (0, 1).$$(3)^✦

The check row $r(g)$ of a Pauli string $g = \sigma_{a_1} \otimes \cdots \otimes \sigma_{a_n}$ is the pair of its $X$ part $x_g$ and its $Z$ part $z_g$, two binary vectors indexed by the qubits, whose entries on qubit $k$ are the check bits of $\sigma_{a_k}$: $$r(g) = (x_g \,|\, z_g), \qquad x_g = (x_{a_1}, \dots, x_{a_n}), \quad z_g = (z_{a_1}, \dots, z_{a_n}) \in \mathbb{Z}_2^n.$$(4)^✦

The check matrix of Pauli strings $g_1, \dots, g_m$ on $n$ qubits is the binary matrix with $m$ rows and $2n$ columns whose rows are $r(g_1), \dots, r(g_m)$.

The Stabilized Subspace

The stabilized subspace $V_S$ of a list $S = (g_1, \dots, g_m)$ of Pauli strings on $n$ qubits is the subspace of $(\mathbb{C}^2)^{\otimes n}$ made of the vectors that every $g_i$ leaves fixed: $$V_S = \bigcap_{i=1}^{m} \bigl\{ |\psi\rangle \in (\mathbb{C}^2)^{\otimes n} : g_i |\psi\rangle = |\psi\rangle \bigr\}.$$(5)^✦

The Claim

What Is Checked

The claim is stated over the subspace $V_S$ of (5), fixed by the Pauli strings (2) built from the matrices (1), and over the check rows (4) of those strings, read from the check bits (3).