E. Knill, R. Laflamme, A. Ashikhmin, H. Barnum, L. Viola and W. H. Zurek
28 July 2002
When physically realized, quantum information processing (QIP) can be used to solve problems in physics simulation, cryptanalysis and secure communication for which there are no known efficient solutions based on classical information processing. Numerous proposals exist for building the devices required for QIP by using a variety of systems that exhibit quantum properties. Examples include nuclear spins in molecules, electron spins or charge in quantum dots, collective states of superconductors, and photons [1]. In all of these cases, there are well established physical models that, under ideal conditions, allow for exact realizations of quantum information and its manipulation. However, real physical systems never behave exactly like the ideal models. The main problems are environmental noise, which is due to incomplete isolation of the system from the rest of the world, and control errors, which are caused by calibration errors and random fluctuations in control parameters. Attempts to reduce the effects of these errors are confronted by the conflicting needs of being able to control and reliably measure the quantum systems. These needs require strong interactions with control devices, and systems sufficiently well isolated to maintain coherence, which is the subtle relationship between the phases in a quantum superposition. The fact that quantum effects rarely persist on macroscopic scales suggests that meeting these needs requires considerable outside intervention.
Soon after P. Shor published the efficient quantum factoring algorithm with its applications to breaking commonly used public-key cryptosystems, A. Steane [2] and P. Shor [3] gave the first constructions of quantum error-correcting codes. These codes make it possible to store quantum information so that one can reverse the effects of the most likely errors. By demonstrating that quantum information can exist in protected parts of the state space, they showed that, in principle, it is possible to protect against environmental noise when storing or transmitting information. Stimulated by these results and in order to solve the problem of errors happening during computation with quantum information, researchers initiated a series of investigations to determine whether it was possible to quantum-compute in a fault-tolerant manner. The outcome of these investigations was positive and culminated in what are now known as ``accuracy threshold theorems'' [4,5,6,7,8,9,10,11,12,13,14,15]. According to these theorems, if the effects of all errors are sufficiently small per quantum bit (qubit) and step of the computation, then it is possible to process quantum information arbitrarily accurately with reasonable resource overheads. The requirement on errors is quantified by a maximum tolerable error rate called the threshold. The threshold value depends strongly on the details of the assumed error model. All threshold theorems require that errors at different times and locations be independent and that the basic computational operations can be applied in parallel. Although the proven thresholds are well out of range of today's devices there are signs that in practice, fault-tolerant quantum computation may be realizable.
In retrospect, advances in quantum error correction and fault-tolerant computation were made possible by the realization that accurate computation does not require the state of the physical devices supporting the computation to be perfect. In classical information processing, this observation is so obvious that it is often forgotten: No two letters ``e'' on a written page are physically identical, and the number of electrons used to store a bit in a computer's memory varies substantially. Nevertheless, we have no difficulty in accurately identifying the desired letter or state. A crucial conceptual difficulty with quantum information is that by its very nature, it cannot be identified by being ``looked'' at. As a result, the sense in which quantum information can be accurately stored in a noisy system needs to be defined without reference to an observer. There are two ways to accomplish this task. The first is to define stored information to be the information that can, in principle, be extracted by a quantum decoding procedure. The second is to explicitly define ``subsystems'' (particle-like aspects of the quantum device) that contain the desired information. The first approach is a natural generalization of the usual interpretations of classical error-correction methods, whereas the second is motivated by a way of characterizing quantum particles.
In this introduction we motivate and explain the ``decoding'' and ``subsystems'' view of quantum error correction. We explain how quantum noise in QIP can be described and classified, and summarize the requirements that need to be satisfied for fault tolerance. Considering the capabilities of currently available quantum technology, the requirements appear daunting. But the idea of ``subsystems'' shows that these requirements can be met in many different, and often unexpected ways.
Our introduction is structured as follows: The basic concepts are introduced by example, first for classical and then for quantum codes. We then show how the concepts are defined in general. Following a discussion of error models and analysis (Sect. 4), we state and explain the necessary and sufficient conditions for detectability of errors and correctability of error sets (Sect. 5). This is followed by a brief introduction to two of the most important methods for constructing error-correcting codes and subsystems (Sect. 6). For a basic overview, it suffices to read the beginnings of these more technical sections. The principles of fault-tolerant quantum computation are outlined in the last section.
Particles