## Saturday, 1 February 2014

### CSS codes and the 9-qubit Shor code

In the 9-qubit Shor code, the stabilizer $S$ is generated by the following operators

\begin{align*} S_1=& Z_1Z_2 \\ S_2=&Z_2Z_3 \\ S_3=&Z_4Z_5 \\ S_4=&Z_5Z_6 \\ S_5=&Z_7Z_8 \\ S_6=&Z_8Z_9 \\ S_7=&X_1X_2X_3X_4X_5X_6 \\ S_8=&X_4X_5X_6X_7X_8X_9. \\ \end{align*}
Thus, the the dimension of the code space is $2^{9-8}=2$, which implies that the code only encodes one logical qubit. In this case, $\hat{N}(S)/S\cong \hat{P}_1$, so $\hat{N}/S$ will be generated by some elements $\overline{X}, \overline{Z}\in\hat{N}(S)\backslash S$, satisfying the usual Pauli commutation relations:
$\overline{X}^2=\overline{Z}^2=\overline{I}, \ \text{and} \ \overline{X} \ \overline{Z}=-\overline{Z} \ \overline{X}$
In this regard, let
\begin{align*} \overline{Z}=&X_1X_2X_3X_4X_5X_6X_7X_8X_9 \\ \overline{X}=& Z_1Z_2Z_3Z_4Z_5Z_6Z_7Z_8Z_9 \\ \end{align*}
which satisfy the commutation relations described above. Moreover, $\overline{Z}\in\hat{N}(S)\backslash S$. To see this, note that
\begin{align*} [\overline{Z},S_i]=0&, \ \text{for} \ i=7,8 \\ [\overline{X},S_i]=0&, \ \text{for} \ i=1,2,3,4,5,6 \\ \end{align*}
because each of these ease either a product of only $X$ operators or only $Z$ operators. The less trivial relations
\begin{align*} [\overline{Z},S_i]=0&, \ \text{for} \ i=1,2,3,4,5,6 \\ [\overline{X},S_i]=0&, \ \text{for} \ i=7,8 \\ \end{align*}

also hold, because the intersection of the supports of $\overline{Z}$ and $S_i$ ( for $i=1,2,3,4,5,6$) is always an even number of qubits. Likewise, the intersection of the supports of $\overline{X}$ and $S_i$ ( for $i=7,8$) is also always an even number of qubits. Thus, $\overline{X},\overline{Z}\in \hat{N}(S)$.

Now, to see that $\overline{X},\overline{Z}\notin S$ observe that the product$S_7S_8=X_1X_2X_3X_7X_8X_9\neq\overline{Z}$, which implies $\overline{Z}\notin S$. For $\overline{X}$, it is impossible to even generate an operator that contains all the factors $Z_1Z_2Z_3$ since the only stabilizers that even have nontrivial support on these first three qubits are $S_1$ and $S_2$, but yet  $S_1S_2=Z_1Z_3\neq Z_1Z_2Z_3$. Therefore, $\overline{X}\notin S$.

Consider the binary matrix
$\delta=\begin{pmatrix} 1&1&1&0&0 \\ 0&0&1&1&1\\ 1&1&0&1&1 \\ 1&1&1&0&0 \\ 0&0&1&1&1\\ \end{pmatrix}.$
Associate to each row $j$ an $X$-type stbilizer
$M_j=\PROD{l=1}{5}X_l^{\delta_{jl}},$
and to each column a $Z$-stabilizer
$N_j=\PROD{l=1}{5}Z_l^{\delta_{lj}}.$
The product of the matrix $\delta$ with itself (modulo $2$) effectively computes products of  all the $M_j$ operators with all the $N_j$ operators. The $i,j$th coefficient in the matrix of $\delta^2$,  has a value of $0$ if $M_iN_j$ commute and has a value of $1$ if $M_iN_j$ anticommute. In fact, since $\delta^2$ gives the matrix with all coefficients $0$, each $M_i$ commutes with each $N_j$. Therefore, the set $Q$ generated by all such products of $M_j$ and $N_i$ forms an abelian subgroup of the Pauli group $\hat{P}_5$. Moreover, since each $M_j$ and $N_j$ square to $+I$, it is necessarily the case that $-I\notin Q$. Hence, $Q$ actually defines a stabilizer group. By choosing linearly independent operators $M_j$ and $N_i$, it is seen that the stabilizer $Q$ can be generated by $\{M_1,M_2,N_1, N_4\}$.

Let $C_1$ and $C_2$ be a classical linear codes with parity check matrices $H_1$ and $H_2$ given by

$H_1=\begin{pmatrix} 1&0&1&1&0 \\ 0&1&1&0&1 \end{pmatrix} \ \ \text{and} \ \ H_2=\begin{pmatrix} 1&1&1&0&0 \\ 0&0&1&1&1 \end{pmatrix}.$

Notice that $H_1$ consists of the two $Z$-type stabilizer generators $N_1$ and $N_4$, and $H_2$ consists of the two $X$-type stabilizer generators $M_1$ and $M_2$ defined in (2) that together generate the stabilizer group $Q$. In this way, $Q$ is the CSS code $CSS(H_1,H_2)$. Here, $Q=<S_1\cup S_2>$, where $S_1$ and $S_2$ are the stabilizer groups generated by the $Z$-type and $X$-type operators, respectively.  Namely,
$S_1=\begin{pmatrix} 0&0&0&0&0 \\ 1&0&1&1&0 \\ 0&1&1&0&1 \\ 1&1&0&1&1 \end{pmatrix} \ \ \text{and} \ \ S_2=\begin{pmatrix} 1&0&1&1&0 \\ 1&1&1&0&0 \\ 0&0&1&1&1\\ 1&1&0&1&1 \\ \end{pmatrix}.$

Let $G_1$ and $G_2$ be corresponding generator matrices of the codes $C_1$ and $C_2$, respectively. For each code, since there are $5$ physical bits and $3$ encoded bits ($H_1$ and $H_2$ are $2 \times 5$ matrices), both generator matrices have dimensions $3\times 5$. These generators must satisfy the constraints
$G_iH_i^T=0 \ \ \text{and} \ \ H_iG_i^T=0.$
for $i=1,2$. The constraints form a set of $k$ non-singular equations on $n$ bits. It can be checked that the following two particular matrices satisfy these constraints:
$G_1=\begin{pmatrix} 1&0&0&1&0 \\ 1&1&0&1&1 \\ 0&1&1&1&0 \end{pmatrix} \ \ \text{and} \ \ G_2=\begin{pmatrix} 1&0&1&0&1 \\ 1&1&0&0&0 \\ 0&1&1&1&0 \end{pmatrix}.$

The rows of $G_1$ and $G_2$ form a basis of the code spaces $C_1$ and $C_2$, respectively. Hence, the span of each generates the entire code spaces. The elements of these code spaces are then
$C_1=\begin{pmatrix} 0&0&0&0&0 \\ 1&0&0&1&0 \\ 1&1&0&1&1 \\ 0&1&1&1&0 \\ 0&1&0&0&1 \\ 1&0&1&0&1 \\ 1&1&1&0&0 \\ 0&0&1&1&1 \end{pmatrix} \ \ \text{and} \ \ C_2=\begin{pmatrix} 0&0&0&0&0 \\ 1&0&1&0&1 \\ 1&1&0&0&0 \\ 0&1&1&1&0 \\ 1&0&1&1&0 \\ 0&1&1&0&1 \\ 1&1&0&1&1 \\ 0&0&0&1&1 \\ \end{pmatrix}.$

By associating a $Z$-type (or $X$-type) operator $\overline{Z}$ (or $\overline{X}$) to each row of $C_2$ (or $C_1$), and demanding that $\overline{Z}\notin S_1$ (and $\overline{X}\notin S_2$) and also that $\overline{Z} \ \overline{X}=-\overline{X} \ \overline{Z}$, then the pair $(\overline{X},\overline{Z})$ can be made to correspond to a logical operation on a logical qubit. In this case, since there is only $1$ logical qubit a single pair satisfying these properties is all that is needed. In this regard, choose
$\overline{X}=X_1X_4 \ \ \text{and} \ \ \overline{Z}=Z_1Z_3Z_5$
corresponding to the second rows of $C_2$ and $C_1$. Then indeed, $\overline{X}\notin S_2$ and $\overline{Z}\notin S_1$, and $\overline{Z} \ \overline{X}=-\overline{X} \ \overline{Z}$. Therefore, the pair $(\overline{X},\overline{Z})$ function as logical operators on the encoded qubit, and hence generate $\mathcal{N}(S)/S\cong P_1$.

In the classical linear code context, the distances of codes $C_1$ and $C_2$ are both given by $d_1=d_2=2$, which can be seen by examining the elements of $C_1$ and $C_2$ and finding the minimum weight of any non-identity codeword. For $CSS(H_1,H_2)$, the distance of the code $Q$ must satisfy $d\geq min\{d_1,d_2\}=2$. In this context, the distance of $Q$ will be the minimum weight of an operator in $\mathcal{N}(S)\backslash S$, which by inspection is seen to be $d=2$.

In what follows, an algorithm will be described which begins with two parity check matrices $H_1$ and $H_2$ of a general CSS code, and computes a set of generators for $\hat{\mathcal{N}}(S)/S$ grouped into pairs $\{(\overline{X}_i,\overline{Z}_i)\}$.

First, using $H_1$ and $H_2$ (matrices with dimensions $(n-k)\times n$ construct generator matrices $G_1$ and $G_2$ (of dimensions $k\times n$) satisfying the constraints $G_iH_i^T=0$ and $H_iG^T=0$ for each $i=1,2$. Moreover, the rows of such $G_i$ should be linearly independent. Such a procedure can be done in general using the Gram-Schmidt process.

Next, consider the codes paces $C_i$ defined as the span of the rows of $G_i$, and also the stabilizer spaces $S_i$ defined as the span of the rows of $H_i$. Then to find generators of $\hat{\mathcal{N}}(S)/S$, it suffices to choose pairs $(\overline{X}_l,\overline{Z}_l)$ with $\overline{Z}_l\in C_1\backslash S_1$ and $\overline{X}_l\in C_2\backslash S_2$, such that $\overline{X}_l$ and $\overline{Z}_l$ anti commute, and all pairs $(\overline{X}_l,\overline{Z}_l)$ and$(\overline{X}_l',\overline{Z}_l')$ with $l\neq l'$ commute. For $k$ encoded qubits, there will be $k$ many many pairs, corresponding to the logical operations applied to each of the $k$ logical qubits.