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.

\[\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.