The Exercise

Encoding a stabilizer code on $n$ qubits starts from $|0\rangle^{\otimes n}$, whose stabilizer is generated by $Z_1, \dots, Z_n$; the generator $Z_i$ is $Z$ on qubit $i$ and the identity on every other qubit.^✦ A unitary $U$ carries this stabilizer to the one generated by the $U Z_i U^\dagger$, and it encodes the code when these are the generators of the code together with its encoded $Z$ operators.

A Pauli string $g$ on $n$ qubits is a tensor product $g_1 \otimes \cdots \otimes g_n$ of single qubit operators $g_k \in \{I, X, Y, Z\}$, taken up to an overall phase. The check bits of a single qubit Pauli operator are its $X$ bit, which is $1$ for $X$ and $Y$ and $0$ for $I$ and $Z$, and its $Z$ bit, which is $1$ for $Y$ and $Z$ and $0$ for $I$ and $X$.^✦ The check row of $g$ lists the check bits of its factors, $$r(g) = (x \,|\, z) \in \mathbb{Z}_2^n \times \mathbb{Z}_2^n, \qquad (x_k, z_k) = \text{the check bits of } g_k,$$(1)^✦ and the check matrix of a family of Pauli strings has their check rows as its rows.

Let the code encode $k$ qubits, with its generators in standard form. Their check matrix, with the check rows of the encoded $Z$ operators below it, is $$\left[\begin{array}{ccc|ccc} I & A_1 & A_2 & B & 0 & C \\ 0 & 0 & 0 & D & I & E \\ 0 & 0 & 0 & A_2^{T} & 0 & I \end{array}\right],$$(2) where $I$ and $0$ are identity and zero blocks, $A_1, A_2, B, C, D, E$ are binary matrices, $r$ is the number of generators with an $X$ part, and the columns on either side of the bar fall into blocks of $r$, $n-k-r$ and $k$. The check matrix of $Z_1, \dots, Z_n$ is $(0 \,|\, I)$, and Problem 10.3 asks for a circuit that takes it to (2).

Gates and Circuits

An elementary Clifford gate on $n$ wires, one for each qubit, is a Hadamard gate $H_j$ on a wire $j$, a phase gate $S_j$ on a wire $j$, or a controlled NOT gate $\mathrm{CNOT}_{c \to t}$ (CNOT) with control $c$ and a different target $t$.^✦ A Clifford circuit is a finite sequence of such gates; the sequence $G_1, \dots, G_m$ stands for the unitary $G_1 G_2 \cdots G_m$, in which $G_m$ acts first.^✦

A gate $G$ acts on a Pauli string $g$ by conjugation, taking it to $G g G^\dagger$ up to phase: $H_j$ and $S_j$ change only the factor on wire $j$, a CNOT only the factors on its two wires.^✦ A circuit acts gate by gate, and $U g U^\dagger$ is the Pauli string that the circuit $U$ makes of $g$.^✦

The controlled $Z$ gate on two different wires $c$ and $t$ is the circuit $$\mathrm{CZ}_{ct} = H_t \, \mathrm{CNOT}_{c \to t} \, H_t .$$(3)^✦

The Encoding Circuit

Standard form data on $n$ wires consist of three pairwise disjoint groups of wires, the pivots $\mathcal P$ and the data wires $\mathcal D$, each listed without repetition, and the middle wires $\mathcal M$, together with a list $T(w)$ of distinct targets for every wire $w$; the targets of a pivot are middle or data wires, and those of a data wire are middle wires.^✦ For (2) the pivots are the first $r$ wires, the middle wires the next $n-k-r$ and the data wires the last $k$; $T(p)$ is the support of row $p$ of $(A_1\; A_2)$, and $T(d)$ the support of column $d$ of $E$.

The Hadamard layer $H_{\mathcal P} = \prod_{p \in \mathcal P} H_p$ puts a Hadamard on every pivot.^✦ The CNOT fan $F_c$ from a wire $c$ to its targets applies $\mathrm{CNOT}_{c \to t}$ for each $t \neq c$ in $T(c)$ in turn^✦, and the CNOT network $N = \prod_c F_c$ runs over the pivots $c$ and then the data wires $c$, in the order listed.^✦ The core is the Clifford circuit $V$ made of the Hadamard layer $H_{\mathcal P}$ followed by the CNOT network $N$, $$V = N \, H_{\mathcal P} .$$(4)^✦

For a list $W$ of wires, the phase layer $S_W = \prod_{w \in W} S_w$ puts a phase gate on every wire of $W$^✦; for a list $\Gamma$ of pairs of wires, the controlled $Z$ network $\mathrm{CZ}_\Gamma$ is the product of $\mathrm{CZ}_{ab}$ over the pairs $(a, b)$ of $\Gamma$ with $a \neq b$.^✦ The phase and controlled $Z$ network $S_W\,\mathrm{CZ}_\Gamma$ placed after the core gives the encoding circuit $$U_{W,\Gamma} = S_W \, \mathrm{CZ}_\Gamma \, V .$$(5)^✦

The Claim

For a set $A$ of wires, $\mathbf 1_A \in \mathbb{Z}_2^n$ is its indicator vector, and $v|_A$ is the vector that agrees with $v \in \mathbb{Z}_2^n$ on $A$ and vanishes off it; $e_p$ is $\mathbf 1_{\{p\}}$, and the subscript $p$ on a matrix marks its row $p$.

What Is Checked

The claim is stated over the encoding circuit (5) of standard form data, and over the check rows of the images of the generators $Z_i$ under its action by conjugation. For every list $W$ of distinct wires and every list $\Gamma$ of pairs of distinct wires, the check rows of $U_{W,\Gamma} Z_d U_{W,\Gamma}^\dagger$ on the data wires^✦ and of $U_{W,\Gamma} Z_m U_{W,\Gamma}^\dagger$ on the middle wires equal those of the core $V$ alone.^✦ For $B$ and $C$ satisfying (8), phase and controlled $Z$ gates away from the middle wires can be chosen so that the pivot rows take the form (9).^✦