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 ith rows of (A | B ) and (C | D ). The action of CNOT_{i,j} has the effect of adding the ith row of (A |B) to the jth row of (A | B ), and adding the jth row of ( C | D ) to the ith 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:
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 ith rows of (A | B ) and (C | D ). The action of CNOT_{i,j} has the effect of adding the ith row of (A |B) to the jth row of (A | B ), and adding the jth row of ( C | D ) to the ith 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: