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
, an encoding map or encoder is a unitary that maps the message space to the code.
Given any message
What we require is that every code
A quantum error-correction code (
) is a quantum code along with a set of errors , such that given an encoding map associated with the code, there exists a quantum channel , called the decoder, such that for all and for all , where 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
and any state the corrupted codeword must be completely outside the code. If it is not, what would happen? We could write such that and . Now, is in the code, then so is (up to a normalization) and it is some other valid codeword. Hence, the effect of the error on 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 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
for . Given any error , what do we require of and for , 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. . To tease out the non-orthogonal part of this inner product, let's write such that is parallel to , while is perpendicular to . As in the argument above, must also be a valid codeword (because it is part of ). And because and are perpendicular, and are distinct codewords. Hence, we discover that two distinct codewords, and , when acted upon by error 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 to orthgonal states,Let's now make an even stronger condition on our code. Consider the corrupted codewords
and , 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 , called , that under the action of becomes parallel to . As above, is a valid codeword. If the Bob receives , then his decoder will be unable to tell if Alice sent which was distorted by or which was distorted by . Hence, we can conclude that for a valid error-correcting code,What about the case when
with distinct errors? Meaning, is there any requirement on and ? 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 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 where the 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 . However, we can recognize that if and are indeed orthogonal for every pair of errors and , then our code will be an error-correcting one. We assume, Now, recall that when we went from the noise channel to the set we choose from the one of the infinite such sets. Let's transform to a different set where Now, let's evaluate the inner product What this calculation tells us that, unless we pick a very clever basis for the errors, the states and will not be orthogonal for every and every pair of and .
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