Tranversal gates in permutation-invariant codes and CSS 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_n=\{\ket{\Psi}\in(\mathbb{C})^2)^{\otimes{n}} \mid U_{(i j)}\ket{\Psi}=\ket{\Psi} \  \text{for all} \ i\neq j \}.$$

 Let $\vec{b}=b_1b_2\dots b_n \in\{0,1\}^n$ with $b_i\in\{0,1\}$, and let $\ket{\vec{b}}\in(\mathbb{C}^2)^{\otimes n}$ be a $n$-qubit computational basis state. More explicitly, $\ket{\vec{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(\vec{b})=\SUM{i=1}{n}b_i,$$
  which simply counts the number of $1$s appearing in the bit string $\vec{b}$, and call $\omega(\vec{b})$ the \emph{weight} of $\vec{b}$.
 
It was shown in a previous post that a basis of $Q_n$ is given by the $n+1$ states of the form
 
  $$\ket{\omega_k}=\frac{1}{\sqrt{\binom{n}{k}}}\SUM{ \ \ \vec{b} \  : \  \omega(\vec{b})=k}{}\ket{\bar{b}},$$
   
  where each basis state $\ket{\omega_k}$, for $k\in\{0,1,\dots, n\}$, consists of an equally weighted superposition of the $\binom{n}{k}$ computational basis states $\ket{\vec{b}}$ with weight $\omega(\vec{b})=k$.


 Consider the two dimensional subspace of $Q_n$ which is spanned by the following two states:
  $$\begin{align*}  \ket{\overline{0}}&:=\ket{\omega_0}=\TENSOR{i=1}{n}\ket{0}=\ket{\vec{0}}, \\  \ket{\overline{1}}&:=\frac{1}{\sqrt{2^n-1}}\SUM{k=1}{n}\sqrt{\binom{n}{k}}\ket{\omega_k} \\  &=\frac{1}{\sqrt{2^n-1}}\SUM{\vec{b}\neq\vec{0}}{}\ket{\vec{b}},  \end{align*}$$
 and note that $\ip{\overline{0}}{\overline{1}}=0$. Moreover, since each of $\ket{\overline{0}}$ and $\ket{\overline{1}}$ are given by superpositions of basis states of $Q_n$ each state is left invariant under the action of $U_{(ij)}$ for any transposition $(ij)\in S_n$. Therefore, the two dimensional subspace spanned by $\ket{\overline{0}}$ and $\ket{\overline{1}}$ is a valid subcode of $Q_n$. 

  Now, observe the action of the transversal Hadamard gate applied to each of the $n$ qubits of the state $\ket{\overline{0}}$

$$\begin{align*}  H^{\otimes n}\ket{\overline{0}}&= H^{\otimes n}\ket{\vec{0}} \\   &=\frac{1}{\sqrt{2^n}}\SUM{\vec{b}\in\{0,1\}^n}{}\ket{\vec{b}} \\   &=\frac{1}{\sqrt{2^n}}\ket{\vec{0}}+\frac{1}{\sqrt{2^n}}\SUM{\vec{b}\neq \vec{0}}{}\ket{\vec{b}} \\   =&\frac{1}{\sqrt{2^n}}\ket{\vec{0}}+\frac{\sqrt{2^n-1}}{\sqrt{2^n}}\left(\frac{1}{\sqrt{2^n-1}}\SUM{\vec{b}\neq \vec{0}}{}\ket{\vec{b}}\right) \\   &=\sqrt{2^{-n}}\ket{\overline{0}}+\sqrt{1-2^{-n}}\ket{\overline{1}}. \\  \end{align*}$$

 Instead, observe the action of $H^{\otimes n}$ on the state $\ket{\overline{1}}$:
$$\begin{align*}  H^{\otimes n}\ket{\overline{1}}&= \frac{1}{\sqrt{2^n-1}}\SUM{\vec{b}\neq\vec{0}}{}H^{\otimes n}\ket{\vec{b}} \\  &= \frac{1}{\sqrt{2^n-1}\sqrt{2^n}}\SUM{\vec{b}\neq\vec{0}}{}\SUM{ \ \vec{c}\in\{0,1\}^n}{}(-1)^{\vec{b}\cdot\vec{c}}\ket{\vec{c}} \\  &= \frac{1}{\sqrt{2^n-1}\sqrt{2^n}}\SUM{\vec{b}\neq\vec{0}}{}(-1)^{\vec{b}\cdot\vec{0}}\ket{\vec{0}} + \frac{1}{\sqrt{2^n-1}\sqrt{2^n}}\SUM{\vec{b}\neq\vec{0}}{}\SUM{ \ \vec{c}\neq\vec{0}}{}(-1)^{\vec{b}\cdot\vec{c}}\ket{\vec{c}}  \\   &= \frac{2^n-1}{\sqrt{2^n-1}\sqrt{2^n}}\ket{\vec{0}} + \frac{1}{\sqrt{2^n-1}\sqrt{2^n}}\SUM{\vec{b}\neq\vec{0}}{}\SUM{ \ \vec{c}\neq\vec{0}}{}(-1)^{\vec{b}\cdot\vec{c}}\ket{\vec{c}}  \\   &= \sqrt{1-2^{-n}}\ket{\vec{0}} + \frac{1}{\sqrt{2^n-1}\sqrt{2^n}}\SUM{\vec{b}\neq\vec{0}}{}\SUM{ \ \vec{c}\neq\vec{0}}{}(-1)^{\vec{b}\cdot\vec{c}}\ket{\vec{c}}  \\  &= \sqrt{1-2^{-n}}\ket{\vec{0}} + \frac{1}{\sqrt{2^n-1}\sqrt{2^n}}\SUM{\vec{c}\neq\vec{0}}{}\left(\SUM{ \ \vec{b}\neq\vec{0}}{}(-1)^{\vec{b}\cdot\vec{c}}\right)\ket{\vec{c}}  \\   &= \sqrt{1-2^{-n}}\ket{\vec{0}} + \frac{1}{\sqrt{2^n}}\frac{1}{\sqrt{2^n-1}}\SUM{\vec{c}\neq\vec{0}}{}\left(-1\right)\ket{\vec{c}}  \\     &= \sqrt{1-2^{-n}}\ket{\overline{0}} - \sqrt{2^{-n}}\ket{\overline{1}}.  \\  \end{align*}$$

 Thus, in summary the action of $H^{\otimes n}$ on $\ket{\overline{0}}$ and $\ket{\overline{1}}$ is given by:
  $$\begin{align*}  \ket{\overline{0}}&\overset{H^{\otimes n}}\mapsto \sqrt{2^{-n}}\ket{\overline{0}}+\sqrt{1-2^{-n}}\ket{\overline{1}} \\   \ket{\overline{1}}&\overset{H^{\otimes n}}\mapsto \sqrt{1-2^{-n}}\ket{\overline{0}}-\sqrt{2^{-n}}\ket{\overline{1}},  \end{align*}$$

 which is given by the logical operation $\overline{U}$ given by the matrix expressed in the logical basis as
  $$\overline{U}=\begin{pmatrix}  \sqrt{2^{-n}} & \sqrt{1-2^{-n}}\\   \sqrt{1-2^{-n}}&-\sqrt{2^{-n}} \\  \end{pmatrix}.$$

Transitioning now into the setting of CSS codes, let $H_1, H_2$ be parity check matrices such that $Q=CSS(H_1,H_2)$ is a $[[n,k,d]]$-CSS code. The matrix of stabilizers for this code is given by the binary symplectic matrix
  $$S= \left(\begin{array}{c | c}   0&H_1 \\   H_2 & 0   \end{array}\right)$$
 
  The action of conjugation by a transversal Hadamard applied to the symplectic matrix $S$ transforms it to 
    $$S'=H^{\otimes n}SH^{\otimes n \dagger} \left(\begin{array}{c | c}   0&H_2 \\   H_1 & 0   \end{array}\right)$$
 
  Suppose that $H^{\otimes n}$ preserves the code space so that $H^{\otimes n}Q=Q$. This action must send codewords of $Q$ to codewords of $Q$ and only permute the set of stabilizers of the code.  Since $H^{\otimes n}$ effectively turns $X$-type generators into $Z$-type generators, then it must be the case that any row $r_i$ of $H_1$ lies in the span of the rows of $H_2$, and likewise that any row $r'_i$ of $H_2$ lies in the span of the rows of $H_1$. That is, $Row(H_1)\subseteq Row(H_2)$ and $Row(H_2)\subseteq Row(H_1)$, which is equivalent to the condition that
  $$Row(H_1)=Row(H_2),$$  
  where $row(H_i)$ represents the space spanned by rows of $H_i$.
 
  Now, suppose instead that $Row(H1)=Row(H_2)$. This implies that a row of $H_1$ (or $H_2$) can be expressed in terms of the rows of $H_2$ (or $H_1$). Then after the action of a transversal Hadamard $H^{\otimes n }$, each $X$-type (or $Z$-type) stabilizer will be transformed into a $Z$-type ($X$-type) stabilizer that can be generated by the original set of $Z$-type ($X$-type) stabilizers. Hence, the action of $H^{\otimes n}$ preserves the codespace: $H^{\otimes n}Q=Q$.
 
Therefore, the condition that $Row(H_1)=Row(H_2)$ is both a necessary and sufficient condition for $H^{\otimes n}Q=Q$. If $H_1=H_2$, then trivially $Row(H_1)=Row(H_2)$ so that $H^{\otimes n}Q=Q$.


Suppose that $H=H_1=H_2$ and $n$ is odd. Let $Row(H)$ be the space spanned by the rows of $H$, and assume that $|v|=\sum_{j=1}^{n}=0 \ (mod \ 2)$ for every $v\in Row(H)$. Note that this implies that $\vec{1}\in Row(H)^\perp\backslash Row(H)$, where $\vec{1}=(1,\dots,1)$ ($n$ times).

Therefore, the operators given by $X^{\otimes n}$ and $Z^{\otimes n}$ are in the normalizer of the stabilizer for $Q$, because each stabilizer will commute with $X^{\otimes n}$ and $Z^{\otimes n}$ as the size of the intersection of the supports of any stabilizer with either $X^{\otimes n}$ and $Z^{\otimes n}$ is even. Moreover, $X^{\otimes n}$ and $Z^{\otimes n}$ are not in the stabilizer since every stabilizer acts nontrivially only on an even number of physical qubits whereas $X^{\otimes n}$ and $Z^{\otimes n}$ acts on all $n$ qubits (where $n$ is odd). Hence, the operators $X^{\otimes n}$ and $Z^{\otimes n}$ yield a logical operation on $Q$ on some encoded qubit. Without loss of generality associate these logical operations to act on the first encoded qubit:
$$\begin{align*} \overline{X}_1&=X^{\otimes n} \\ \overline{Z}_2&=Z^{\otimes n} \end{align*}$$

Consider then the logical basis states for the $1$st encoded qubit: $\ket{\overline{0}}_1$ and $\ket{\overline{1}}_1$. In this basis, these states can be expressed as:
$$\begin{align*} \ket{\overline{0}}_1\bra{\overline{0}}_1&=\frac{I+\overline{Z}}{2} \\ \ket{\overline{1}}_1\bra{\overline{1}}_1&=\frac{I-\overline{Z}}{2}. \end{align*}$$

Then since $HXH^\dagger=Z$ and $HZH\dagger=X$, this implies that $H^{\otimes n}\overline{X}H^{\otimes n \dagger}=\overline{Z}$ and $H^{\otimes n}\overline{Z}H^{\otimes n \dagger}=\overline{X}$. Therefore,
$$\begin{align*} H^{\otimes n}\left(\frac{I+\overline{Z}}{2}\right)H^{\otimes n \dagger}&=\frac{I+\overline{X}}{2}=\ket{\overline{+}}_1\bra{\overline{+}}_1 \\ H^{\otimes n}\left(\frac{I-\overline{Z}}{2}\right)H^{\otimes n \dagger}&=\frac{I-\overline{X}}{2}=\ket{\overline{-}}_1\bra{\overline{-}}_1, \end{align*}$$
  where $\ket{\overline{+}}=\frac{1}{\sqrt{2}}(\ket{\overline{0}}_1+\ket{\overline{1}}_1)$ and $\ket{\overline{-}}=\frac{1}{\sqrt{2}}(\ket{\overline{0}}_1-\ket{\overline{1}}_1)$. Hence, the action of $H^{\otimes n}$ on the logical computational basis of the first encoded qubit is given by a logical Hadamard on that encoded qubit:
$$\begin{align*}   \ket{\overline{0}}&\overset{\overline{H}}\mapsto\ket{\overline{+}},\\   \ket{\overline{1}}&\overset{\overline{H}}\mapsto\ket{\overline{-}}.   \end{align*}$$
 
  In regards to the action of $H^{\otimes n}$ on the rest of the $k-1$ encoded qubits, recall that $H^{\otimes n}$ preserves the code space. Therefore, $H^{\otimes n}$ merely permutes the individual stabilizers. More generally, $H^{\otimes n}$ is in the Clifford group $C_n$. Thus, it must be the case that $H^{\otimes n}=\overline{H}\otimes \overline{C}$, where $\overline{C}$ is some logical Clifford operation since $H^{\otimes n}$ is a Clifford operation.    
 

Probabilistic implementation of gates by cyclic permutation and measurement

Given an $n$- qubit Pauli operator $P=P_1\otimes \cdots \otimes P_n$, with $P_j\in\{I,X,Y,Z\}$, let $\eta(P)=P_2\otimes P_3\otimes\cdots\otimes P_n\otimes P_1$ be the Pauli operator obtained by cyclically permuting the factors. Let $S$ be a stabilizer with generators $\{M_j\}_j$, and let $\{\overline{X}_l,\overline{Z}_l\}_l$ be generators of $N(S)/S$. Consider the stabilizer $\eta(S)$ defined by generators $\{M'_j:=\eta(M_j)\}_j$, and the associated generators $\{\overline{X}'_l=\eta(\overline{X}_l), \overline{Z}'_l=\eta(\overline{Z}_l)\}_l$ of $N(\eta(S))/\eta(S)$.
Consider the following process:

1. Start with some encoded state $\ket{\overline{\Psi}}$ for $S$.
2. Measure all the stabilizer generators of $\eta(S)$.
3. Output `success' and the post-measurement state if all outcomes are $+1$.

Let $S$ be the stabilizer of the $[[5,1,3]]$-code, and let $\ket{\overline{\Psi}}\in\mathcal{T}(S)$ be an arbitrary encoded state.

The stabilizer generators $S=<M_1,M_2,M_3,M_4>$ for this 5-qubit code, are given by
$$\begin{align*} M_1=&X \ Z \ Z \ X \ I \\ M_2=& I \ X \ Z \ Z \ X \\ M_3=& X \ I \ X \ Z \ Z \\ M_4=& Z \ X \ I \ X \ Z , \end{align*}$$
and so the resulting generators for $\eta(S)=<M'_1,M'_2,M'_3,M'_4>$ are given by
$$\begin{align*} M'_1=&Z \ Z \ X \ I \ X \\ M'_2=&X \ Z \ Z \ X \ I \\ M'_3=& I \ X \ Z \ Z \ X \\ M'_4=& X \ I \ X \ Z \ Z. \\ \end{align*}$$

Observe that $M'_2=M_1$, $M'_3=M_2$, $M'_4=M_3$, and that $M'_1=M_1M_2M_3M_4$. Thus, each of the generators $M'_j$ can be expressed in terms of the generators of $S$, which implies that $\eta(S)=S$. Since each $M\in S=\eta(S)$ satisfies $M\ket{\overline{\Psi}}=\ket{\overline{\Psi}}$, measuring the stabilizer generators $M'_j$ will always yield an outcome corresponding to $+1$, and the state will be left invariant as $\ket{\overline{\Psi}}$.  In regards to the procedure outlined above, the success probability will be $1$, and the post-measurement state will be $\ket{\overline{\Psi}}$.


Consider the set of stabilizers $S=<M_1,M_2>$ and generators of $N(S)/S=<\overline{X}_1,\overline{Z}_1,\overline{X}_2,\overline{Z}_2>$ given by
$$\begin{align*} M_1=&X \ X \ X \ I  \\ M_2=& I \ Z \ Z \ I  \\ \overline{X}_1=& I \ X \ X \ I \\ \overline{Z}_1=& Z \ I \ Z \ I   \\ \overline{X}_2=& I \ I \ I \ X \\ \overline{Z}_3=&I \ I \ I \ Z. \end{align*}$$

Then the stabilizer generators of $\eta(S)=<M'_1,M'_2>$ are given by
$$\begin{align*} M'_1=&X \ X \ I \ X  \\ M'_2=& Z \ Z \ I \ I.  \\ \end{align*}$$
It is readily seen that $\{M'_1,M_i\}=0$ and $[M'_2,M_i]=0$, for $i=1,2$, implying that $M'_1\notin N(S)$, and that $M'_2\in N(S)$ but $M'_2\notin S$.


Consider the set of stabilizer generators of $S=<M_1,M_2>$ and generators of \\ $N(S)/S=<\overline{X}_1,\overline{Z}_1,\overline{X}_2,\overline{Z}_2>$ given by
$$\begin{align*} M_1 =& X \ X \ X \ I \\ M_2 =& I \ Z \ Z \ I \\ \overline{X}_1=& I \ X \ X \ I \\ \overline{Z}_1=& Z \ I \ Z \ I \\ \overline{X}_2=& I \ I \ I \ X \\ \overline{Z}_2=& I \ I \ I \ Z, \\ \end{align*}$$

and the generators of $\eta(S)$ and $N(\eta(S))/\eta(S)$ given by

$$\begin{align*} M'_1 =& X \ X \ I \ X \\ M'_2 =& Z \ Z \ I \ I \\ \overline{X}'_1=& X \ X \ I \ I \\ \overline{Z}'_1=& I \ Z \ I \ Z \\ \overline{X}'_2=& I \ I \ X \ I \\ \overline{Z}'_2=& I \ I \ Z \ I. \\ \end{align*}$$

Suppose the initial state is an encoded state $\ket{\overline{\Psi}}=\ket{\overline{+}}_1\otimes\ket{\overline{0}}_2$. Here, $\ket{\overline{+}}_1$ is interpreted as an encoded state of $3$ physical qubits, and the other encoded state $\ket{\overline{0}}_2$ in the tensor product is an encoded state represented by a single qubit.

More explicitly, consider the state $\frac{1}{\sqrt{2}}(\ket{000}+\ket{111})$ and observe that
$$\overline{X}_1\frac{1}{\sqrt{2}}(\ket{000}+\ket{111})=\frac{1}{\sqrt{2}}(\ket{011}+\ket{100}),$$
 which suggests the encoded basis is given by
  $$\ket{\overline{0}}_1= \frac{1}{\sqrt{2}}(\ket{000}+\ket{111}) \ \ \text{and} \ \ \ket{\overline{1}}_1=\frac{1}{\sqrt{2}}(\ket{011}+\ket{100}).$$
 For the second encoded qubit, it must be that $\ket{\overline{0}}_2=\ket{0}$ and $\ket{\overline{1}}_2=\ket{1}$.

 Hence, the intitial encoded state is of the form
$$\begin{align*}  \ket{\overline{\Psi}}=&\ket{\overline{+}}_1\ket{\overline{0}}_2 \\  =&\frac{1}{\sqrt{2}}(\ket{\overline{0}}_1+\ket{\overline{1}}_1)\ket{\overline{0}}_2 \\  =&\frac{1}{\sqrt{2}}(\ket{000}+\ket{111}+\ket{011}+\ket{100})\ket{0} \\  =&\frac{1}{\sqrt{2}}(\ket{0000}+\ket{1110}+\ket{0110}+\ket{1000}).  \end{align*}$$

Consider the two permuted stabilizer $M'_1$ and $M'_2$. Note that $M'_1$ anticommutes with all of the logical Pauli operators in $N(S)/S$ so that $M'_1\notin N(S)$.  On the contrary, note that $M'_2$ does commute with all generators of $N(S)/S$, yet is not in the stabilizer $S$ since it cannot be generated by $M_1$ and $M_2$. Therefore, $M'_2\in N(S)\backslash S$, and can be expressed as a logical operation as $M'_2=\overline{Z}_1M_2$.

 Now suppose the operator $M'_2$ is measured on the encoded state $\ket{\overline{\Psi}}$. Since $M'_2=\overline{Z}_1M_2$ has the effect of applying a logical $Z$ operation on the first encoded qubit, which is in the state $\ket{\overline{+}}$, the probability of observing a $+1$ eigenvalue is $1/2$. In this case, the state after measuring $M'_2$ can be determined by applying the projector into the $+1$ eigenstate of $M'_2$:
$$\begin{align*}  \frac{1}{2}(I+M'_2)\ket{\overline{\Psi}}=&\frac{1}{2}(I+\overline{Z}_1M_2)(\ket{\overline{+}}_1\ket{\overline{0}}_2)\\  =&\frac{1}{2}(\ket{\overline{+}}_1\ket{\overline{0}}_2+\ket{\overline{-}}_1\ket{\overline{0}}_2) \\  =&\frac{1}{2}\ket{\overline{0}}_1\ket{\overline{0}}_2 \end{align*}$$

Thus, after renormalization the resulting state is given by $\ket{\overline{0}}_1\ket{\overline{0}}_2$.

Now, consider measuring $M'_1$. Since $M'_1\notin N(S)$, it commutes with exactly half of the Paulis and anticommutes with the other half. This gives a $1/2$ probability of measuring a $+1$ eigenvalue. Hence, the overall success probability of measuring a $+1$ outcome for both operators $M'_1$ and $M'_2$ is given by $1/4$.

Moreover, the resulting state after this second measurement is made is determined via the projector:
$$\begin{align*}  \frac{1}{2}(I+M'_1)\ket{\overline{0}}_1\ket{\overline{0}}_2=&\frac{1}{2\sqrt{2}}(I+M'_1)(\ket{000}\ket{0}+\ket{111}\ket{0}) \\  =&\frac{1}{2\sqrt{2}}(\ket{000}\ket{0}+\ket{111}\ket{0}+\ket{110}\ket{1}+\ket{001}\ket{1})\\  \rightarrow& \ \frac{1}{2}(\ket{000}\ket{0}+\ket{111}\ket{0}+\ket{110}\ket{1}+\ket{001}\ket{1}), \end{align*}$$
 where the resulting state has been normalized accordingly.

 In the context of the permuted stabilizer $\eta(S)$, the $2$nd encoded qubit now appears physically in the $3$rd register of the system. Then by effectively permuting the qubits cyclically, the final state can be expressed in the form
  $$\begin{align*} \ket{\psi_{final}}=& \frac{1}{2}(\ket{000}\ket{0}+\ket{011}\ket{1}+\ket{111}\ket{0}+\ket{100}\ket{1}) \\ =&\frac{1}{2}((\ket{000}+\ket{111})\ket{0}+(\ket{011}+\ket{100})\ket{1})\\ =&\frac{1}{2}(\ket{\overline{0}}_1\ket{\overline{0}}_2+\ket{\overline{1}}_1\ket{\overline{1}}_2),  \end{align*}$$
 showing that the state is entangled between logical qubits.

Clifford circuits for stabilizer codes

 Consider the quantum code $T(S)$ defined by the encoding circuit shown below:



The initial state is of the form $\ket{\psi}\ket{0}\ket{+}$, where $\ket{\psi}$ is an arbitrary single qubit state to be encoded. Two stabilizers $M_1$ and $M_2$ acting on the three qubits can be associated to this initial state such that $\ket{0}$ is a $+1$ eigenstate of $M_1$ and $\ket{+}$ is a $+1$ eigenstate of $M_2$. Since $Z\ket{0}=\ket{0}$ and $X\ket{+}=\ket{+}$, then $M_1=IZI$ and $M_2=IIX$. The ``logical" Pauli operators in this case are simply $\overline{X}=XII$ and $\overline{Z}=ZII$.

When passing through some gate $U$ in an encoding circuit the stabilizer generators and logical Pauli operators after the action of the gate $U$ can be updated to new stabilizer generators $M'_1, M'_2$ and new logical Paulis $\overline{X}', \overline{Z}'$ given by conjugation by $U$:
$$M'_1=UM_1U^\dagger , M'_2=UM_2U^\dagger, \overline{X}'=U\overline{X}U^\dagger, \overline{Z}'=U\overline{Z}U^\dagger.$$

In the table shown below, such an updating procedure is shown for every gate in the encoding circuit. The following relations were used throughout
$$\begin{align*} &HXH=Z, \ \  HZH=X , \ \ \ \  RXR^\dagger=Y, \ \  RZR^\dagger=Z \\ &CNOT(X\otimes I)CNOT=X\otimes X, \  \  CNOT(I\otimes X)CNOT=I\otimes X \\ &CNOT(Z\otimes I)CNOT=Z\otimes I, \ \  CNOT(I\otimes Z)CNOT=Z \otimes Z \end{align*}$$



Therefore, the stabilizer generators of $S$ are $M_1=-YZY$ and $M_2=-XXY$, and the logical Pauli operators corresponding to generators of $N(S)/S$ are $\overline{X}=IYX$ and $\overline{Z}=-XXY$.


Let $\delta$ be an $n\times n$ matrix and $S$ a $2n\times 2n$ matrix given as
$$S=\begin{pmatrix} 0 & \delta \\ \delta & 0 \end{pmatrix},$$
where here $0$ is an $n\times n$ matrix. By definition, $S$ is symplectic if and only if $J=S^TJS$, where
$$J=\begin{pmatrix} 0 &I \\ I & 0 \end{pmatrix}.$$
Then since
$$\begin{pmatrix} 0 &I \\ I & 0 \end{pmatrix}=\begin{pmatrix} 0 &\delta^T \\ \delta^T & 0 \end{pmatrix}\begin{pmatrix} 0 &I \\ I & 0 \end{pmatrix} \begin{pmatrix} 0 &\delta \\ \delta & 0 \end{pmatrix} =\begin{pmatrix} 0 &\delta^T\delta \\ \delta^T\delta & 0 \end{pmatrix},$$
in order for $S$ to be a symplectic matrix it must be the case that $I=\delta^T\delta$. Let the columns of the matrix $\delta$ be given by $\vec{r}_i\in\mathbb{Z}^n_2$ for $i\in\{1,\dots,n\}$. Then the condition $I=\delta^T\delta$ can then be interpreted as requiring each row $\vec{r}_i$ to have unit norm, $\vec{r}_i\cdot\vec{r}_i=1 (mod \ 2)$, and also that distinct rows be orthogonal, $\vec{r}_i\cdot\vec{r}_j=0 (mod \ 2)$ for $i\neq j$.

Now let the matrix $\delta=(d_{a,b})_{a,b}$ be given by
$$d_{a,b}= \left\{ \begin{array}{ll} 1 \ \ \text{for} \ \ a \neq b\\ \\ 0\ \ \text{for} \ \ a=b\\ \end{array} \right.$$

Then the condition $\delta^T\delta=I$, implies that  $\delta^T\delta=\delta^2=(\sum_{i=1}^{n}d_{a,i}d_{i,b})_{a,b}=(\delta_{a,b})_{a,b}=I$. Therefore, $\sum_{i=1}^{n}d_{a,i}d_{i,a}=\sum_{i=1}^{n}d^2_{a,i}=n-1(mod 2)=1$ and $\sum_{i=1}^{n}d_{a,i}d_{i,b}=n-2(mod 2)=0$, which implies that $n$ must be even. Hence the matrix
$$S=\begin{pmatrix} 0 & \delta \\ \delta & 0 \end{pmatrix},$$
is symplectic if and only if $n$ is even.

Consider the case $n=4$ with $\delta$ defined as above. Then
$$S=\begin{pmatrix} 0 &0 & 0& 0 & 0 & 1 & 1&1 \\ 0 &0 & 0& 0 & 1 & 0 & 1&1 \\ 0 &0 & 0& 0 & 1 & 1 & 0&1 \\ 0 &0 & 0& 0 & 1 & 1 & 1&0 \\ 0 &1 & 1& 1 & 0 & 0 & 0&0 \\ 1 &0 & 1& 1 & 0 & 0 & 0&0 \\ 1 &1 & 0& 1 & 0 & 0 & 0&0 \\ 1 &1 & 1& 0 & 0 & 0 & 0&0 \\ \end{pmatrix}$$
The objective here will be to find symplectic matrices $V_{L,k},V_{R,k}\in\{H, CNOT\}$ such that
$$\left(\PROD{k=1}{g_L}V_{L,k} \right)S\left(\PROD{k=1}{g_R}V_{R,k} \right)=I.$$
This would then imply that
$$\left(\PROD{k=g_l}{1}V^\dagger_{L,k} \right)\left(\PROD{k=g_R}{1}V^\dagger_{R,k} \right)=S,$$
giving a decomposition of $S$ in terms of $H$ and $CNOT$ gates alone. Actually, in what follows, only matrices acting from the left will be considered, so that $g_R=0$ and
$$\left(\PROD{k=1}{g_L}V_{L,k} \right)S=I \ \ \text{so that} \ \ \left(\PROD{k=g_L}{1}V^\dagger_{L,k} \right)=S$$
In general, for a symplectic matrix in the block form:
$$U=\begin{pmatrix} A & B \\ C & D \end{pmatrix},$$
the action of multiplying on the left by $H_i$ has the effect of switching the $i$th rows of $(A | B )$ and $(C | D )$. The action of $CNOT_{i,j}$ has the effect of adding the $i$th row of $(A |B)$ to the $j$th row of $(A | B )$, and adding the $j$th row of $( C | D )$ to the $i$th row of $(C|D)$.

Consider the following sequence of transformations:
$$\begin{align*} S=\begin{pmatrix} 0 &0 & 0& 0 & 0 & 1 & 1&1 \\ 0 &0 & 0& 0 & 1 & 0 & 1&1 \\ 0 &0 & 0& 0 & 1 & 1 & 0&1 \\ 0 &0 & 0& 0 & 1 & 1 & 1&0 \\ 0 &1 & 1& 1 & 0 & 0 & 0&0 \\ 1 &0 & 1& 1 & 0 & 0 & 0&0 \\ 1 &1 & 0& 1 & 0 & 0 & 0&0 \\ 1 &1 & 1& 0 & 0 & 0 & 0&0 \\ \end{pmatrix} \overset{CN_{4,1}CN_{3,1}CN_{2,1}}\rightarrow& \begin{pmatrix} 0 &0 & 0& 0 & 1 & 1 & 1&1 \\ 0 &0 & 0& 0 & 1 & 0 & 1&1 \\ 0 &0 & 0& 0 & 1 & 1 & 0&1 \\ 0 &0 & 0& 0 & 1 & 1 & 1&0 \\ 0 &1 & 1& 1 & 0 & 0 & 0&0 \\ 1 &1 & 0& 0 & 0 & 0 & 0&0 \\ 1 &0 & 1& 0 & 0 & 0 & 0&0 \\ 1 &0 & 0& 1 & 0 & 0 & 0&0 \\ \end{pmatrix} \\ \overset{CN_{1,4}CN_{1,3}CN_{1,2}}\rightarrow& \begin{pmatrix} 0 &0 & 0& 0 & 1 & 1 & 1&1 \\ 0 &0 & 0& 0 & 1 & 0 & 0&0 \\ 0 &0 & 0& 0 & 0 & 0 & 1&0 \\ 0 &0 & 0& 0 & 0 & 0 & 0&1 \\ 1 &0 & 0& 0 & 0 & 0 & 0&0 \\ 1 &1 & 0& 0 & 0 & 0 & 0&0 \\ 1 &0 & 1& 0 & 0 & 0 & 0&0 \\ 1 &0 & 0& 1 & 0 & 0 & 0&0 \\ \end{pmatrix} \\ \overset{CN_{4,1}CN_{3,1}CN_{2,1}}\rightarrow& \begin{pmatrix} 0 &0 & 0& 0 & 1 & 0 & 0&0 \\ 0 &0 & 0& 0 & 0 & 1 & 0&0 \\ 0 &0 & 0& 0 & 0 & 0 & 1&0 \\ 0 &0 & 0& 0 & 0 & 0 & 0&1 \\ 1 &0 & 0& 0 & 0 & 0 & 0&0 \\ 0 &1 & 0& 0 & 0 & 0 & 0&0 \\ 0 &0 & 1& 0 & 0 & 0 & 0&0 \\ 0 &0 & 0& 1 & 0 & 0 & 0&0 \\ \end{pmatrix} \\ \overset{H_{1}H_{2}H_{3}H_{4}}\rightarrow& \begin{pmatrix} 1 &0 & 0& 0 & 0 & 0 & 0&0 \\ 0 &1 & 0& 0 & 0 & 0 & 0&0 \\ 0 &0 & 1& 0 & 0 & 0 & 0&0 \\ 0 &0 & 0& 1 & 0 & 0 & 0&0 \\ 0 &0 & 0& 0 & 1 & 0 & 0&0 \\ 0 &0 & 0& 0 & 0 & 1 & 0&0 \\ 0 &0 & 0& 0 & 0 & 0 & 1&0 \\ 0 &0 & 0& 0 & 0 & 0 & 0&1 \\ \end{pmatrix}=I \end{align*}$$

Recalling that $H^\dagger=H$ and $CNOT^\dagger=CNOT$, and reversing the order of the operations used above then yields a sequence of operations that implements $S$ (the rightmost operation is applied first) :

$$S=CN_{2,1}CN_{3,1}CN_{4,1}CN_{1,2}CN_{1,3}CN_{1,4}CN_{2,1}CN_{3,1}CN_{4,1}H_{4}H_{3}H_{2}H_{1}.$$

A circuit diagram depicting this sequence is shown below: