Quantum error-correcting codes#
Given a quantum code, it is not clear if it is useful. The above definition only talks about how to encode a message into the codespace. It does not speak at all about which errors can be detected or corrected with such an encoding. Why is this a problem, when this was not a significant problem for classical codes. There are three critical issues which make the construction of a quantum error-correction codes a more difficult task than their classical counterparts.
- The no-cloning theorem forbids us from copying quantum states. This limits the types of operations we can perform during the decoding process.
- Measuring quantum states in superposition destroys the superposition, so we can't simply measure the received blocks to determine what state they are in.
- Classical codes only have to deal with bit-flip errors, but quantum codes will have to deal with any sort of unitary or non-unitary noisy interactions. This includes phase errors, and it includes continuous rotations etc.
Fortunately, we will discover that all of these challenges can be surmounted. To build the theory to do so we start by explicitly defining what conditions make a quantum code an error-correcting one.
An encoding map is a transformation from the message space to the code, the subspace of the codespace, formally defined as follows.
Given a quantum code $\vecs{C}$, an encoding map or encoder is a unitary $U:\vecs{H}^m \to \vecs{H}^c$ that maps the message space to the code.
Given any message $\ket{\psi} \in \vecs{H}^m$, the state $U\ket{\psi}$ is an element of the code $C$. The encoding map is akin to the generator matrix for classical codes.
What we require is that every code $C$ be paired with a set of errors $\st{E}$ that it can correct, and that there exist a process to actually do so.
A quantum error-correction code ($C,\st{E}$) is a quantum code along with a set of errors $\st{E}$, such that given an encoding map $U$ associated with the code, there exists a quantum channel $\oper{D}$, called the decoder, such that for all $E \in \st{E}$ and for all $\ket{\psi} \in \vecs{H}^m$, \begin{equation} \oper{D}\left(EU\ket{\psi}\bra{\psi}U^\dagger E^\dagger\right) = c(E,\ket{\psi}) \ket{\psi}\bra{\psi}, \end{equation} where $c(E,\ket{\psi})$ is a constant.
This definition postulates that the existence of a decoder is necessary for a code to be an error-correcting one. When can such a decoder exist? Whenever, there is enough information extractable from every corrupted codeword so as to reverse the effects of the error. Let's build some basic results that will lead us to some precise mathematical conditions.
First, note that given any error $E_a$ and any state $\ket{\psi} \in \vecs{C}$ the corrupted codeword $\ket{\tilde\psi} = E_a\ket{\psi}$ must be completely outside the code. If it is not, what would happen? We could write $\ket{\psi} = \ket{\psi_c} + \ket{\psi_\perp}$ such that $E_a\ket{\psi_\perp} \in \vecs{C}$ and $E_a\ket{\psi_\perp} \in \vecs{C}^{\perp}$. Now, $\ket{\psi}$ is in the code, then so is $\ket{\psi_c}$ (up to a normalization) and it is some other valid codeword. Hence, the effect of the error $E_a$ on $\ket{\psi_c}$ is to keep it inside the code, i.e.\ map it onto a different codeword. This is clearly a bad situation because Bob would just assume that no error has occurred and $E_a\ket{\psi_c}$ is the codeword Alice meant to send. Hence, by contradiction, we infer that our code must be designed so that all errors move every codeword out of the code.
Next, suppose we have an orthogonal basis $\set{\ket{\psi_i}}_i$ for $\vecs{C}$. Given any error $E_a$, what do we require of $E_a\ket{\psi_i}$ and $E_a\ket{\psi_j}$ for $i\ne j$, so the decoder can function. We will need these two corrupted codewords to remain orthogonal, so that the decoder has enough information to correctly decode. To see this, let's assume to the contrary that the corrupted states are not orthogonal, i.e. $(\bra{\psi_i}E_a^\dagger)( E_a\ket{\psi_j}) \ne 0$. To tease out the non-orthogonal part of this inner product, let's write \begin{equation} \ket{\psi_j} = \ket{\psi_\parallel} + \ket{\psi_\perp}, \end{equation} such that $E_a\ket{\psi_\parallel}$ is parallel to $E_a\ket{\psi_i}$, while $E_a\ket{\psi_\perp}$ is perpendicular to $E_a\ket{\psi_i}$. As in the argument above, $\ket{\psi_\parallel}$ must also be a valid codeword (because it is part of $\ket{\psi_j}$). And because $\ket{\psi_i}$ and $\ket{\psi_j}$ are perpendicular, $\ket{\psi_\parallel}$ and $\ket{\psi_i}$ are distinct codewords. Hence, we discover that two distinct codewords, $\ket{\psi_\parallel}$ and $\ket{\psi_i}$, when acted upon by error $E_a$ result in the same corrupted codeword. This is again a bad situation, because the decoder will be unable to decide how to fix the error on the corrupted codeword. Hence, in order to have an error-correcting code that works, we need each error to map orthogonal basis vectors of $C$ to orthgonal states, \begin{equation} (\bra{\psi_i}E_a^\dagger) (E_a\ket{\psi_j}) = 0, \quad i\ne j. \end{equation}
Let's now make an even stronger condition on our code. Consider the corrupted codewords $E_a\ket{\psi_i}$ and $E_b\ket{\psi_j}$, i.e. distinct errors on two distinct basis states. Do these need to be orthogonal? By exactly the same argument as above, yes. In words, if these two corrupted codewords are not orthogonal, then there is a part of $\ket{\psi_j}$, called $\ket{\psi_\parallel}$, that under the action of $E_b$ becomes parallel to $E_a\ket{\psi_i}$. As above, $\ket{\psi_\parallel}$ is a valid codeword. If the Bob receives $E_a\ket{\psi_i} = E_b\ket{\psi_\parallel}$, then his decoder will be unable to tell if Alice sent $\ket{\psi_i}$ which was distorted by $E_a$ or $\ket{\psi_\parallel}$ which was distorted by $E_b$. Hence, we can conclude that for a valid error-correcting code, \begin{equation} (\bra{\psi_i}E_a^\dagger) (E_b\ket{\psi_j}) = 0, \quad i\ne j. \end{equation}
What about the case when $i = j$ with distinct errors? Meaning, is there any requirement on $E_a\ket{\psi_i}$ and $E_b\ket{psi_i}$? First of all, let's make it clear that these don't need to be orthogonal - though they can be. We saw the example of the phase-flip code where the action of $Z$ on different qubits yielded the same corrupted codeword. But this was not a problem, because in each case, the correction operation was the same. So up till now, our condition is \begin{equation} \bra{\psi_i}E_a^\dagger E_b\ket{\psi_j} = \delta_{ij}A, \end{equation} where the $\delta_{ij}$ ensures that the inner product is zero if we are dealing with two different basis states, and possibly non-zero if they are the same. This last part is determined by the unknown constant $A$. However, we can recognize that if $E_a\ket{\psi_i}$ and $E_b\ket{\psi_i}$ are indeed orthogonal for every pair of errors $E_a$ and $E_b$, then our code will be an error-correcting one. We assume, \begin{equation} \bra{\psi_i}E_a^\dagger E_b\ket{\psi_j} = \delta_{ij}\delta_{ab}A. \end{equation} Now, recall that when we went from the noise channel to the set $\set{E_a}_a$ we choose from the one of the infinite such sets. Let's transform to a different set $\set{F_c}$ where \begin{equation} F_c = \sum_a\alpha_{ca}E_a. \end{equation} Now, let's evaluate the inner product \begin{align} \bra{\psi_i}F_c^\dagger F_d\ket{\psi_j} &= \sum_{ab}\alpha_{ca}^*\alpha_{db}\bra{\psi_i}E_a^\dagger E_b\ket{\psi_j}, \\ &= \sum_{ab}\alpha_{ca}^*\alpha_{db}\delta_{ij}\delta_{ab}A, \\ &= \left(\sum_a\alpha_{ca}^*\alpha_{da}A\right)\delta_{ij}, \\ &= A_{cd}'\delta_{ij}. \tag{*} \end{align} What this calculation tells us that, unless we pick a very clever basis for the errors, the states $E_a\ket{\psi_i}$ and $E_b\ket{\psi_i}$ will not be orthogonal for every $i$ and every pair of $E_a$ and $E_b$.
In the above, we have taken care of every possible case of possible confusion of the detector, and resolved them. We can now use Eq. (*) to write down the following theorem.
Theorem: A code $\vecs{C}$ is a quantum error-correcting code for the set of errors $\set{E_a}$ iff \begin{equation} \bra{\psi_i}E_a^\dagger E_b\ket{\psi_j} = A_{ab}\delta_{ij}, \end{equation} for the orthogonal basis $\set{\ket{\psi_i}}_i$.