## Saturday, 22 March 2014

### 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: