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.

An impossible operation: the transpose

Question: Is the transpose a valid quantum operation?

 To make things a little more rigorous, let an operation $\Lambda$ on qubits be defined as $\Lambda(\rho)=\rho^T$, where $\rho^T$ denotes the transpose of $\rho$.

Consider the one qubit  state $\ket{\psi_+}=\frac{1}{\sqrt{2}}(\ket{0}+i\ket{1})$ so that
\[ \begin{align*}
 \ket{\psi_+}\bra{\psi_+}&=\frac{1}{2}(\ket{0}+i\ket{1})(\bra{0}-i\bra{1}) \\
 &=\frac{1}{2}(\ket{0}\bra{0}-i\ket{0}\bra{1}+i\ket{1}\bra{0}+\ket{1}\bra{1}) \\
 &=\frac{1}{2}\begin{pmatrix} 1&-i \\ i&1\end{pmatrix}.
 \end{align*}\]
 Then
\[ \begin{align*}
 \Lambda(\ket{\psi_+}\bra{\psi_+})=\frac{1}{2}\begin{pmatrix} 1&-i \\ i&1\end{pmatrix}^T
&=\frac{1}{2}\begin{pmatrix} 1&i \\ -i&1\end{pmatrix} \\
&=\frac{1}{2}(\ket{0}\bra{0}+i\ket{0}\bra{1}-i\ket{1}\bra{0}+\ket{1}\bra{1}) \\
&=\frac{1}{2}(\ket{0}-i\ket{1})(\bra{0}+i\bra{1}) \\
&=\ket{\psi_-}\bra{\psi_-},
  \end{align*}\]
  where $\ket{\psi_-}=\frac{1}{\sqrt{2}}(\ket{0}-i\ket{1})$. Then the inner product of $\ket{\psi_-}$ and $\ket{\psi_+}$ is
\[  \begin{align*}
  \ip{\psi_-}{\psi_+}&=\frac{1}{2}(\bra{0}+i\bra{1})(\ket{0}+i\ket{1}) \\
  &=\frac{1}{2}(\ip{0}{0}+i\ip{0}{1}+i\ip{1}{0}-\ip{1}{1}) \\
  &=\frac{1}{2}(1+0+0-1) \\
  &=0.
  \end{align*}\]
  Thus, $\ket{\psi_+}$ and $\ket{\psi_-}$ are orthogonal pure states such that $\Lambda(\ket{\psi_+}\bra{\psi_+})=\ket{\psi_-}\bra{\psi_-}$.
 
 Now, it will be proven that there does not exist a unitary operation $U$ such that $\Lambda(\rho)=U\rho U^\dagger$ for all $\rho$.
 
  It suffices to show that such a unitary does not exist in the single qubit (two dimensional) case. For the sake of contradiction suppose that such a unitary $U$ does exist. Moreover, consider the two states $\ket{0}$ and $\ket{\psi_+}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$, whose density operators are given by
\[
  \ket{0}\bra{0}=\begin{pmatrix} 1&0 \\0&0 \end{pmatrix} \ \ \  \text{and} \ \ \ \ket{\psi_+}\bra{\psi_+}=\frac{1}{2}\begin{pmatrix} 1&1\\1&1 \end{pmatrix}.
\]
  Then
 \[ \begin{align*}
 \Lambda(\ket{0}\bra{0})&=\begin{pmatrix} 1&0 \\0&0 \end{pmatrix}^T=\begin{pmatrix} 1&0 \\0&0 \end{pmatrix}=\ket{0}\bra{0} \\
    \Lambda(\ket{\psi_+}\bra{\psi_+})&=\frac{1}{2}\begin{pmatrix} 1&1\\1&1 \end{pmatrix}^T=\frac{1}{2}\begin{pmatrix} 1&1\\1&1 \end{pmatrix}=\ket{\psi_+}\bra{\psi_+},
  \end{align*}\]
  which shows that these two states remain the same under the transposition operation $\Lambda$. Therefore, these two states must also be left unchanged by the action of the unitary $U$. That is, it must be the case that
  \[\begin{align*}
  U\ket{0}\bra{0}U^\dagger&=\ket{0}\bra{0},\\
  U\ket{\psi_+}\bra{\psi_+}U^\dagger&=\ket{\psi_+}\bra{\psi_+},
  \end{align*}\]
  or equivalently that $U\ket{0}=\ket{0}$ and $U\ket{\psi_+}=\ket{\psi_+}$. By thinking of these states and the action of $U$ as a rotation on the Block sphere, this implies that both of these states remain fixed and must therefore lie on the axis of rotation of $U$. More explicitly, recall that a one-qubit unitary can be represented as
\[
  U=e^{i\alpha}\cos(\theta/2)I-ie^{i\alpha}\sin(\theta/2)\left(c_x X +c_Y Y + c_Z Z\right),
\]
  where $\alpha$ is just a phase factor, $\theta$ gives the angle of rotation, and $(c_X,c_Y,c_Z)$ is a unit vector.
 
    Then since the state $\ket{0}$ lies on the $z$-axis of the Bloch sphere, the rotation of $U$ must have its axis of rotation as the $z-$ axis in order to keep $\ket{0}$ fixed, which implies that $c_X,c_Y=0$. Furthermore, since the state $\ket{\psi_+}$ lies along the $y$-axis, this also implies that $U$ must rotate about the $y$-axis in order to ket $\ket{\psi_+}$ fixed, but this implies that $c_X,C_Z=)$. These implications together imply that $c_X,c_Y,c_Z=0$,so that $U=I$. However, as seen above the transpose operation $U$ does not act as the identity operation all states. This is a contradiction, and therefore there cannot exist a unitary $U$ satisfying the desired conditions.

  Another, perhaps more general, way to see why such a unitary cannot exist is too note that any operation of the form $\Phi(\rho)=U\rho U^\dagger$ defined with some unitary $U$ always yields a valid quantum operation. This means that $\Phi(\rho)$ is both trace preserving and a completely positive map by definition. On the other hand,  although the transpose operation $\Lambda$ is trace preserving it is not completely positive in general, and thus cannot define a valid quantum operation by definition.

An impossible operation: mapping every state to an orthogonal state

Here, we'll question the existence of a quantum operation that maps every quantum state to an orthogonal state relative to its input. More specifically: is there a one-qubit unitary operation $U$ that maps each pure state $\ket{\psi}$ to some state $U\ket{\psi}=\ket{\psi'}$ such that $\ip{\psi}{\psi'}=0$.

I claim that there does not exist such a unitary!

Suppose, for the sake of contradiction, that such a unitary $U$ did exist. Consider an arbitrary one-qubit state $\ket{\psi}$. Let $U\ket{\psi}=\ket{\psi'}$ so that $\ip{\psi}{\psi'}=0$. Moreover, let $U\ket{\psi'}=\ket{\psi''}$ so that $\ip{\psi''}{\psi'}=0$ as well by the assumption of the existence of such a unitary. Now, consider the state $\ket{\phi}=\frac{1}{\sqrt{2}}(\ket{\psi}+\ket{\psi'})$, and let $U\ket{\phi}=\ket{\phi'}$ so that $\ip{\phi}{\phi'}=0$. Then it must also follow that
\[
U\ket{\phi}=\frac{1}{\sqrt{2}}(U\ket{\psi}+U\ket{\psi'})=\frac{1}{\sqrt{2}}(\ket{\psi'}+\ket{\psi''})=\ket{\phi'}.
\]
This implies that the inner product of $\ket{\phi}$ and $\ket{\phi}$ must also satisfy
\[\begin{align*}
\ip{\phi}{\phi'}&=\frac{1}{2}(\bra{\psi'}+\bra{\psi''})(\ket{\psi'}+\ket{\psi''}) \\
&=\frac{1}{2}(\ip{\psi'}{\psi'}+\ip{\psi'}{\psi''}+\ip{\psi''}{\psi'}+\ip{\psi''}{\psi''}) \\
&=\frac{1}{2}(1+0+0+1) \\
&=1,
\end{align*}\]
but then $1=\ip{\phi}{\phi'}=0$ which a contradiction. Therefore, no such unitary can exist.

A particular instance of Grover's search

Here, we will analyze how Grover's search algorithm can be used in the particular cases when the density of marked items is $1/4$ and $1/2$.

Consider a function $f:\{0,1\}^n \to \{0,1\}$, define the sets
\[\begin{align*}
A&=\{x\in\{0,1\}^n : f(x)=1\} \\
B&=\{x\in\{0,1\}^n : f(x)=0\},
\end{align*} \]
and let $a=|A|$ and $b=|B|$.

The equally weighted superposition of all basis states in a $2^n=N$ dimensional Hilbert space can be expressed as
\[
\ket{\psi_0}=\frac{1}{\sqrt{N}}\SUM{x\in\{0,1\}^n}{}\ket{x}=\sqrt{\frac{a}{N}}\SUM{f(x)=1}{}\ket{x}+\sqrt{\frac{b}{N}}\SUM{f(x)=0}{}\ket{x}.
\]
Assuming that $a=|A|$ is known, choose $\theta$ such that $\sin(\theta)=\sqrt{\frac{a}{N}}$. Then the superposition $\ket{\psi_0}$ can be equivalently written as
\[
\ket{\psi_0}=\sin(\theta)\SUM{f(x)=1}{}\ket{x}+\cos(\theta)\SUM{f(x)=0}{}\ket{x}.
\]
In Grover's search algorithm, $\ket{\psi_0}$ is prepared as an initial state, and then a sequence of \emph{Grover} iterations are applied, which after $k$ iterations, results in the state
\[
\ket{\psi_k}=\sin((2k+1)\theta)\SUM{f(x)=1}{}\ket{x}+\cos((2k+1)\theta)\SUM{f(x)=0}{}\ket{x}.
\]
The objective is to choose the number of iterations $k$ so that $\sin((2k+1)\theta)\approx 1$ so that some state $\ket{x}$ such that $x\in{A}$ is measured with high probability. For this to be the case, it suffices that the following conditions hold:
\[\begin{align*}
\sin((2k+1)\theta)&\approx 1 \\
(2k+1)\theta&\approx \frac{\pi}{2} \\
k&\approx \frac{\pi}{4\theta}-\frac{1}{2} \\
\end{align*}\]

Consider the case when $a=\frac{1}{4}2^n=\frac{1}{4}N$ so that the initial angle $\theta$ is chosen to satisfy $\sin(\theta)=\sqrt{\frac{a}{N}}=\sqrt{\frac{N}{4N}}=\frac{1}{2}$ implying that $\theta=\frac{\pi}{6}$. In this case, the number of desired iterations that need to be performed is actually given by
\[
k= \frac{\pi}{4\theta}-\frac{1}{2}=\frac{\pi 6}{4\pi}-\frac{1}{2}=1,
\]
and thus Grover's algorithm is guaranteed to find an $x$ such that $x\in A$ in just a single iteration.

Now consider the case where $a=\frac{1}{2}2^n=\frac{1}{2}N$ so that the initial angle $\theta$ is chosen to satisfy $\sin(\theta)=\sqrt{\frac{a}{N}}=\sqrt{\frac{N}{2N}}=\frac{1}{\sqrt{2}}$ implying that $\theta=\frac{\pi}{4}$. In this case, the number of desired iterations that need to be performed is approximately
\[
k\approx \frac{\pi}{4\theta}-\frac{1}{2}=\frac{\pi 4}{4\pi}-\frac{1}{2}=\frac{1/2}.
\]
However, since $k$ is not an integer and is equally close to the integers $0$ and $1$ it is seen that a state $\ket{x}$ such that $x\in A$ is not guaranteed to be found with certainty if the state $\ket{\psi_k}$ were to be measured. In this instance, Grover's search algorithm provides no benefit, in the sense that the likelihood of observing a state $\ket{x}$ such that $x\in A$ is equally probably if $1$ iteration is performed or if $0$ iterations are performed to the initial state.

Correcting errors at known positions

Here we consider error correcting codes in scenarios where, after the qubits have been transmitted, the location of the possible error is known but not the error itself.  In what follows, it will be assumed without loss of generality  that the single-qubit error occurs on the $4^{th}$ qubit of the encoded state. It will be straightforward to generalize how errors are to be corrected that inflict the other qubits instead.

Consider a $4$-qubit quantum error correcting code, Code A, which encodes the single-qubit computational basis as
\[\begin{align*}
\ket{0}\mapsto\ket{c_0}&:=\frac{1}{\sqrt{2}}(\ket{0000}+\ket{1111})\\
\ket{1}\mapsto\ket{c_1}&:=\frac{1}{\sqrt{2}}(\ket{0011}+\ket{1100}).
\end{align*}\]
 Then an arbitrary qubit $\ket{\psi}=\alpha\ket{0}+\beta\ket{1}$ is encoded as the state
\[
\ket{\psi_A}:=\alpha\ket{c_0}+\beta\ket{c_1}=\frac{\alpha}{\sqrt{2}}(\ket{0000}+\ket{1111})+\frac{\beta}{\sqrt{2}}(\ket{0011}+\ket{1100}).
\]
The circuit shown tin the figure below describes how a possible $X$ error is corrected.


 Here, the $Error$ gate can be though of as the gate $X^a$, for $a\in\{0,1\}$, where the case $a=0$ means no error has occurred and the case $a=1$ implies an $X$ error has occurred on the $4^{th}$ qubit.

  Notice the presence of a single qubit ancilla present in the circuit which is initialized in the state $\ket{0}$. The ancilla effectively measures the parity of the $4$ qubits in the state $\ket{\psi_A}$ after a potential error has occurred on it via the sequence of $4$ controlled-$X$ operations using the ancilla as a target. In this case, the action of the parity operation on the $5$ qubit system carried out by the first $4$ controlled-$X$ gates in the circuit can be more explicitly described as
\[
 \ket{abcd}\ket{0}\overset{parity \ check}\mapsto \ket{abcd}\ket{a\oplus b\oplus c\oplus d},
\]
 where $a,b,c,d\in\{0,1\}$ and $\oplus$ denotes addition modulo $2$.

 The final controlled-$X$ that appears in the circuit, which uses the ancilla as the control register, serves to correct the state of the potentially errored $4^{th}$ qubit of the encoded state $\ket{\psi_A}$. This gate will be denoted by $c_5-X_4$ (specifying that the $4^{th}$ qubit is the target and the $5^{th}$ qubit is the control).

  To see that this error correcting scheme does indeed correct a possible $X^j$ error, observe the following:
\[ \begin{align*}
 \ket{\psi_A}\ket{0} \overset{Error}\mapsto \ \  \ &\frac{\alpha}{\sqrt{2}}(\ket{000}X^j\ket{0}+\ket{111}X^j\ket{1})\ket{0}+\frac{\beta}{\sqrt{2}}(\ket{001}X^j\ket{1}+\ket{110}X^j\ket{0})\ket{0} \\
 \overset{parity \ check}\mapsto &\frac{\alpha}{\sqrt{2}}(\ket{000}X^j\ket{0}+\ket{111}X^j\ket{1})\ket{j}+\frac{\beta}{\sqrt{2}}(\ket{001}X^j\ket{1}+\ket{110}X^j\ket{0})\ket{j} \\
  \overset{c_5-X_4}\mapsto &\frac{\alpha}{\sqrt{2}}(\ket{000}X^jX^j\ket{0}+\ket{111}X^jX^j\ket{1})\ket{j}+\frac{\beta}{\sqrt{2}}(\ket{001}X^jX^j\ket{1}+\ket{110}X^jX^j\ket{0})\ket{j} \\
  =&\frac{\alpha}{\sqrt{2}}(\ket{0000}+\ket{1111})\ket{j}+\frac{\beta}{\sqrt{2}}(\ket{0011}+\ket{1100})\ket{j} \\
  =&\ket{\psi_A}\ket{j}.
 \end{align*}\]
Hence, the erred state is returned to the encoded state $\ket{\psi_A}$ showing that the circuit does successfully correct $X$ errors.

The procedure is similar if the error happened to occur on some other qubit of the encoded state, say the $k^{th}$. The rest of the circuit remains the same except the last controlled-$X$ would be replaced by $c_5-X_k$, where the gate has the $k^{th}$ qubit of the register as its target instead.

Now consider the following code variant, Code B, whose basis codewords are given by
\[\begin{align*}
\ket{0}\mapsto&\ket{c'_0}=H^{\otimes 4}\ket{c_0}  \\
\ket{1}\mapsto&\ket{c'_1}=H^{\otimes 4}\ket{c_1},
\end{align*}\]
so that an arbitrary qubit $\ket{\psi}=\alpha\ket{0}+\beta\ket{1}$ is encoded as
\[
\ket{\psi_B}:=\alpha\ket{c'_0}+\beta\ket{c'_1}.
\]

For a bit string $x=x_1x_2\dots x_n\in\{0,1\}^n$, let $p(x)=x_1\oplus x_2\oplus \dots\oplus x_n$ (where $\oplus$ is addition modulo $2$) denote the parity of $x$, and say that $x$ is \emph{even} is $p(x)=0$ and that $x$ is \emph{odd} if $p(x)=1$. Also for $s=s_1s_2s_3s_4\in\{0,1\}^4$ let $a,b\in\{0,1\}^2$ be such that $a=s_1s_2$ and $b=s_3s_4$ so that a quantum state can be represented as $\ket{s}=\ket{a}\ket{b}$.

 The states $\ket{c'_0}$ and $\ket{c'_1}$ can be expressed more explicitly as follows.
\[\begin{align*}
\ket{c'_0}=H^{\otimes 4}\ket{c_0}&=\frac{1}{\sqrt{2}}(H^{\otimes 4}\ket{0000}+H^{\otimes 4}\ket{1111}) \\
&=\frac{1}{\sqrt{2}^5}\left(\SUM{s\in\{0,1\}^4}{}(-1)^{s\cdot0000}\ket{s}\right)+\frac{1}{\sqrt{2}^5}\left(\SUM{s\in\{0,1\}^4}{}(-1)^{s\cdot1111}\ket{s}\right) \\
&=\frac{1}{\sqrt{2}^5}\left(\SUM{p(s)=0}{}\ket{s}+\SUM{p(s)=1}{}\ket{s}\right)+\frac{1}{\sqrt{2}^5}\left(\SUM{p(s)=0}{}\ket{s}-\SUM{p(s)=1}{}\ket{s}\right) \\
&=\frac{1}{\sqrt{2}^5}\left(\SUM{p(s)=0}{}2\ket{s}\right) \\
&=\frac{1}{\sqrt{8}}\left(\SUM{p(s)=0}{}\ket{s}\right) \\
&=\frac{1}{\sqrt{8}}\left(\SUM{\substack{p(a)=0 \\ p(b)=0}}{}\ket{a}\ket{b}+\SUM{\substack{p(a)=1 \\ p(b)=1}}{}\ket{a}\ket{b}\right).
\end{align*}\]

Likewise, the state $\ket{c'_0}$ can be expressed as
\[\begin{align*}
\ket{c'_1}=H^{\otimes 4}\ket{c_1}&=\frac{1}{\sqrt{2}}(H^{\otimes 4}\ket{0011}+H^{\otimes 4}\ket{1100}) \\
&=\frac{1}{\sqrt{2}^5}\left(\SUM{s\in\{0,1\}^4}{}(-1)^{s\cdot0011}\ket{s}\right)+\frac{1}{\sqrt{2}^5}\left(\SUM{s\in\{0,1\}^4}{}(-1)^{s\cdot1100}\ket{s}\right) \\
&=\frac{1}{\sqrt{2}^5}\left(\SUM{a,b\in\{0,1\}^2}{}(-1)^{ab\cdot0011}\ket{a}\ket{b}\right)+\frac{1}{\sqrt{2}^5}\left(\SUM{a,b\in\{0,1\}^2}{}(-1)^{ab\cdot1100}\ket{a}\ket{b}\right) \\
&=\frac{1}{\sqrt{2}^5}\left(\SUM{p(a)=0}{}\ket{a}+\SUM{p(a)=1}{}\ket{a}\right)\left(\SUM{p(b)=0}{}\ket{b}-\SUM{p(b)=1}{}\ket{b}\right) \\
 & \ \ \ +\frac{1}{\sqrt{2}^5}\left(\SUM{p(a)=0}{}\ket{a}-\SUM{p(a)=1}{}\ket{a}\right)\left(\SUM{p(b)=0}{}\ket{b}+\SUM{p(b)=1}{}\ket{b}\right) \\
&=\frac{1}{\sqrt{8}}\left(\SUM{\substack{p(a)=0 \\ p(b)=0}}{}\ket{a}\ket{b}-\SUM{\substack{p(a)=1 \\ p(b)=1}}{}\ket{a}\ket{b}\right).
\end{align*}\]

Then by combining the two previous results the encoded state of $\ket{\psi}=\alpha\ket{0}+\beta\ket{1}$ can be expressed as
\[\begin{align*}
\ket{\psi_B}&=\alpha\ket{c'_0}+\beta\ket{c'_1} \\
&=\frac{\alpha}{\sqrt{8}}\left(\SUM{\substack{p(a)=0 \\ p(b)=0}}{}\ket{a}\ket{b}+\SUM{\substack{p(a)=1 \\ p(b)=1}}{}\ket{a}\ket{b}\right)+\frac{\beta}{\sqrt{8}}\left(\SUM{\substack{p(a)=0 \\ p(b)=0}}{}\ket{a}\ket{b}-\SUM{\substack{p(a)=1 \\ p(b)=1}}{}\ket{a}\ket{b}\right) \\
&=\frac{\alpha+\beta}{\sqrt{8}}\left(\SUM{\substack{p(a)=0 \\ p(b)=0}}{}\ket{a}\ket{b}\right) +\frac{\alpha-\beta}{\sqrt{8}}\left(\SUM{\substack{p(a)=1 \\ p(b)=1}}{}\ket{a}\ket{b}\right)\\
&=\frac{\alpha+\beta}{\sqrt{8}}\left((\ket{00}+\ket{11})(\ket{00}+\ket{11}) \right)+\frac{\alpha-\beta}{\sqrt{8}}\left((\ket{01}+\ket{10})(\ket{01}+\ket{10}) \right).
\end{align*}\]

With this in mind, it can similarly be seen that the same procedure used to correct $X$ errors for Code A can also be used to correct $X$ errors for Code B. The circuit is shown again for convenience, where the only thing that has changed in the encoded state:


To see that this procedure does indeed work consider the following
 \[\begin{align*}
 &\ket{\psi_B}\ket{0} \\
 &\overset{Error}\mapsto \\ 
 &\frac{\alpha+\beta}{\sqrt{8}}\left((\ket{00}+\ket{11})(\ket{0}X^j\ket{0}+\ket{1}X^j\ket{1}) \right)\ket{0}+\frac{\alpha-\beta}{\sqrt{8}}\left((\ket{01}+\ket{10})(\ket{0}X^j\ket{1}+\ket{1}X^j\ket{0}) \right)\ket{0} \\
 &\overset{parity \ check}\mapsto \\
 &\frac{\alpha+\beta}{\sqrt{8}}\left((\ket{00}+\ket{11})(\ket{0}X^j\ket{0}+\ket{1}X^j\ket{1}) \right)\ket{j}+\frac{\alpha-\beta}{\sqrt{8}}\left((\ket{01}+\ket{10})(\ket{0}X^j\ket{1}+\ket{1}X^j\ket{0})\ket{0} \right)\ket{j} \\
 & \overset{c_5-X_4}\mapsto \\
 &\frac{\alpha+\beta}{\sqrt{8}}\left((\ket{00}+\ket{11})(\ket{0}X^jX^j\ket{0}+\ket{1}X^jX^j\ket{1}) \right)\ket{j}+\frac{\alpha-\beta}{\sqrt{8}}\left((\ket{01}+\ket{10})(\ket{0}X^jX^j\ket{1}+\ket{1}X^jX^j\ket{0})\ket{0} \right)\ket{j} \\
&=\frac{\alpha+\beta}{\sqrt{8}}\left((\ket{00}+\ket{11})(\ket{00}+\ket{11}) \right)\ket{j}+\frac{\alpha-\beta}{\sqrt{8}}\left((\ket{01}+\ket{10})(\ket{01}+\ket{10}) \right)\ket{j} \\
  &=\ket{\psi_B}\ket{j}.
 \end{align*}\]
Hence, the errored state is returned to the encoded state $\ket{\psi_B}$ showing that the circuit does successfully correct $X$ errors for Code B. If the error is known to occur at one of the other locations of the encoded state, this procedure can be generalized to correct the error in that case as described in previously.


It will know be shown how Code A can protect against $I, X, Z$ and $XZ$ errors at known location. Here it will be implicit that the error is occurring on the $4^{th}$ qubit of the encoded state. First, consider the result of possible errors on the encoded state $\ket{\psi_A}=\frac{\alpha}{\sqrt{2}}(\ket{0000}+\ket{1111})+\frac{\beta}{\sqrt{2}}(\ket{0011}+\ket{1100})$.
\[\begin{align*}
\ket{\psi_A} \overset{I}\mapsto& \frac{\alpha}{\sqrt{2}}(\ket{0000}+\ket{1111})+\frac{\beta}{\sqrt{2}}(\ket{0011}+\ket{1100}) \\
\ket{\psi_A} \overset{X}\mapsto& \frac{\alpha}{\sqrt{2}}(\ket{0001}+\ket{1110})+\frac{\beta}{\sqrt{2}}(\ket{0010}+\ket{1101}) \\
\ket{\psi_A} \overset{Z}\mapsto& \frac{\alpha}{\sqrt{2}}(\ket{0000}-\ket{1111})+\frac{\beta}{\sqrt{2}}(\ket{1100}-\ket{0011}) \\
\ket{\psi_A} \overset{XZ}\mapsto& \frac{\alpha}{\sqrt{2}}(\ket{1110}-\ket{0001})+\frac{\beta}{\sqrt{2}}(\ket{0010}-\ket{1101}).
\end{align*}\]
For reasons that will soon become clear consider the state that results from applying $H^{\otimes 4}$ to the encoded state that has only a $Z$ error:
\[\begin{align*}
Z\ket{\psi_A} &= \frac{\alpha}{\sqrt{2}}(\ket{0000}-\ket{1111})+\frac{\beta}{\sqrt{2}}(\ket{1100}-\ket{0011}).\\
\end{align*}\]
 Examining the two parts of the state seperately yields
\[ \begin{align*}
 \frac{\alpha}{\sqrt{2}}(\ket{0000}-\ket{1111})\overset{H^{\otimes 4}}\mapsto& \frac{\alpha}{\sqrt{2}}(H^{\otimes 4}\ket{0000}-H^{\otimes 4}\ket{1111}) \\
 &=\frac{\alpha}{\sqrt{2}^5}\left(\SUM{s\in\{0,1\}^4}{}(-1)^{s\cdot0000}\ket{s}\right)-\frac{\alpha}{\sqrt{2}^5}\left(\SUM{s\in\{0,1\}^4}{}(-1)^{s\cdot1111}\ket{s}\right) \\
&=\frac{\alpha}{\sqrt{2}^5}\left(\SUM{p(s)=0}{}\ket{s}+\SUM{p(s)=1}{}\ket{s}\right)-\frac{\alpha}{\sqrt{2}^5}\left(\SUM{p(s)=0}{}\ket{s}-\SUM{p(s)=1}{}\ket{s}\right) \\
&=\frac{\alpha}{\sqrt{2}^5}\left(\SUM{p(s)=1}{}2\ket{s}\right) \\
&=\frac{\alpha}{\sqrt{8}}\left(\SUM{p(s)=1}{}\ket{s}\right) \\
&=\frac{\alpha}{\sqrt{8}}\left(\SUM{\substack{p(a)=0 \\ p(b)=1}}{}\ket{a}\ket{b}+\SUM{\substack{p(a)=1 \\ p(b)=0}}{}\ket{a}\ket{b}\right)
  \end{align*}\]
and
\[\begin{align*}
\frac{\beta}{\sqrt{2}}(\ket{1100}-\ket{0011})\overset{H^{\otimes 4}}\mapsto& \frac{\beta}{\sqrt{2}}(H^{\otimes 4}\ket{1100}-H^{\otimes 4}\ket{0011}) \\
&=\frac{\beta}{\sqrt{2}^5}\left(\SUM{s\in\{0,1\}^4}{}(-1)^{s\cdot1100}\ket{s}\right)-\frac{\beta}{\sqrt{2}^5}\left(\SUM{s\in\{0,1\}^4}{}(-1)^{s\cdot0011}\ket{s}\right) \\
&=\frac{\beta}{\sqrt{2}^5}\left(\SUM{a,b\in\{0,1\}^2}{}(-1)^{ab\cdot1100}\ket{a}\ket{b}\right)-\frac{\beta}{\sqrt{2}^5}\left(\SUM{a,b\in\{0,1\}^2}{}(-1)^{ab\cdot0011}\ket{a}\ket{b}\right) \\
&=\frac{\beta}{\sqrt{2}^5}\left(\SUM{p(a)=0}{}\ket{a}-\SUM{p(a)=1}{}\ket{a}\right)\left(\SUM{p(b)=0}{}\ket{b}+\SUM{p(b)=1}{}\ket{b}\right) \\
 & \ \ \ -\frac{\beta}{\sqrt{2}^5}\left(\SUM{p(a)=0}{}\ket{a}+\SUM{p(a)=1}{}\ket{a}\right)\left(\SUM{p(b)=0}{}\ket{b}-\SUM{p(b)=1}{}\ket{b}\right) \\
&=\frac{\beta}{\sqrt{8}}\left(\SUM{\substack{p(a)=0 \\ p(b)=1}}{}\ket{a}\ket{b}-\SUM{\substack{p(a)=1 \\ p(b)=0}}{}\ket{a}\ket{b}\right),
\end{align*}\]
which combined give
\[\begin{align*}
Z\ket{\psi_A} &= \frac{\alpha}{\sqrt{2}}(\ket{0000}-\ket{1111})+\frac{\beta}{\sqrt{2}}(\ket{1100}-\ket{0011})\\
&=\frac{\alpha}{\sqrt{8}}\left(\SUM{\substack{p(a)=0 \\ p(b)=1}}{}\ket{a}\ket{b}+\SUM{\substack{p(a)=1 \\ p(b)=0}}{}\ket{a}\ket{b}\right)+\frac{\beta}{\sqrt{8}}\left(\SUM{\substack{p(a)=0 \\ p(b)=1}}{}\ket{a}\ket{b}-\SUM{\substack{p(a)=1 \\ p(b)=0}}{}\ket{a}\ket{b}\right) \\
&=\frac{\alpha+\beta}{\sqrt{8}}\left(\SUM{\substack{p(a)=0 \\ p(b)=1}}{}\ket{a}\ket{b}\right)+\frac{\alpha-\beta}{\sqrt{8}}\left(\SUM{\substack{p(a)=1 \\ p(b)=0}}{}\ket{a}\ket{b}\right) \\
&=\frac{\alpha+\beta}{\sqrt{8}}\left((\ket{00}+\ket{11})(\ket{01}+\ket{10})+\frac{\alpha-\beta}{\sqrt{8}}\left((\ket{01}+\ket{10})(\ket{00}+\ket{11}) \right) \right)
\end{align*}\]

With this mind consider the following circuit which corrects both $X, Z$, and $XZ$ errors on the $4^{th}$ qubit.


Note that, here,  two qubits are being used as an ancilla where each is initialized to the state $\ket{0}$. This circuit will first correct any possible $X$ errors before the sequence of Hadamard gates, and then correct any $Z$ errors. In this case, a general error will be represented by $Error=X^jZ^k$, where $j,k\in\{0,1\}$. The action of this circuit will now be described:
 \[\begin{align*}
 &\ket{\psi_A}\ket{0}\ket{0} \\
 & \overset{Error}\mapsto \\ 
 &\frac{\alpha}{\sqrt{2}}(\ket{000}X^jZ^k\ket{0}+\ket{111}X^jZ^k\ket{1})\ket{0}\ket{0}+\frac{\beta}{\sqrt{2}}(\ket{001}X^jZ^k\ket{1}+\ket{110}X^jZ^k\ket{0})\ket{0}\ket{0} \\
& \overset{parity \ check}\mapsto \\
&\frac{\alpha}{\sqrt{2}}(\ket{000}X^jZ^k\ket{0}+\ket{111}X^jZ^k\ket{1})\ket{j}\ket{0}+\frac{\beta}{\sqrt{2}}(\ket{001}X^jZ^k\ket{1}+\ket{110}X^jZ^k\ket{0})\ket{j}\ket{0} \\
 &\overset{c_5-X_4}\mapsto \\
&\frac{\alpha}{\sqrt{2}}(\ket{000}X^jX^jZ^k\ket{0}+\ket{111}X^jX^jZ^k\ket{1})\ket{j}\ket{0}+\frac{\beta}{\sqrt{2}}(\ket{001}X^jX^jZ^k\ket{1}+\ket{110}X^jX^jZ^k\ket{0})\ket{j}\ket{0} \\
 &=\frac{\alpha}{\sqrt{2}}(\ket{000}Z^k\ket{0}+\ket{111}Z^k\ket{1})\ket{j}\ket{0}+\frac{\beta}{\sqrt{2}}(\ket{001}Z^k\ket{1}+\ket{110}Z^k\ket{0})\ket{j}\ket{0} \\ 
 &=Z^k\ket{\psi_A}\ket{j}\ket{0}.
 \end{align*}\]

At this point, all the remains is correcting a possible $Z$ error on the $4^{th}$ qubit. For simplicity, consider the two cases separately for $k=0$ where there is no $Z$ error, and the case $k=1$ where there is a $Z$ error. In the former case, with $k=0$, it can be seen that the effect of the rest of the circuit leaves the state unchanged since the the state of the encoded qubits before the Hadamard gates is just $\ket{\psi_A}$, and it was shown in part (b) that the state $H^{\otimes 4}\ket{\psi_A}=\ket{\psi_B}$ after the Hadamard gates are applied is left unchanged when acted on by the circuit for Code B. Therefore, the effect of the final sequence of Hadamard gates will bring the encoded qubits back to the state $\ket{\psi_A}$.

Suppose instead that a $Z$ error is present (the $k=1$ case). Then it can be seen that the state after the $X$ error has been corrected transforms as
\[\begin{align*}
&Z\ket{\psi_A}\ket{j}\ket{0} = \left(\frac{\alpha}{\sqrt{2}}(\ket{0000}-\ket{1111})+\frac{\beta}{\sqrt{2}}(\ket{1100}-\ket{0011})\right)\ket{j}\ket{0} \\
&\overset{H^\otimes 4}\mapsto \\
&\left(\frac{\alpha+\beta}{\sqrt{8}}(\ket{00}+\ket{11})(\ket{01}+\ket{10})+\frac{\alpha-\beta}{\sqrt{8}}\left((\ket{01}+\ket{10})(\ket{00}+\ket{11}) \right)\right)\ket{j}\ket{0} \\
&\overset{parity \ check}\mapsto \\
&\left(\frac{\alpha+\beta}{\sqrt{8}}(\ket{00}+\ket{11})(\ket{01}+\ket{10})+\frac{\alpha-\beta}{\sqrt{8}}\left((\ket{01}+\ket{10})(\ket{00}+\ket{11}) \right)\right)\ket{j}\ket{1} \\
&\overset{c_6-X_4}\mapsto \\
&\left(\frac{\alpha+\beta}{\sqrt{8}}(\ket{00}+\ket{11})(\ket{0}X\ket{1}+\ket{1}X\ket{0})+\frac{\alpha-\beta}{\sqrt{8}}\left((\ket{01}+\ket{10})(\ket{0}X\ket{0}+\ket{1}X\ket{1}) \right)\right)\ket{j}\ket{1} \\
&=\left(\frac{\alpha+\beta}{\sqrt{8}}(\ket{00}+\ket{11})(\ket{00}+\ket{11})+\frac{\alpha-\beta}{\sqrt{8}}\left((\ket{01}+\ket{10})(\ket{01}+\ket{10}) \right)\right)\ket{j}\ket{1} \\
&=\ket{\psi_B}\ket{j}\ket{1} \\
&\overset{H^\otimes 4}\mapsto \\
&\ket{\psi_A}\ket{j}\ket{1}.
\end{align*}\]
Thus, the circuit successfully recovers the encoded state $\ket{\psi_A}$ subject to $X, Z$, or $XZ$ errors.

It can now be shown that Code A can actually protect against any one-qubit unitary $U$ error of known location. This follows from the fact that an arbitrary one-qubit unitary can be expressed in terms of the Pauli operators as
\[
U=c_I I+c_X X +c_Y Y + c_Z Z,
\]
where $Y=-iXZ$ and the vector $(c_I,c_X,c_Y,c_Z)$ of complex numbers has unit norm. Since it has been shown that Code A can correct $I,X, Z$, and $XZ$ errors, then by the linearity of quantum operations an arbitrary one-qubit unitary $U$ can also be corrected because $U$ can be expressed as a linear combination of the Pauli operators.