17 Quantum error correction
One of the biggest challenges with quantum computing is noise. This means for example that when we apply a unitary to our quantum system, this unitary might not behave exactly as we expect. To overcome this challenge we introduce quantum error correction.
Classically error correction works as follows: We start with some message \(w\), which we encode as \(c\) with some error correcting code. This \(c\) is then transmitted over some noisy communication channel, which introduces some error. The recipient therefore receives a slightly changed version \(c'\). We now try to recover \(c\) from \(c'\) and then hopefully get \(w\) without any error. This can be visualized as follows: \[ \text{word } \omega \xrightarrow{\text{encode}} \text{codeword } c \xrightarrow{\text{noise}} c' \xrightarrow{\text{recovery}} \text{codeword } c \xrightarrow{\text{decode}} \text{word } \omega. \] Important parameters of any error correcting code are the length of the message which we encode \(|w|\), the length of our encoded message \(|c|\) and the number of errors, which recovery can correct.
17.1 Repetition code
One of the simplest classical error correcting codes is the repetition code. The idea is very straightforward: The message \(\omega\) is one bit, and we simply repeat it three times. So we encode a \(0\) as \(000\) and a \(1\) as \(111\). With this encoding, we can correct one error on the transmitted \(c\) by just picking the bit in the majority. E.g. if the received message is \(010\) due to an error, we can still correct it to \(000\).
To summarize \(|\omega| = 1\), \(|c| = 3\) and one error can be corrected.
We now try to construct a similar error correcting code for quantum computers. To do so, we need to overcome two challenges:
In the classical repetition code, we looked at all bits to decide which of them is in the majority. In the quantum world this would mean a measurement of our system, which would destroy our superposition. We therefore need to find a way of measuring the error without measuring the underlying data.
The errors introduced in a quantum system are way more complex. In a classical setting, a single bit can have two states, where one is the correct state and the other is the correct state flipped. Contrary a single qubit can have infinitely many different states and therefore also infinitely many possible errors.
17.1.1 Bit flip code
We first consider a direct analogue to the repetition code, the so-called bit flip code. It encodes \(\ket{0}\) as \(\ket{000}\), and \(\ket{1}\) as \(\ket{111}\).
We can encode a quantum state \(\ket{a}\) using the following circuit:
Note that if course we can also encode non-basis states. E.g. \(\ket{+}\) as \(\frac{1}{\sqrt{2}} \ket{000} + \frac{1}{\sqrt{2}} \ket{111}\) (not as \(\ket{+} \otimes \ket{+} \otimes \ket{+}\)).
Let’s assume a single \(X\)-error happened. By this, we means that an \(X\)-gate was applied to one of the code qubits but we don’t know which. When we measure all three wires we can detect if and on which wire the \(X\)-error has happened. If all bits are the same, no error occurred. If one bit is different then the other two bits, the error must occurred on this wire. The problem is that we then also measure the original message and not only the error position. So we would destroy a superposition, in an encoding of \(\ket{+}\) for example. To get rid of this problem we can use the following circuit:
Note that the wires start with the three different qubits \(\ket{a}\), \(\ket{b}\) and \(\ket{c}\), because they might be different through an error. It is \(m_1 = a \oplus b\) and \(m_2 = a \oplus c\). Now we know the following:
- If \(m_1 = m_2 = 0\): no error,
- If \(m_1 = 0\) and \(m_2 = 1\): error on wire 3,
- If \(m_1 = 1\) and \(m_2 = 0\): error on wire 2,
- If \(m_1 = 1\) and \(m_2 = 1\): error on wire 1.
Since we measure no information on the first three wires, we can detect where the \(X\)-error occurred without losing information. (To prove this, one would of course need to explicitly calculate what happens when we start with a superposition.) And then we just apply \(X\) to that wire to correct the error.
17.1.2 Phase flip code
Using this bit flip code we can only correct \(X\)-errors. But what about e.g. \(Z\)-errors? For these errors, we can use a similar concept by encoding \(\ket{0}\) as \(\ket{+} \otimes \ket{+} \otimes \ket{+}\) and \(\ket{1}\) as \(\ket{-} \otimes \ket{-} \otimes \ket{-}\). This encoding is possible with:
The position of the error can be determined like for the bit flip code using this circuit:
17.2 Shor’s code
We now have an error correcting code for \(X\)-errors and \(Z\)-errors based on repetition. Using both of these techniques, we can create an error correcting code for \(XZ\)-errors. This is called Shor-code.
The idea is to encode one qubit first with the phase flip code and then encode each of the three new qubits using the bit flip code. This encodes the qubits \(\ket{0}\) and \(\ket{1}\) as follows:
\[ \begin{aligned} \ket{0} &\rightarrow \tfrac{1}{2\sqrt{2}} \Bigl(\ket{000} + \ket{111} \Bigr) \otimes \Bigl(\ket{000} + \ket{111} \Bigr) \otimes \Bigl(\ket{000} + \ket{111} \Bigr), \\ \ket{1} &\rightarrow \tfrac{1}{2\sqrt{2}} \Bigl(\ket{000} - \ket{111} \Bigr) \otimes \Bigl(\ket{000} - \ket{111} \Bigr) \otimes \Bigl(\ket{000} - \ket{111} \Bigr). \end{aligned} \]
With this encoding we can correct an \(X\) error. We do this by handling each block as an individual bit flip code. If an \(Y\) error occurred the three blocks are different and we can use a variation of the error handling from the bit phase code.
So we can use the error correcting techniques from above to correct \(X\)-errors and \(Z\)-errors. Since \(Y\) can be constructed from \(X\) and \(Z\), we also can correct \(Y\)-errors with this technique. All in all the Shor-code handles one \(X\),\(Y\) or \(Z\)-error.
Without proof we introduce a theorem:
From this theorem a corollary follows:
17.3 Steane code
Another code is the Steane code. 1 qubit is encoded to 7 qubits and it can correct one error. This code has some nice additional properties useful for fault tolerant computation (see Chapter 18).