## Saturday, 14 December 2013

### The Stabilizer Formalism

Consider the single qubit unitary matrices commonly referred to as the Pauli matrices defined as:

$$I=\begin{pmatrix}1&0 \\ 0 &1\end{pmatrix}, X=\begin{pmatrix}0&1 \\ 1&0 \end{pmatrix}, Y=\begin{pmatrix}0&1 \\ -1&0 \end{pmatrix}, Z=\begin{pmatrix}1&0 \\ 0&-1 \end{pmatrix}.$$

It is worth noting that the operator $Y$ is commonly defined instead as the operator $\sigma_Y=iY$, but the definition of $Y$ introduced here will be convenient for our purposes. These operators satisfy the following properties:
\begin{align*}
X^2&=Z^2=-Y^2=I \\
XY&=-YX=Z, \\
YZ &=-ZY=X, \\
ZX &=-XZ=Y.
\end{align*}

These Properties give the set $P=\{\pm I,\pm X, \pm Y, \pm X\}$ a group structure under the usual matrix multiplication. Define $P_n:=\{U_1\otimes\dots\otimes U_n \ | \ U_j\in P, 0\leq j\leq n\}$, as the set of $n$-fold tensor products of Pauli operators from $P$. The set $P_n$ also forms a group structure under the natural multiplication and is called the Pauli group with order $|P_n|=2^{2n+1}$.

An important property about the Pauli operators is that they span the space of unitary operators acting on a single qubit. That is, any single qubit unitary $U$ can be expressed as
$U=c_II+c_XX+c_YY+c_ZZ,$
where the vector $(c_I,c_X,c_Y,c_Z)$ consists of complex numbers and is of unit norm. Similarly, any unitary operator acting on a $n$-qubit Hilbert space can be expressed in terms of elements of the Pauli group $P_n$.

Moreover, the Pauli Group $P_n$ also satisfies the following properties:

1.  Every $M\in P_n$ in unitary: $M^\dagger=M^{-1}$.
2.  Every $M\in P_n$ satisfies $M^2=\pm I^{\otimes n}$.
3.  If $M^2=I^{\otimes n}$, then $M=M^\dagger$; if $M^2=-I$, then $M=-M^\dagger$.
4.  For any $M, N \in P_n$, either $MN=NM$ (they commute) or $MN=-NM$ (they anti-commute).
Consider some abelian subgroup $S\subset P_n$, consisting of elements that all commute with one another. Then all elements of $S$ can be simultaneously diagonalized. The subspace $\Hil_S\subset\Hil^{2^n}$ defined as
$$\Hil_S:=\{\ket{\psi}\in\Hil^{2^n} \ | \ M\ket{\psi}=\ket{\psi} \text{for all} M\in S \}$$
consists of the simultaneous eigenspace with eigenvalue $+1$ of elements of $S$. The space $\Hil_S$ is called the \emph{stabilizer code} associated with $S$, and $S$ is called the stabilizer of the code.

A generating set of $S$ is a collection of elements of $S$ such that each element of $S$ can be expressed as some product of elements from the generating set. In addition, it is required that the elements of the generating set be independent, meaning that no element of the generating set can be expressed as a product of the other elements of the generating set. It can be shown \cite{Got} that if $S$ has $n-k$ generators, then the codes space $\Hil_S$ has dimension $2^k$ implying that it can effectively encode $k$ qubits.

Index the elements of a generating set of a stabilizer $S$ as $\{M_1,\dots,M_{n-k}\}$. The utility of the stabilizer formalism for quantum error correction comes from the fact that the elements of $S$ serve as operators for diagnosing possible errors that may occur to an encoded state of $\ket{\psi}\in\Hil_S$. In general, an error can be represented in terms elements $E_a\in P_n$. Then since every $E_a$ either commutes or anti-commutes with some generator $M_j\in S$, the following two cases may occur.
•  If $E_a$ anti-commutes with some $M_j$, then for $\ket{\psi}\in\Hil_S$,
$M_jE_a\ket{\psi}=-E_aM_j\ket{\psi}=-E_a\ket{\psi},$ which implies that the error can be detected if the the erred state $E_a\ket{\psi}$ is acted on by $M_j$.

• If $E_a$ commutes with some $M_j$, then for $\ket{\psi}\in\Hil_S$,
$M_jE_a\ket{\psi}=E_aM_j\ket{\psi}=E_a\ket{\psi},$ and the error may go undetected when the erred state $E_a\ket{\psi}$ is acted on by $M_j$.
A more thorough error syndrome can be provided by measuring each of the $n-k$  stabilizer generators. That is for a particular error $E_a$, consider the set of values $\{s_{a,j} \}$, where each $s_{a,j}\in\{0,1\}$ satisfies
$M_jE_a=(-1)^{s_{a,j}}E_aM_j.$
If it is the case that for every $a\neq b$, with $s_{a,j}\neq s_{b,j}$ for all $j$, then the code is considered to be non degenerate and there will be no ambiguity in what error occurred allowing for the error to be corrected by measuring the $n-k$ generators of $S$.

Another condition which must be satisfied by the stabilizer $S$ in order to ensure complete error recovery due to arbitrary errors is that, for each possible error $E_a, E_b$ and any $\ket{\psi}\in\Hil_S$,
$\bra{\psi}E_a^\dagger E_b\ket{\psi}=C_{ab},$
such that the constants $C_{ab}$ are independent of $\ket{\psi}$. This condition can be equivalently shown to hold if one of the following holds for each possible pair of errors $E_a$ and $E_b$:
1.  $E_a^\dagger E_b\in S$,
2.  There exists an $M\in S$ that anti-commutes with $E_a^\dagger E_b$.
In this way, error recovery may fail if both conditions are violated. That is, if there exists some $E_a^\dagger E_b$ that commutes with every element of $S$, but yet $E_a^\dagger E_b\not\in S$. In this circumstance, the operator $E_a^\dagger E_b$ that preserves the code space $\Hil_S$ but still modifies it in a non trivial way, implying that encoded information may still be transformed. In addition, both $E_a$ and $E_b$ will have the same syndrome leaving an inherent ambiguity on how either error should be corrected, and any mistake in diagnosis can apply a nontrivial transformation to the encoded space.