Quantum Error Correction

Let ${\color{red}{\cal E}}=\{{\color{red}E}_0={\mathchoice {\rm 1\mskip-4mu l} {\rm ... ...kip-4mu l} {\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}},{\color{red}E}_1,\ldots\}$ be the set of errors that we wish to be able to correct. When is there a decoding procedure for the code $C$ such that all errors in ${\color{red}{\cal E}}$ are corrected? When such a decoding procedure exists, we say that ${\color{red}{\cal E}}$ is ``correctable'' (by $C$). A situation in which correctability of ${\color{red}{\cal E}}$ is apparent occurs when the errors ${\color{red}E}_i$ are unitary operators satisfying the condition that ${\color{red}E}_i C$ are mutually orthogonal subspaces. The repetition code has this property for the set of errors consisting of the identity and Pauli operators acting on a single qubit. In this situation, the procedure for decoding is to first make a projective measurement to determine which of the subspaces ${\color{red}E}_i C$ the state is in, and then to apply the inverse of the error operator, ${\color{red}E}_i^\dagger$. This situation is not far from the generic one. One characterization of correctability is in the following theorem:

$$% latex2html id marker 1871\begin{minipage}[b]{6in}\textbf... ... to a restriction to $C$\ of a unitary operator. \end{minipage}$$ (36)

To relate this characterization to detectability, note that the two properties imply that $({\color{red}E}'_i)^\dagger{\color{red}E}'_j C$ is orthogonal to $C$ if $i\not=j$, and $({\color{red}E}'_i)^\dagger {\color{red}E}'_i$ restricted to $C$ is proportional to the identity on $C$. In other words, the $({\color{red}E}'_i)^\dagger{\color{red}E}'_j$ are detectable. This detectability condition applied to the original error set constitutes a second characterization of correctability, given in the next theorem:

$$% latex2html id marker 1888\begin{minipage}[b]{6in}\textbf... ...}E}_i\in{\color{red}{\cal E}}\}$\ are detectable.\end{minipage}$$ (37)

Before explaining the characterizations of correctability, we consider the situation of $n$ qubits, where the characterization by detectability (37) leads to a useful relationship between minimum distance and correctability of low weight errors:

$$% latex2html id marker 1902\begin{minipage}[b]{6in}\textbf... ... of errors of weight at most $e$\ is correctable.\end{minipage}$$ (38)

This theorem follows by observing that the weight of ${\color{red}E}_1^\dagger {\color{red}E}_2$ is at most the sum of the weights of the ${\color{red}E}_i$. As a result of this observation, the problem of finding good ways of correcting all errors up to a maximum weight reduces to that of constructing codes with sufficiently high minimum distance. Thus questions such as ``what is the maximum dimension of a code of minimum distance $d$ on $n$ qubits?'' are of great interest. As in the case of classical coding theory this problem appears to be very difficult in general. Answers are known for small $n$ [6] and there are asymptotic bounds [23]. Of course, for achieving low error probabilities, it is not necessary to correct all errors of weight $\leq e$, just almost all such errors. For example, the concatenated codes used for fault-tolerant quantum computation achieve this goal (see Sec. 7).

For the remainder of this section we explain the characterizations of correctability. Using the conditions for detectability from the previous section, the condition for correctability in Thm. 37 is equivalent to

$$P{\color{red}E}_i^\dagger{\color{red}E}_j P = \lambda_{ij} P$$ (39)

This condition is preserved under a linear change of basis for ${\color{red}{\cal E}}$. That is, if $A$ is any invertible matrix with coefficients $a_{ij}$, we can define new error operators ${\color{red}D}_k=\sum_i {\color{red}E}_ia_{ik}$. For the ${\color{red}D}_k$, the left side of Eq. 39 is

$$P{\color{red}D}_k^\dagger{\color{red}D}_l P = P\left(\sum_{ij} \bar a_{ik} {\color{red}E}_i^\dagger {\color{red}E}_ja_{jl}\right) P$$

$$= \sum_{ij}\bar a_{ik} a_{jl}\lambda_{ij}P$$

$$= \left(A^\dagger\Lambda A\right)_{kl} P,$$ (40)

where $\Lambda$ is the matrix formed from the $\lambda_{ij}$. Using the fact that $\Lambda$ is a positive semidefinite matrix (that is, for all $x$, $x^\dagger \Lambda x \geq 0$ and $\Lambda^\dagger = \Lambda$), we can choose $A$ such that $A^\dagger\Lambda A$ is of the form $\left(\begin{array}{cc}{\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} {\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}&0\\ 0&0\end{array}\right)$. In this matrix, the upper left block is the identity operator for some dimension.

An important consequence of invariance under a change of basis of error operators is that the set of errors correctable by a particular code and decoding procedure is linearly closed. Thus, if ${\color{red}E}$ and ${\color{red}D}$ are corrected by the decoding procedure, then so is $\alpha{\color{red}E}+\beta{\color{red}D}$. This observation also follows from the linearity of quantum mechanically implementable operations.

We explain the condition for correctability by using the subsystems interpretation of decoding procedures. For simplicity, assume that ${\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} {\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}\in{\color{red}{\cal E}}$. To show that correctability of ${\color{red}{\cal E}}$ implies detectability of all ${\color{red}E}\in{\color{red}{\cal E}}^\dagger{\color{red}{\cal E}}$, suppose that we have a decoding procedure that recovers the information encoded in $C$ after any of the errors in ${\color{red}{\cal E}}$ have occurred. Every physically realizable decoding procedure can be implemented by first adding ``ancilla'' quantum systems in a prepared pure state to form a total system labeled $\mathsf {T}$, then applying a unitary map $U$ to the state of $\mathsf {T}$, and finally separating $\mathsf {T}$ into a pair of systems $\mathsf {S},\mathsf {Q}$, where $\mathsf {S}$ corresponds to the syndrome subsystem, and $\mathsf {Q}$ is a quantum system with the same dimension as the code that carries the quantum information after decoding. Denote the state space of the physical system containing $C$ as ${\cal H}$, and the state space of system $\mathsf {X}$ by ${\cal H}_\mathsf {X}$, where $\mathsf {X}$ is any one of the other systems. Let $V$ be the unitary operator that encodes information by mapping ${\cal H}_\mathsf {Q}$ onto $C\subseteq{\cal H}$. We have the following relationships:

$${\cal H}_\mathsf {Q} \stackrel{V}{\leftrightarrow} C\subsete... ...trightarrow} {\cal H}_\mathsf {S}\otimes {\cal H}_\mathsf {Q}.$$ (41)

Here, we used bidirectional arrows `` $\leftrightarrow$'' to emphasize that the operators $V$ and $U$ can be inverted on their range and therefore identify the states in their domains with the states in their ranges. The inclusion ${\cal H}\subseteq{\cal H}_{\mathsf {T}}$ implicitly identifies ${\cal H}$ with the subspace determined by the prepared pure state on the ancillas. The last state space of Eq. 41 is expressed as a tensor product (``$\otimes$''), which is the state space of the combined system $\mathsf {SQ}$. For states of ${\cal H}_\mathsf {Q}$ we write $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace... ...e\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {L}}}}\in C$. Because ${\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} {\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}$ is a correctable error, it must be the case that $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace... ...le\hspace*{-4.3pt}\rangle$}\in {\cal H}_\mathsf {S}\otimes {\cal H}_\mathsf {Q}$ for some state $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{0}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {S}}}}$ of the syndrome subsystem. To establish this fact, use linearity of the maps. In general:

$$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {L}}}} \rightarrow {\color{red}E}_i\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\ver... ...rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {L}}}}$$

$$\stackrel{U}{\leftrightarrow} \mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\ra... ...3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$$ (42)

The $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {S}}}}$ need not be normalized or orthogonal. Let $F$ be the subspace spanned by the $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {S}}}}$. Then $U$ induces an identification of $F\otimes {\cal H}_{Q}$ with a subspace $\bar C\subseteq {\cal H}$. This is the desired subsystem identification. We can then see how the errors act in this identification:

$$\begin{array}{ccc} \mbox{$\vert\hspace*{-3pt}\vert\hspace*{... ...gle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$} \end{array}$$ (43)

This means that for all $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ and $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\phi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$,

$${}^{\scriptscriptstyle\mathsf { L}}\!\mbox{$\langle\hspace*{... ...mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$},$$ (44)

that is, all errors in ${\color{red}{\cal E}}^\dagger{\color{red}{\cal E}}$ are detectable.

Now, suppose that all errors in ${\color{red}{\cal E}}^\dagger{\color{red}{\cal E}}$ are detectable. To see that this implies correctability of ${\color{red}{\cal E}}$, choose a basis for the errors so that $\lambda_{ij} = \delta_{ij} \lambda_i$ with $\lambda_i=1$ for $i<s$ and $\lambda_i=0$ otherwise. Define a subsystem identification by

$$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox... ...3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {L}}}},$$ (45)

for $0\leq i<s$. By assumption and construction, ${}^{\scriptscriptstyle\mathsf { L}}\!\mbox{$\langle\hspace*{-4.3pt}\langle\hspa... ...{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {L}}}} = \delta_{ij}$, which implies that $W$ is unitary (after linear extension), and so this is a proper identification. For $i\geq s$, ${\color{red}E}_i\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox... ...le\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {L}}}} = 0$, which implies that for states in the code, these errors have probability $0$. Therefore, the identification can be used to successfully correct ${\color{red}{\cal E}}$.