Stabilizer Codes

The Pauli group $G_n$ for a single qubit it is defined $G_1\equiv \{\pm I,\pm iI,\pm X,\pm iX,\pm Y,\pm iY,\pm Z,\pm iZ\}$and for $n$ qubits is all $n$-fold tensor products of Pauli matrices with multiplicative factors $\pm 1$ and $\pm i$ to ensure the elements are closed under multiplication.

Suppose $S$ is a subgroup of the Pauli group $G_n$, and define $V_S$ to be the set of $n$ qubit states which are fixed by every element of $S$ (eigenvalue 1). $V_S$ is the vector space stabilized by $S$, and $S$ is said to be the stabilizer of the space $V_S$.

A group is described by generators. A set of elements $g_1,\cdots ,g_l$ in a group $G$ is said to generate the group $G$ if every element of $G$ can be written as a product of elements from the list $g_1,\cdots ,g_l$, and we write $G=⟨g_1,\cdots ,g_l⟩$.

Unitary gates and the stabilizer formalism

Suppose we apply a unitary $U$ to a vector space $V_S$ stabilized by the group $S$, then for any element $g$ of $S$ $U|\psi ⟩=Ug|\psi ⟩=Ug{U}^{†}Y|\psi ⟩$ The state $U|\psi ⟩$ is stabilized by $Ug{U}^{†}$, and the vector space $U{V}_S$ is stabilized by the group $US{U}^{†}\equiv \{Ug{U}^{†}|g\in S\}$. If $g_1,\cdots ,g_l$ generates $S$, then $U{g}_1^{†},\cdots ,U{g}_l{U}^{†}$ generates $US{U}^{†}$. To see how unitary affects stabilizer, we only need to compute how it affects the generators of the stabilizer.

For special unitary operations $U$, this transformation of the generators takes simple form. Suppose we apply a Hadamard gate to a single qubit. Note $HX{H}^{†};HY{H}^{†}=-Y;HZ{H}^{†}=X$ As a consequence we deduce that after a Hadamard gate is applied to the state stabilized by $Z|0⟩$, the resulting state will be stabilized by $X|+⟩$.

Clifford Gate

Clifford gates are the elements of the Clifford group, a set of transformations which normalize the $n$-qubit Pauli group. Any unitary operations taking elements of $G_n$ to elements of $G_n$ can be composed from the Hadamard, phase, and C-NOT gates. By definition, the set of $U$ such that $U{G}_n{U}^{†}=G_n$ is the normalizer of $G_n$, and is denoted by $N(G_n)$.

Theorem: Suppose $U$ is any unitary operator on $n$ qubits with the property that if $g\in G_n$ , then $Ug{U}^{†}\in G_n$. Then up to a global phase, $U$ may be composed from $\mathcal{O}(n^2)$ Hadamard, phase, and C-NOT gates.

Each Pauli gate is trivially an element of the Clifford group.

Measurement in the stabilizer formalism

Imagine we make a measurement of $g\in G_n$. We assume without loss of generality that $g$ is a product of Pauli matrices with no multiplicative factor of $-1$ or $\pm i$ out front. The system is assumed to be in state $|\psi ⟩$ with stabilizer $⟨g_1,\cdots ,g_n⟩$. The stabilizer of the state transforms under measurement in two ways

• Measurement $g$ commutes with all generators of the stabilizer
• Measurement $g$ anti-commutes with one or more of the generators of the stabilizer. Suppose $g$ anti-commutes with $g_1$, without loss of generality we may assume $g$ commutes with $g_2,\cdots ,g_n$ since if it does not commute with one of these elements say $g_2$ then it will commute with $g_1{g}_2$, and we simply replace the generator $g_2$ by $g_1{g}_2$

In case 1, either $g$ or $-g$ is an element of the stabilizer since $g_{j}g|\psi ⟩=g{g}_j|\psi ⟩=g|\psi ⟩$ , $g|\psi ⟩\in V_s$ and is a multiple of $|\psi ⟩$. If $+g$ is in the stabilizer, then $g|\psi ⟩=|\psi ⟩$ and measurement of $g$ yields $+1$ with probability one, and the measurement does not disturb the state of the system and leaves the stabilizer invariant.

In case 2, when $g$ anti-commutes with $g_1$ and commutes with all other generators. $g$ has eigenvalues $\pm 1$ so the projectors for the measurement outcomes $\pm 1$ are given by $(I\pm g)/2$, respectively, and the measurement probabilities are given by

$$p(+1)=\text{Tr}\left(\frac{I+g}{2}|\psi ⟩⟨\psi |\right)$$ $$p(-1)=\text{Tr}\left(\frac{I-g}{2}|\psi ⟩⟨\psi |\right)$$

Since $g_1|\psi ⟩=|\psi ⟩$ and $g{g}_1=-g_{1}g$ then

$$p(+1)=\text{Tr}\left(\frac{I+g}{2}{g}_1\right)|\psi ⟩⟨\psi |=\text{Tr}\left(g_1\frac{I-g}{2}\right)|\psi ⟩⟨\psi |$$

Applying the cyclic property of the trace, we may take $g_1$ to the right hand end of the trace and absorb it into $⟨\psi |$ using $g_1=g_1^{†}$, giving $p(+1)=\text{Tr}\left(\frac{I-g}{2}|\psi ⟩⟨\psi \right)=p(-1)$ Thus $p(+1)=p(-1)=1/2$. Suppose the result $+1$ occurs, then the system is in state $|{\psi }^{+}⟩\equiv (I+g)|\psi ⟩/\sqrt{2}$ which has stabilizer $⟨g,g_2,\cdots ,g_n⟩$. Similarly, if the result $-1$ occurs the posterior state is stabilized by $⟨-g,g_2,\cdots ,g_n⟩$.

The Gottesman-Knill theorem

Theorem: Suppose a quantum computation is performed which involves only the following elements: state preparations in the computational basis, Hadamard gates, phase gates, C-NOT gates, Pauli gates, and measurements of observables in the Pauli group, together with the possibility of classical control conditioned on the outcome of such measurements. Such a computation may be efficiently simulated on a classical computer.

The way a classical computer performs the simulation is simply to keep track of the generators of the stabilizer as the various operations are being performed in the computation. For example, to simulate a Hadamard gate we simply update each of the $n$ generators describing the quantum state. Similarly, simulation of the state preparation, phase gate, C-NOT gate, Pauli gates, and measurements of observables in the Pauli group may all be done using $\mathcal{O}(n^2)$ steps on a classical computer, so that a quantum computation involving $m$ operations from this set can be simulated using $\mathcal{O}(n^{2}m)$ operations on a classical computer. Some quantum computations involving highly entangles states may be simulated efficiently on classical computers.

Fault-tolerant Measurement