7
Quantum Error Correction
Markus Grassl
Max‐Planck‐Institut für die Physik des Lichts, Staudtstraße 2, 91058 Erlangen, Germany
7.1 Introduction
In the theory of quantum information processing, it is usually assumed that the quantum mechanical system is completely decoupled from its environment. On the other hand, when implementing quantum operations on a real quantum mechanical system, some interaction with the system is needed in order to control the dynamics of the system. Moreover, this control has only finite precision. So it seems to be inevitable that the state of the quantum systems decoherence, and, eventually the behavior of the system, becomes more and more classical. Before Shor's first paper on quantum error correction (1), it was widely believed that quantum information processing was a purely theoretical computation model without any perspective of realization.
More than 20 years later, the theory of quantum error correction is widely developed. In what follows, we give an introduction to the basic concepts of quantum error correction, illustrated by some simple quantum error‐correcting codes (QECCs). We start with a brief introduction to the general mathematical framework.
7.2 Quantum Channels
Similar to the classical situation, one needs a model of the errors in order to design a code that is able to correct them. For this, we consider the joint Hilbert space 
of the system used for information processing and its environment. If the dimensions of both Hilbert spaces are sufficiently large, the initial state is without loss of generality pure. Moreover, we make the assumption that initially the system and its environment are decoupled, that is, the initialization process is perfect. Again by possibly increasing the dimension of the Hilbert spaces, the interaction between the system and the environment can be modeled by a unitary transformation 
on the joint Hilbert space (see Figure 7.1).
Figure 7.1 Modeling the interaction with the environment by a unitary transformation.
As we have no access to the environment, we are only interested in the state of the system and its dynamics. Tracing out the environment yields the possibly mixed state
Equivalently, the state 7.1 can be written as a function of the input state 
in the form
where the operators 
are the so‐called error operators or Kraus operators (2). They completely describe the quantum channel given by the initial state 
of the environment and the unitary interaction 
. Not all choices for a set of Kraus operators give rise to a quantum mechanical channel, but a quantum channel has nonetheless many degrees of freedom. In what follows, we consider some important special cases.
For qubit systems, the depolarizing channel can also be described as follows:
In this representation, the channel transmits the state undisturbed with probability 
, and with probability 
an error operator is applied. The four different error operators are given by the Pauli matrices and identity, each of which is applied with equal probability. This means that in the “error case” with equal probability the spin of a spin‐
particle is unchanged or one of the 
‐, 
‐, or 
‐components is flipped.
In some sense, the depolarizing channel is the quantum mechanical generalization of a uniform symmetric channel. Any input state is treated in the same way; there are no states that are transmitted particularly good or bad. The next channel is basis dependent.
The quantum mechanical analogue of a memoryless channel is a product channel, which is defined for a quantum system 
with 
subsystems of equal dimension, that is, 
. The product channel is given by 
uses of a channel 
on 
, acting independently on each of the 
subsystems. If the channel 
is given by the error operators 
, the error operators of the product channel on 
are
In order to compare quantum channels – with or without error correction – we have to quantify how close the output of a quantum channel is to the input, that is, how much the state has been changed by the channel. As we allow a channel to act on a part of the system, we additionally want to preserve a possible entanglement of the input state with the rest of the system. The situation is depicted in Figure 7.2. The state space of the system is 
. The quantum channel 
, represented by 
, acts only on 
. Tracing out the environment 
, we get the state 
on 
. Hence, the state 
is mapped to 
.
Figure 7.2
Unitary representation of a quantum channel acting on the subsystem 
of the composed system 
.
The entanglement fidelity of the channel 
described by the initial state 
of the environment and the unitary transformation 
is given by
where the minimization is over all pure states 
of the composed system 
. It can be shown that 7.2 is independent of the system 
and can be computed in terms of the error operators 
of the channel (3):
where the minimization is over all mixed states 
of the system 
.
Now we are ready to define the capacity of a quantum channel. For simplicity, we consider quantum systems composed of subsystems of equal dimension.
Expression 7.3 states that, in the limit of large 
for a given number 
of inputs to our system, we can find encoding and decoding operations 
and 
such that the fidelity of the composed channel 
approaches 1. As the channel is memoryless, 
uses of the channel do not introduce any correlations between the subsystems. However, using entangled input states for the channel 
may help us to increase the fidelity. Therefore, the capacity of the channel 
might be strictly larger than twice the capacity of 
. Because of this phenomenon of superadditivity, it is very hard to compute the quantum channel capacity. In general, superadditivity is one of the big puzzles of quantum information theory.
We close this section with a criterion for the question when perfect error correction is possible, that is, when it is possible to attain fidelity in 7.3 for finite 
. A QECC in this sense is a subspace 
of the Hilbert space on which the channel acts such that restricted to that subspace the operator 
can be inverted.
From the proof of Theorem 7.1 given in (5,6), it is possible to derive an in‐principle algorithm that allows the error correction. As in the classical case (cf. Section 1.3.4), we cannot expect to have an efficient algorithm for the general situation.
A common misinterpretation of the conditions (7.4) is that it was only possible to correct exactly those errors that are one of the error operators 
, that is, only a finite number of errors could be corrected. However, conditions (7.4) are linear in the error operators. To show this, we introduce the new error operators
which are arbitrary linear combinations of the 
. Using (7.4) we compute
where 
is some constant depending on the operators 
and 
only. Hence, conditions (7.4) guarantee that the effect of any error operator 
that is in the linear span of the error operators 
can be corrected. It also demonstrates that it is sufficient to check (7.4) for a vector space basis of 
and hence for a finite set of errors. For qubit systems, the Pauli matrices
together with identity form a vector space basis of all matrices in 
. For a quantum code using 
qubits, we consider the tensor product of Pauli matrices and identity as the so‐called error basis. For an element of the error bases, the number of tensor factors different from identity is referred to as the number of errors or the weight of an error. This naturally generalizes to any error operator that can be written as a tensor product. The weight equals the number of subsystems on which the operator acts nontrivially.
7.3 Using Classical Error‐Correcting Codes
7.3.1 Negative Results: The Quantum Repetition Code
At the end of the previous section, we had seen that it is sufficient to be able to correct a finite number of different errors. Additionally, using error bases whose elements are tensor products, we have the notion of the weight of an error. This is very similar to the situation for classical error correction. In Section 1.3.1, pp. 7f, we have seen that the simplest way of protecting classical information against errors is to replicate the information several times. For quantum states, the encoding transformation for an 
‐fold quantum repetition code must implement the following map:
From the linearity of quantum mechanics, it follows that there is no quantum transformation such that 7.5 holds for all input states 
(cf. the “no‐cloning theorem” (7)).
If the input state 
or an algorithm for its preparation is known, one can, of course, also prepare 
independent copies of the state and send them through the quantum channel. However, at the receiver's side, a quantum mechanical analogue of majority decision is required. Again, it is impossible to unambiguously decide if, for example, two of three unknown quantum states 
are identical and then output a quantum state 
that equals the majority of the states. While at the sender's side, the no‐cloning theorem could be circumvented, the direct quantum mechanical analogue of the repetition code fails at the receiver's side. An approach to avoid the no‐go theorems for quantum repetition codes – which is different from what we will see in the next section – encodes quantum information in symmetric spaces (8).
7.3.2 Positive Results: A Simple Three‐Qubit Code
The direct application of a fundamental principle of classical error‐correcting codes, namely, the replication of information, essentially fails because quantum mechanics allows the coherent superposition of basis states. When restricted to basis states, the theory becomes completely classical, and error correction is possible.
So in order to implement mechanisms that allow the correction of errors, we turn our attention to the basis states and additionally require that all operations are linear, that is, everything works for superpositions as well. From the characterization of quantum error‐correcting codes in Theorem 7.1, we have already learned that it suffices to deal with a finite set of errors. For qubit systems, these error operators are tensor products of Pauli matrices. The operator 
interchanges the basis states 
and 
; hence, it corresponds to a classical bit‐flip error. Similarly, the operator 
changes the sign of the state 
; hence, it is referred to as a sign‐flip error. With respect to the Hadamard transformed basis 
and 
, the rôle of 
and 
is interchanged, that is, 
flips the basis states and 
changes the sign of the state 
. From the relations among the Pauli matrices, it follows that 
is proportional to the product of 
and 
. Hence, a 
‐error can be modeled as a combination of a bit‐flip and a phase‐flip error on the same qubit.
The first approach is to deal with the two basic types of errors, bit flip and phase flip, independently. If we want to correct for bit‐flip errors only, we are almost in the situation of classical error‐correcting codes. Therefore, we apply the principle of the repetition code to the basis states and obtain the following code, which can already be found in (9):
By construction, the mapping 7.6 is linear, that is, the superposition 
is mapped to 
. The states 
and 
span a two‐dimensional subspace 
. Flipping the spin in one of the subsystems we obtain the following states:
The four different cases yield four mutually orthogonal subspaces, that is, the Hilbert space of three qubits can be decomposed as follows:
By a projective measurement whose eigenspaces are the two‐dimensional spaces 
in 7.7, one obtains information about the error without disturbing the superposition within the corresponding two‐dimensional subspace. However, a phase flip, say the error 
acting on the first qubit, changes the coefficients 
and 
of the superposition, but the resulting state does not leave the subspace 
. Hence, the measurement does not detect such an error and hence it cannot be corrected.
Figure 7.3 Quantum circuit for encoding one qubit, computing the error syndrome, and extracting two classical syndrome bits.
The projective measurement distinguishing the different errors can be implemented using an auxiliary quantum system. The basis states of the subspaces 
are characterized by comparing the first and last qubit as well as the second and the last qubit. Using the correspondence 
and 
, comparing two qubits translates into computing the sum modulo 2 of the labels 0 and 1 of the basis states. A quantum circuit that implements the encoding 7.6 and the measurement is shown in Figure 7.3. Measuring the two ancilla qubits one obtains two classical bits 
and 
, which, like the error syndrome of a classical linear block code (see Proposition 1.3), provide information about the error. From this error syndrome, one has to deduce the most likely error and then correct it.
Figure 7.4 Quantum circuit for encoding one qubit, computing the error syndrome, and coherent error correction.
The quantum circuit shown in Figure 7.4 integrates the error‐correction step as well. Using multiply controlled quantum gates, the three different correction operators are applied depending on the state of the syndrome qubits 
. It can be shown that after the error‐correction step, the syndrome qubits 
are not entangled with the code qubits 
.
As already discussed earlier, the Hadamard transform interchanges the rôle of bit‐flip and phase‐flip errors. Therefore, we can obtain a code that can correct a single phase‐flip error by using essentially the same three‐qubit code, but replacing the basis states 
and 
by 
and 
, respectively. Rewriting everything with respect to the computation basis 
and 
, we obtain the following orthogonal decomposition of the state space shown in Table 7.1.
Table 7.1 Orthogonal decomposition corresponding to the three‐qubit code correcting a single phase‐flip error.
| Phase flip | State | Subspace |
| No error |
|
|
position |
|
|
position |
|
|
position |
|
|
7.3.3 Shor's Nine‐Qubit Code
The three‐qubit code of the previous section corrects a single bit‐flip error and its Hadamard transformed version of the code can correct a single phase‐flip error, but it is not able to correct both types of errors at the same time. A solution to this problem can be obtained by using two levels of error correction. On the first level, we use the three‐qubit code 7.6, which protects against a single‐bit flip of any of the three qubits. So every logical qubit is represented by three physical qubits:
A phase‐flip error on any of the three physical qubits has the following effect:
In terms of the logical qubits, these operators act as an encoded 
‐operator, that is,
where 
corresponds to any of the three‐qubit operators in 7.9. For the second level of encoding, we use the three‐qubit code
correcting a single phase‐flip error. For the states 
and 
in 7.10, we use the logical qubits of 7.8. This yields the following encoding (1):
This encodes one logical qubit using nine physical qubits. A single bit‐flip error on the physical qubits can be corrected using the first level of encoding. So actually we can correct bit flips in any of the three groups of three physical qubits. A single phase‐flip error on the physical qubits corresponds to an encoded sign‐flip with respect to the first level of encoding, which can be corrected using the second level of encoding. In summary, we can independently correct single bit‐flip errors and single phase‐flip errors. The combination of a bit‐flip error and a phase‐flip error corresponds to the Pauli matrix 
. Therefore, we can correct all single‐qubit errors corresponding to the Pauli matrices. From the linearity of conditions (7.4), it follows that the Shor's nine‐qubit code (7.11) can correct an arbitrary error acting on any of the nine qubits.
There are even some errors of weight two that can be corrected. As bit‐flip and phase‐flip errors are corrected independently, they may act on different qubits. If there are two bit‐flip errors acting on different blocks corresponding to the first level of encoding, for example, the first and fifth qubit, they can be corrected, too. Two phase‐flip errors acting on the same block have no effect at all, so there is no need to correct them. However, two phase‐flip errors acting on different blocks have the same effect as a single phase‐flip error and interchanging the encoded basis states. Hence, the code only guarantees to be able to correct an arbitrary error of weight one. In analogy to the notation used for linear block codes (cf. Section 1.3.3, p. ), this code is denoted by 
, or in general as 
. Here 
and 
refer to the number of logical and physical qubits, respectively. The minimum distance 
is not related to a distance in the usual sense on Hilbert or operator spaces, it rather has the following operational interpretation:
For quantum codes, we get the analogue of Theorem 1.6 on p. :
7.3.4 Steane's Seven‐Qubit Code and CSS Codes
The main idea underlying Shor's QECC is to use the concatenation of two codes, one code being able to correct bit flips while the other one to correct phase flips. In order to obtain a more efficient QECC, that is, a code for which the rate 
or, equivalently, the fraction of logical qubits related to the number of physical qubits is larger, we have to find a code that is able to correct both types of errors using only a single layer of encoding. We have seen that quantum states, which are basis states corresponding to codewords of classical binary codes, such as the triple‐repetition code, are able to deal with bit‐flip errors. Furthermore, the Hadamard transformation interchanges the rôle of bit flips and phase flips. The idea is now to use certain superpositions of states corresponding to a binary code, such that after a Hadamard transformation we are still able to correct bit‐flip errors. For this, we use the following lemma:
Lemma 7.1 shows that the Hadamard transformation does not only change phase‐flip errors into bit‐flip errors, but also maps superpositions of all codewords of the linear binary code 
to superpositions of all codewords of the dual code 
(cf. Proposition 1.4, p. ). The 
Hamming code 
of Example 1.4, p. contains its dual code 
, that is, 
. Hence, we can partition the codewords of 
into two cosets of 
as follows:
Based on this decomposition, we define the following encoding:
Hadamard transformation of these states yields
A superposition 
of the logical qubits is a superposition of words of the Hamming code 
. This implies that a single bit‐flip error can be corrected. From (7.13), it can be seen that Hadamard transformation of the state 
is again a superposition of words of the Hamming code, so a single phase‐flip error can be corrected as well. Similar to Shor's nine‐qubit code, for this seven‐qubit code (7.12), bit flips and phase flips can be corrected independently. The generalization of this construction principle is now known as CSS codes and was independently derived by Calderbank and Shor (10) and Steane (11,12).
7.3.5 The Five‐Qubit Code and Stabilizer Codes
By the CSS construction outlines in the previous section, the rate of a single‐error‐correcting code can be improved from 
for Shor's code to 
. Instead of two layers of encoding, only a single layer is used, while the correction of bit‐flip errors and phase‐flip errors can still be done independently. As we will see next, integrating the error correction into a single step will result in a further improved rate.
The theory of CSS codes is closely connected to binary codes whose codewords are used as labels for the quantum states. Quantum error correction is basically reduced to the correction of bit‐flip errors. This corresponds to a Schrödinger picture, that is, the effect of the error operators on the quantum states is considered. Alternatively, we may develop a Heisenberg picture of quantum error correction (see also (13)).
For Shor's nine‐qubit code, we have seen that there are nontrivial error operators, which have no effect at all, for example, two phase‐flip errors acting on qubits within the same block. Also, flipping all bits in two blocks does not change the logical qubits 
and 
. In general, we have some error operators 
with
Hence, the code 
lies in the eigenspace of 
with eigenvalue 
. We consider all operators 
, which are tensor products of Pauli matrices and identity, which generate to the so‐called (
qubit) Pauli group. The elements of the Pauli group for which (7.14) holds form a subgroup, the stabilizer group 
of an error‐correcting code 
. For Shor's nine‐qubit code (7.11), we find the following set of error operators acting trivially on the logical qubits:
where we have omitted the tensor product symbols. This set is minimal in the sense that none of the stabilizers 
can be expressed as product of the others. Two elements of the Pauli group either commute or anticommute, that is, 
. Together with (7.14), this implies that the stabilizer group is Abelian. Starting with an Abelian subgroup of the Pauli group, we get the following definition:
The error‐free states of the stabilizer code 
are characterized as being an eigenstate of the stabilizers with eigenvalue 
. As the Pauli matrices are both unitary and Hermitian, we can interpret them as observables as well. Measuring the stabilizers 7.15, we obtain an error syndrome similar to that of classical block codes (cf. Proposition 1.3, p. ). Here, the measurements yield eight eigenvalues 
, which form a binary syndrome vector of length eight. A bit flip of the first qubit, that is, the operator 
, commutes with all but the first stabilizer 
. Therefore, a bit‐flip error on the first position changes the first bit of the syndrome. A phase‐flip error on the second position 
commutes with all stabilizers apart from 
. Hence, this error changes the entry 
of the syndrome. In total, we have 
different single‐qubit errors. For the error syndrome, respectively the sign of the eigenvalues measured, we have 
different possibilities. This indicates that, as in the classical case (cf. Table 1.2, p. ), the code can correct more errors than what is guaranteed by its minimum distance.
For the nine‐qubit code, we are measuring the eight independent commuting observables 7.15. This yields an orthogonal decomposition of the space of nine qubits into 
two‐dimensional spaces. Similar to 7.7 and Table 7.1, the coefficients of a superposition of logical qubits are preserved within those spaces. So measuring the stabilizers provides information about the eigenspace and thereby about the error, but does not provide any information about the logical quantum state.
Using this type of construction, which is due to Gottesman (14) and Calderbank et al. (15), one gets the most efficient QECC with one logical qubit correcting one error. The stabilizer for such a five‐qubit code 
is generated by
Measuring the stabilizers 7.16 yields four syndrome bits. The 
different possible syndromes match the total number of possible errors, namely, the 
different one‐qubit errors and the no‐error event.
Similarly as the CSS construction is using classical linear binary codes, the theory of stabilizer codes can be linked to block codes over the field 
with four elements (15) (for more details, see also (16)).
7.4 Further Aspects
In this introduction to QECCs, we have neglected almost all algorithmic aspects, such as quantum circuits for encoding and decoding. For CSS codes, one can derive efficient quantum circuits for encoding and syndrome computation consisting of 
and Hadamard gates only ( 5, 6). Quantum circuits for encoding stabilizer codes can be realized with polynomially many elementary gates as well, and the algorithm to construct them has polynomial complexity, too. Two alternative versions can be found in (17) and (18). Both naturally extend to QECCs for quantum systems whose subsystems are not qubits, but have a higher dimension. The theory of such codes is presented in (19). Some aspects of finding codes with both high rate and high minimum distance are discussed in (20).
The question of decoding, including the correction of errors, is a bit more complicated. Both the CSS construction and stabilizer codes reduce the problem of quantum error correction to the problem of the correction of errors for a classical code. This step, namely, the computation of an error syndrome, can be solved by techniques similar to those used for the encoding circuits. The remaining task is to determine the most likely error given the syndrome. From the theory of classical error‐correcting codes, we have some classes of codes for which this problem can be efficiently solved at least for a subset of all correctable errors. Among these codes, the cyclic codes are particularly interesting (21).
Another aspect that has been ignored in this introduction is the dynamics on quantum codes. The ultimate goal is to process quantum information. In the discussion of Shor's nine‐qubit code, we have already seen that there are also encoded operators that preserve the code space, but act nontrivially on it. It has been shown that one can implement a universal set of encoded quantum gates in such a way that failures of a small number of gates can be corrected either in a later error‐correction step, or more importantly, using concatenated codes. This eventually allows us to prove the so‐called threshold theorem, which implies that one can perform arbitrarily long quantum computations with bounded residual error and reasonable overhead for error correction provided that each individual gate has a failure probability below some threshold (see e.g., (22)). Unfortunately, the gap between what can be achieved in the laboratories and what is demanded by the theory is still large.
References
- 1 Shor, P.W. (1995) Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 52 (4), R2493–R2496.
- 2 Kraus, K. (1983) States, Effects, and Operations, Lecture Notes in Physics, vol. 190, Springer‐Verlag, Berlin.
- 3 Schumacher, B. (1996) Sending entanglement through noisy quantum channels. Phys. Rev. A, 54 (4), 2614–2628.
- 4 Knill, E. and Laflamme, R. (1997) Theory of quantum error‐correcting codes. Phys. Rev. A, 55 (2), 900–911.
- 5 Grassl, M. (2002) Algorithmic aspects of quantum error‐correcting codes, in Mathematics of Quantum Computation (eds R.K. Brylinski and G. Chen), CRC Press, Boca Raton, FL, pp. 223–252.
- 6 Grassl, M. (2001) Fehlerkorrigierende Codes für Quantensysteme: Konstruktionen und Algorithmen, Shaker, Aachen, 2002. Zugl.: Universität Karlsruhe, Dissertation.
- 7 Wootters, W.K. and Zurek, W.H. (1982) A single quantum cannot be cloned. Nature, 299 (5886), 802–803.
- 8 Barenco, A., Berthiaume, A., Deutsch, D., Ekert, A., Jozsa, R., and Macchiavello, C. (1997) Stabilization of quantum computations by symmetrization. SIAM J. Comput., 26 (5), 1541–1557.
- 9 Peres, A. (1985) Reversible logic and quantum computers. Phys. Rev. A, 32 (6), 3266–3276.
- 10 Calderbank, A.R. and Shor, P.W. (1996) Good quantum error‐correcting codes exist. Phys. Rev. A, 54 (2), 1098–1105.
- 11 Steane, A.M. (1996) Simple quantum error correcting codes. Phys. Rev. A, 54 (6), 4741–4751.
- 12 Steane, A.M. (1996) Error correcting codes in quantum theory. Phys. Rev. Lett., 77 (5), 793–797.
- 13 Gottesman, D. (1999) The Heisenberg representation of quantum computers, in Proceedings of the 22nd International Colloquium on Group Theoretical Methods in Physics (eds S.P. Corney, R. Delbourgo, and P.D. Jarvis), International Press, Cambridge, MA, pp. 32–43.
- 14 Gottesman, D. (1996) A class of quantum error‐correcting codes saturating the quantum hamming bound. Phys. Rev. A, 54 (3), 1862–1868.
- 15 Calderbank, A.R., Rains, E.M., Shor, P.W., and Sloane, N.J.A. (1998) Quantum error correction via codes over GF(4). IEEE Trans. Inf. Theory, 44 (4), 1369–1387.
- 16 Beth, T. and Grassl, M. (1998) The quantum hamming and hexacodes. Fortschr. Phys., 46 (4–5), 459–491.
- 17 Cleve, R. and Gottesman, D. (1997) Efficient computations of encodings for quantum error correction. Phys. Rev. A, 56 (1), 76–82.
- 18 Grassl, M., Rötteler, M., and Beth, T. (2003) Efficient quantum circuits for non‐qubit quantum error‐correcting codes. Int. J. Found. Comput. Sci., 14 (5), 757–775.
- 19 Ashikhmin, A. and Knill, E. (2001) Nonbinary quantum stabilizer codes. IEEE Trans. Inf. Theory, 47 (7), 3065–3072.
- 20 Grassl, M., Beth, T., and Rötteler, M. (2004) On optimal quantum codes. Int. J. Quantum Inf., 2 (1), 55–64.
- 21 Grassl, M. and Beth, T. (2000) Cyclic quantum error‐correcting codes and quantum shift registers. Proc. R. Soc. London, Ser. A, 456 (2003), 2689–2706.
- 22 Knill, E., Laflamme, R., and Zurek, W.H. (1998) Resilient quantum computation: error models and thresholds. Proc. R. Soc. London, Ser. A, 454 (1969), 365–384.