## Tuesday, 10 December 2013

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