Pages

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.


Graph states


Let $G=(V,E)$ be a undirected graph with so self-loops. That is, for all $v,v'\in V$, $(v,v)\notin E$, and  if $(v,v')\in E$ then also $(v',v)\in E$. Associate a qubit to each vertex in $V$. When necessary, the vertices will be indexed as $v_i$ with $i\in\{1,\dots, N\}$ where $|V|=N$. Let $I_N=I^{\otimes N}$ be the identity operator on all $N$ qubits, where $I$ is the identity operator on a single qubit. For some single qubit unitary $U$, write $U_{v_i}=I\otimes\cdots\otimes I\otimes U\otimes\cdots\otimes I$ to denote the operator on the $N$-qubit space which applies the single qubit unitary $U$ to the qubit associated to vertex $v_i$. Now, define the operators
\[
M_v=X_v\PROD{v':(v,v')\in E}{} Z_{v'}
\]
for $v\in V$, where $X_v$ and $Z_v$ are the single qubit $X$ and $Z$ operators acting on the qubit associated to vertex $v$.


 For compatible operators $A$ and $B$, let $[A,B]=ABA^{-1}B^{-1}$. If $[A,B]=I$, then $A$ and $B$ \emph{commute}, and if $[A,B]=-I$ then $A$ and $B$ \emph{anticommute}. Now observe the following commutation relations:
\[
\begin{align*}
\text{for any} \ v_i,v_j\in V:& \ \ \ [I_N,X_{v_i}]=[I_N,Z_{v_i}]=[X_{v_i},X_{v_j}]=[Z_{v_i},Z_{v_j}]=I_N\\
\text{if} \  v_i\neq v_j:& \ \ \ [X_{v_i},Z_{v_j}]=I_N\\
\text{if} \ v_i=v_j:& \ \ \ [X_{v_i},Z_{v_j}] =-I_N.
\end{align*}
\]
These then imply the following commutation relations:
\[
\begin{align*}
\text{for any} \ v_i,v_j\in V:& \ \ \ \left[\PROD{v':(v_i,v')\in E}{} Z_{v'} \ , \ \PROD{v':(v_j,v')\in E}{} Z_{v'}\right]=I_N \\
\text{if} \ (v_i,v_j)\notin E:& \ \ \ \left[X_{v_i} \ , \ \PROD{v':(v_j,v')\in E}{} Z_{v'}\right]=I_N \\
\text{if} \ (v_i,v_j)\in E:& \ \ \ \left[X_{v_i} \ , \ \PROD{v':(v_j,v')\in E}{} Z_{v'}\right]=-I_N.
\end{align*}
\]

Trivially, for any graph $G$ and $v\in V$, the operator $M_v$ commutes with itself since $M_v^2=I_N$ as $M_v$ is only comprised of $X$ and $Z$ terms which satisfy $X^2=I$ and $Z^2=I$.  Therefore, consider graphs $G$ with more than one vertex so that $|V|\geq 2$. For any two $M_{v_i}, M_{v_j}\in \{M_v\}_{v\in V}$ such that $v_i\neq v_j$, there are two cases two consider: either $(v_i,v_j)\notin E$ or $(v_i,v_j)\in E$.

Suppose first that $(v_i,v_j)\notin E$. Then $ Z_{v_j}$ does not appear in $M_{v_i}$, and likewise $Z_{v_i}$ does not appear in $M_{v_j}$. Then in the product $M_{v_i}M_{v_j}$, the pairs of operators that act on any particular qubit all commute. Therefore, $M_{v_i}M_{v_j}=M_{v_j}M_{v_i}$ so that $M_{v_i}$ and $M_{v_j}$ commute as well in this case.

Instead, suppose that $(v_i,v_j)\in E$. In this case, $ Z_{v_j}$ does appear in $M_{v_i}$, and likewise $Z_{v_i}$ appears in $M_{v_j}$. Then in the product $M_{v_i}M_{v_j}$ there are two pairs of operators that anticommute--namely,  $X_{v_i}Z_{v_i}$  and $Z_{v_j}X_{v_j}$. Then since $X_{v_i}Z_{v_i}=-Z_{v_i}X_{v_i}$ and $Z_{v_j}X_{v_j}=-X_{v_j}Z_{v_j}$, the two resulting $-1$ factors will cancel. Hence, that $M_{v_i}M_{v_j}=M_{v_j}M_{v_i}$ implying that $M_{v_i}$ and $M_{v_j}$ commute. To see this more explicitly, consider the calculation shown below, which makes use of the nontrivial commutation relations given above:
\[
\begin{align*}
M_{v_i}M_{v_j}=&\left(X_{v_i}\PROD{v':(v_i,v')\in E}{} Z_{v'} \right)\left(X_{v_j}\PROD{v':(v_j,v')\in E}{} Z_{v'} \right)\\
&=(-1)X_{v_i}X_{v_j}\PROD{v':(v_i,v')\in E}{} Z_{v'}\PROD{v':(v_j,v')\in E}{} Z_{v'} \\
&=(-1)X_{v_j}X_{v_i}\PROD{v':(v_j,v')\in E}{} Z_{v'}\PROD{v':(v_i,v')\in E}{} Z_{v'} \\
&=(-1)(-1)X_{v_j}\PROD{v':(v_j,v')\in E}{} Z_{v'}X_{v_i}\PROD{v':(v_i,v')\in E}{} Z_{v'} \\
&=\left(X_{v_i}\PROD{v':(v_i,v')\in E}{} Z_{v'} \right)\left(X_{v_j}\PROD{v':(v_j,v')\in E}{} Z_{v'} \right)\\
&=M_{v_j}M_{v_i}.
\end{align*}
\]
It has now been shown that all operators in the set $\{M_v\}_{v\in V}$ commute with one another.

Since each operator $M_v$ contains the operator $X_v$, and any other $M_{v'}$ with $v\neq v'$ contains a different $X_{v'}$ operator, $M_v$ cannot be generated as a product of other $M_{v'}$ operators. Thus, the set $\{M_v\}_{v\in V}$ forms an independent set of commuting Pauli operators. Then the group $S_G:=<M_v>_{v\in V}$ generated by all $M_v$ forms a valid stabilizer group.

The stabilizer group $S_G=<M_v>_{v\in V}$ defines the code space
\[
T(S_G):=\{\ket{\Psi}\in(\mathbb{C}^2)^{\otimes n} \mid M_v\ket{\Psi}=\ket{\Psi}, \ \text{for all} \ v\in V \}.
\]
Furthermore, since are $|V|=N$ qubits and also $r=N$  independent generators, the number of encoded qubits expressed in $T(S_G)$ is given by $2^{N-r}=2^{0}=1$. Therefore, every graph $G$ can be associated to a unique (up to phase) state $\ket{\Psi_G}\in T(S_G)$ which encodes one logical qubit.



Suppose $G=C_n=(V,E)$ is the $n$-cycle graph with $n> 4$. Here, $V=\{v_1,v_2,\dots,v_n\}$ and $E=\{(v_a,v_b)\mid a\equiv b (mod \ n)\}$. Let $\ket{\Psi_{G}}\in T(S_G)$ be the associated graph state. Let $\mathcal{M}_{\bar{b}}\in S_G$,  Then the projection onto $T(S_G)$ satisfies
 \[
 \ket{\Psi_G}\bra{\Psi_G}=\frac{1}{2^n}\SUM{U_a}{}U_a,
 \]
 since $T(S_G)$ is one dimensional. Denote by $Tr_{(i-1,i,i+1)}(\ket{\Psi_G}\bra{\Psi_G})$, the reduced density operator that results by tracing out all qubit registers except for those associated to neighboring registers $i-1, i$, and $i+1$ (where addition is taken $mod \ n$). Then
 \[
 Tr_{(i-1,i,i+1)}(\ket{\Psi_G}\bra{\Psi_G})=\frac{1}{2^n}\SUM{U_a}{}Tr_{(i-1,i,i+1)}(U_a).
 \]
 Hence, consider $Tr_{(i-1,i,i+1)}(U_a)$ for an arbitrary $U_a\in S_G$. Each $U_a$ is a product of some $M_v$ operators. If  $U_a$ contains some $M_v$ which has nontrivial support on some vertex other than $v_{i-1},v_i$, or $v_{i+1}$, then $Tr_{(i-1,i,i+1)}(U_a)=0$, because the trace of any Pauli operator  is $0$.  Hence, the only nonzero contribution comes from $U_a=I$ and $U_a=M_{v_i}$ so that
\[\begin{align*}
 Tr_{(i-1,i,i+1)}(\ket{\Psi_G}\bra{\Psi_G})=&\frac{1}{2^n}\SUM{U_a}{}Tr_{(i-1,i,i+1)}(U_a)\\
 =&\frac{1}{2^n}\left(Tr_{(i-1,i,i+1)}(I)+Tr_{(i-1,i,i+1)}(M_{v_i})\right)\\
 =&\frac{1}{2^{3}}\left(I+M_{v_i}\right) \\
 =&\frac{1}{2^{3}}\left(I+X_{v_i}Z_{v_{i-1}}Z_{v_{i+1}}\right).
 \end{align*}\]


 Let $G=(V_G,E_G)$ and $G'=(M_{G'},E_{G'})$ be graphs and suppose $G'$ is obtained from $G$ by adding a vertex $v'$ which has no edges. Then $V_{G'}=V_G\cup\{v'\}$, and $E_{G'}=E_G$. Let $\ket{\Psi_G}\in T(S_G)$ and $\ket{\Psi_G'}\in T(S_{G'})$ be the associated graph states of $S_G$ and $S_{G'}$, respectively. In terms of $\ket{\Psi_G}$, the state $\ket{\Psi_{G'}}$ can be expressed as
 \[
 \ket{\Psi_{G'}}=\ket{\Psi_G}\otimes\ket{\varphi},
 \]
 where $\ket{\varphi}$ is a yet to be determined single qubit state.

 In this case, the set of stabilizer generators for $G'$ is given by $\{M_v\}_{v\in V_G}\cup \{M_{v'}\}$, where $M_{v'}=X_{v'}$. All of the operators in $S_G$ act trivially on the state $\ket{\varphi}$ of $\ket{\Psi_{G'}}$, and the operator $M_{v'}$ acts trivially on all registers of the state $\ket{\Psi_{G'}}$ except for the qubit in the state $\ket{\varphi}$. However, since it must be the case that $M_v\ket{\Psi_{G'}}=\ket{\Psi_{G'}}$ for any $M_v\in S_{G'}$, then $\ket{\varphi}$ must be a $+1$ eigenstate of $M_{v'}=X_{v'}$. Therefore, $\ket{\varphi}=\ket{+}:=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$ as
 \[
 X\ket{+}=\frac{1}{\sqrt{2}}(X\ket{0}+X\ket{1})=\frac{1}{\sqrt{2}}(\ket{1}+\ket{0})=\ket{+},
 \]
  which shows that $\ket{+}$ is the unique $+1$ eigenstate of $X$. Hence, the associated graph state of $S_{G'}$ is given by
 \[
 \ket{\Psi_{G'}}=\ket{\Psi_G}\otimes\ket{+}.
 \]
 
  Now suppose $G'=(V_{G'},E_{G'})$ is obtained from $G=(V_{G},E_{G})$ by adding an edge $(v_1,v_2)$, where $(v_1,v_2)\notin E_{G}$, so that $E_{G'}=E_{G}\cup\{(v_1,v_2)\}$ and $V_{G'}=V_{G}$. Let $S_G=<M^G_v>_{v\in V_G}$ and $S_{G'}=<M^{G'}_v>_{v\in V_{G'}}$ be the stabilzer groups generated by the operators $M^G_v$ and $M^{G'}_v$, respectively. Then all  of the operators in $S_{G'}$ and $ S_{G}$ are the same, except the operators $M^{G'}_{v_1},M^{G'}_{v_2}\in S_{G'}$ differ from those in $S_{G}$, by including additional $Z_{v_2}$ and $Z_{v_1}$ terms, respectively. That is,
\[
M^{G'}_{v_i}=
\left\{
\begin{array}{ll}
M^{G}_{v_i} \ \ \text{if} \ \ v_i \neq v_1, v_2 \\
\\
M^{G}_{v_i}Z_2\ \ \text{if} \ \ v_i=v_1\\
\\
M^{G}_{v_i}Z_1\ \ \text{if} \ \ v_i=v_2.\\
\end{array}
\right.
\]


 Consider $\ket{\Psi_{G}}\in T(S_{G})$, and let $\ket{\Phi}=CZ_{z_1,z_2}\ket{\Psi_G}$, where $CZ_{z_1,z_2}$ is the two qubit phase gate applied to the qubits associated to vertices $v_1$ and $v_2$ given by
\[
 CZ=\begin{pmatrix}
 1 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 \\
 0 & 0 &1 & 0  \\
 0 & 0 & 0 & -1
 \end{pmatrix}.
\]
 Since $M^{G'}_{v_i}=M^{G}_{v_i}$ for $v_i\neq v_1, v_2$, and neither $X_{v_1}$ nor $X_{v_2}$ appear as factors in any of the operators  $M^{G'}_{v_i}$ in this case, then each  $M^{G'}_{v_i}$ commutes with $CZ_{z_1,z_2}$. Therefore,
\[
 M^{G'}_{v_i}\ket{\Phi}=M^{G'}_{v_i}CZ_{z_1,z_2}\ket{\Psi_G}=CZ_{z_1,z_2}M^{G'}_{v_i}\ket{\Psi_G}=CZ_{z_1,z_2}\ket{\Psi_G}=\ket{\Phi},
\]
  in the case where $v_i\neq v_1, v_2$.
 
  For the other cases, first observe that $X_{v_1}Z_{v_2}CZ_{v_1,v_2}=CZ_{v_1,v_2}X_{v_1}$. Now suppose $v_i=v_1$, then
\[\begin{align*}
M^{G'}_{v_1}CZ_{z_1,z_2}=&M^{G}_{v_1}Z_{v_2}CZ_{z_1,z_2} \\
=&M^{G}_{v_1}X_{v_1}X_{v_1}Z_{v_2}CZ_{z_1,z_2} \\
=&M^{G}_{v_1}X_{v_1}CZ_{z_1,z_2}X_{v_1}\\
=& CZ_{z_1,z_2}M^{G}_{v_1}X_{v_1}X_{v_1} \\
=&CZ_{z_1,z_2}M^{G}_{v_1}.
 \end{align*}  \]
 Hence,  $M^{G'}_{v_1}\ket{\Phi}=M^{G'}_{v_1}CZ_{z_1,z_2}\ket{\Psi_G}=CZ_{z_1,z_2}M^{G}_{v_1}\ket{\Phi_G}=CZ_{z_1,z_2}\ket{\Psi_G}=\ket{\Phi}$. Therefore, for all $v_i\in V_{G'}$, it follows that $M^{G'}_{v_1}\ket{\Phi}=\ket{\Phi}$, implying that $\ket{\Phi}=CZ_{z_1,z_2}\ket{\Psi_G}\in T(S_{G'})$ is the encoded graph state of $S_{G'}$.

 The consequences just shown can be applied to construct the graph state $\ket{\Psi_{C_4}}$ for the cycle graph $C_4$. In this approach, a Hadamard gate is applied  to each of the four qubits (that all begin in the $\ket{0}$ state) which puts each qubit into the $\ket{+}$  state. Then a controlled phase $CZ_{v_i,v_j}$ for each pair of adjacent vertices is applied. The resulting state produced by this circuit will then be $\ket{\Psi_{C_4}}$.

Permutation-invariant codes

Let $S_n$ be the group of permutations of the $n$-element set $[n]:=\{1 , 2, \dots, n\}$, and let $\pi\in S_n$. Define the unitary $U_\pi: (\mathbb{C}^2)^{\otimes n}\mapsto(\mathbb{C}^2)^{\otimes n}$ by
\[
U_\pi(\ket{\varphi_1}\otimes\cdots\otimes\ket{\varphi_n})=\ket{\varphi_{\pi^{-1}(1)}}\otimes\cdots\otimes\ket{\varphi_{\pi^{-1}(n)}}
\]
for all product states $\ket{\varphi_1}\otimes\cdots\otimes\ket{\varphi_n}$ (and extended linearly to all of $(\mathbb{C})^{\otimes{n}}$). Denote by $(i j)$ the transposition of $i,j\in[n]$ for $i\neq j$, and define the subspace
\[
Q=\{\ket{\Psi}\in(\mathbb{C})^2)^{\otimes{n}} \mid U_{(i j)}\ket{\Psi}=\ket{\Psi} \  \text{for all} \ i\neq j \}.
\]


An arbitrary state $\ket{\Psi}\in Q$ can be written generally as a linear combination
\[
\ket{\Psi}=\SUM{}{}\gamma_k\ket{\xi_k},
\]
 where $\ket{\xi_k}\in\mathcal{B}$ and $\mathcal{B}$ is a complete set of basis vectors of $Q$. Since every $\ket{\xi_k}\in Q$, must also satisfy the constraint $U_{(ij)}\ket{\xi_k}=\ket{\xi_k}$ for all $(ij)\in S_n$, each state $\ket{\xi_k}$ must be comprised of states possessing a property that remains invariant under the $U_{(ij)}$ operations. In this regard, let $\bar{b}=b_1b_2\dots b_n \in\{0,1\}^n$ with $b_i\in\{0,1\}$, and let $\ket{\bar{b}}\in(\mathbb{C}^2)^{\otimes n}$ be a $n$-qubit computational basis state. More explicitly, $\ket{\bar{b}}=\bigotimes_{i=1}^{n}\ket{b_i}$, describes the $n$-qubit state where each qubit is either in the state $\ket{0}$ or $\ket{1}$. Now define the map
 \[
  \omega: \{0,1\}^n\to \{0,1,\dots,n\} \ \ \text{given as} \ \  \omega(\bar{b})=\SUM{i=1}{n}b_i,
  \]
  which simply counts the number of $1$s appearing in the bit string $\bar{b}$, and call $\omega(\bar{b})$ the \emph{weight} of $\bar{b}$.
 
  For every $\bar{b}\in\{0,1\}^n$ and any $\pi\in S_n$, it will always be the case that $U_{\pi}\ket{\bar{b}}=\ket{\bar{b'}}$ for some $\bar{b'}\in\{0,1,\}^n$ such that $\omega(\bar{b})=\omega(\bar{b'})$, because $U_{\pi}$ will only permute the bits $b_i$ comprising the string $\bar{b}$ which preserves the  weight of the string. That is, if $\ket{\bar{b}}=\bigotimes_{i=1}^{n}\ket{b_i}$, then $U_\pi\ket{\bar{b}}=\ket{\bar{b'}}=\bigotimes_{i=1}^{n}\ket{b_{\pi^{-1}(i)}}$, where the bits of the resulting string $\bar{b'}$ are given by $b'_i=b_{\pi^{-1}(i)}$, and consequently $\omega(\bar{b})=\sum_{i=1}^{n}b_i=\sum_{i=1}^{n}b_{\pi^{-1}(i)}=\omega(\bar{b'})$.
 
  Therefore, let
  \[
  \ket{\xi_k}=\frac{1}{\sqrt{\binom{n}{k}}}\SUM{ \ \ \bar{b} \  : \  \omega(\bar{b})=k}{}\ket{\bar{b}}
    \]
  be an equally weighted superposition of the $\binom{n}{k}$ computational basis states $\ket{\bar{b}}$ with weight $\omega(\bar{b})=k$. Then it follows that $U_{(ij)}\ket{\xi_k}=\ket{\xi_k}$ for all $(ij)\in S_n$, since each $U_{(ij)}$ yields a bijection between the set of states $\ket{\bar{b}}$ having the same weight. Hence, the set of basis vectors of $Q$ is given by $\mathcal{B}=\{\ket{\xi_k} \mid  k=0,1,\dots, n\}$ consisting of $n+1$ basis vectors.
 
A projector $P$ onto the subspace $Q$ can be expressed in terms of the basis vectors in $\mathcal{B}$ as
\[
P=\SUM{k=0}{n}\ket{\xi_k}\bra{\xi_k}.
\]

In terms of the operators $U_\pi$, the projector can be equivalently expressed as an equally weighted superposition over all permutations as
\[
P=\frac{1}{n!}\SUM{\pi\in S_n}{}U_\pi
\]


Consider the set of errors
\[
\mathcal{E}=\left\{\SUM{\pi\in S_n}{}a_\pi U_\pi \mid (a_\pi)_{\pi\in S_n} \subset \mathbb{C} \right\}.
\]
 For the group symmetric $S_n$, recall that any permutation $\pi\in S_n$ can be expressed as a product of transpositions only. Actually, $S_n$ can  be generated by the $n-1$ transpositions of the form $(i,i+1)$ for $i\in\{1, 2, \dots, n-1\}$. This algebraic structure extends to the operators $U_\pi$, That is, for any $\pi\in S_n$,
 \[
 U_\pi=\PROD{(ab)\in S_n}{}U_{(ab)},
  \]
  where $(ab)=(i,i+1)$ for some $i\in\{1, 2, \dots, n-1\}$. Note that in this product, any particular $U_{(ab)}$ can appear multiple times. Therefore, for any $\pi\in S_n$ and any $\ket{\psi}\in Q$
  \[
  U_\pi\ket{\psi}=\PROD{(ab)\in S_n}{}U_{(ab)}\ket{\psi}=\ket{\psi},
  \]
  because $U_{(ab)}\ket{\psi}=\ket{\psi}$ for any $(ab)\in S_n$.
 
  In regards to to the correctability of the error set $\mathcal{E}$, consider any $\pi,\pi\in S_n$ and any basis vectors $\ket{\xi_k},\ket{\xi_{k'}}\in\mathcal{B}$. As a consequence of what was just shown $U_{\pi}\ket{\xi_k}=\ket{\xi_k}$ and $U_{\pi'}\ket{\xi_{k'}}=\ket{\xi_{k'}}$. Then,
  \[
  \bra{\xi_{k'}}U_{\pi'}^{\dagger}U_\pi\ket{\xi_k}=\ip{\xi_{k'}}{\xi_k}=\delta_{k'k}.
  \]
 Since the error correction conditions for a code state that
   \[
  \bra{\xi_{k'}}U_{\pi'}^{\dagger}U_\pi\ket{\xi_k}=c_{\pi'\pi}\ip{\xi_{k'}}{\xi_k},
  \]
  where the $c_{\pi'\pi}$ are constants that do not depend on the states $\ket{\xi_k}$ and $\ket{\xi_k'}$, then $c_{\pi'\pi}=1$ for all $\pi,\pi'\in S_n$.
  More generally, for any $\ket{\psi},\ket{\psi'}\in Q$ this implies
  \[
    \bra{\psi'}U_{\pi'}^{\dagger}U_\pi\ket{\psi}=\ip{\psi'}{\psi}
  \]
 
 Therefore, each $U_\pi$ for $\pi\in S_n$ is a correctable error. Then since any linear combination of correctable errors can also be corrected, any error of the form
  \[
  E=\SUM{\pi\in S_n}{}a_\pi U_\pi
  \]
  can be corrected. Thus, the set $\mathcal{E}$ is correctable.
 
 An operator basis $\{F_j\}_j$ of $\mathcal{E}$ which diagonalizes the matrix $C=(c_{ab})$ is given by $F_\pi =U_\pi$, where $\pi\in S_n$. Since the order of $S_n$ is $n!$ (meaning there are $n!$ different permutation operators), there are $n!$ many different operators $U_\pi$ in this basis. Then upon being diagonalized, the coefficients of the matrix $C$ are given by $c_{\pi'\pi}=1$ if $\pi'= \pi$ and $c_{\pi'\pi}=0$ if $\pi'\neq \pi$.
 
  For the subspace $Q$, the set of detectable errors is defined as
 \[
 \mathcal{E}_D:=\left\{E \mid \bra{\psi}E\ket{\phi}=c(E)\ip{\psi}{\phi}, \forall \ket{\psi},\ket{\phi}\in Q\right\}.
 \]
  Consider a single bit flip error, say, $E=X_1$ that applies the bit flip $X$ to the first qubit of the register. Moreover, consider the two basis states $\ket{\xi_0}$ and $\ket{\xi_1}$ of Q. Here, $\ket{\xi_0}=\bigotimes_{i=1}^{n}\ket{0}$ is the unique state with weight $0$, and $\ket{\xi_1}$ is the superposition of all states labelled by weight $1$ bit strings. Observe that $X_1\ket{\xi_0}=\ket{1}\bigotimes_{i=2}^{n}\ket{0}$, which is a state that appears in the superposition of states expressed in $\ket{\xi_1}$. Therefore,
  \[
  \bra{\xi_1}X_1\ket{\xi_0}=\frac{1}{\sqrt{\binom{n}{k}}}\neq 0,
  \]
  but yet $\ket{\xi_1}$ and $\ket{\xi_0}$ are orthogonal basis states so that $\ip{\xi_1}{\xi_0}=0$. Hence, the single bit flip error $E=X_1$ is an undetectable error by definition.  
 

Let $E=X^{\otimes n}$, and consider the two basis states $\ket{\xi_0},\ket{\xi_n}\in\mathcal{B}$ of $Q$. Then
\[
E\ket{\xi_0}=X^{\otimes n}\TENSOR{i=1}{n}\ket{0}=\TENSOR{i=1}{n}\ket{1}=\ket{\xi_1},
\]
Which implies that $\bra{\xi_n}E\ket{\xi_0}=\ip{\xi_n}{\xi_n}=1$. However, $\ip{\xi_n}{\xi_0}=0$ since they are orthogonal basis states, and thus
$E=X^{\otimes n}$ is an undetectable error.

More generally, let $U\in SU(2)$, with $U\neq I$, and consider the error $E=U^{\otimes n}$. According to the Shur-Weyl duality, $[E,U_\pi]=0$ for all $U\in SU(2)$ and $\pi\in S_n$. Consider an arbitrary state $\ket{\psi}\in Q$ so that $U_\pi\ket{\psi}=\ket{\psi}$ for all $\pi\in S_n$ as argued in above. Then,
\[
U_\pi E\ket{\psi}=EU_\pi\ket{\psi}=E\ket{\psi},
\]
Where the first equality follows from the Shur-Weyl duality. This implies that $E\ket{\psi}\in Q$.  Since, $\ket{\psi}$ was assumed to be arbitrary, this is equivalent to the statement $EQ=Q$.

Consider any basis state $\ket{\xi_j}$. Then since $EQ=Q$, it must be the case that $E\ket{\xi_j}\in Q$ so that $E\ket{\xi_j}$  itself can be expressed in terms of the basis $\mathcal{B}$ of $Q$. That is,
\[
E\ket{\xi_j}=U^{\otimes n}\ket{\xi_j}=\SUM{k=1}{n=1}\alpha_k\ket{\xi_k}.
\]
Then there must exist at least one $\alpha_{k'}\neq 0$, and perhaps more. Moreover, since $U\neq I$ by assumption, $k'\neq j$. Choose one such basis state $\ket{\xi_{k'}}$ with $\alpha_{k'}\neq 0$. With this choice,
\[
\bra{\xi_{k'}}E\ket{\xi_j}>0.
\]
However, since $\ip{\xi_k'}{\xi_j}=0$ this implies that
\[
\bra{\xi_{k'}}E\ket{\xi_j}\neq c(E)\ip{\xi_k'}{\xi_j}.
\]
Therefore, the error $E=U^{\otimes n}$ is undetectable.