Qubit.org

Abstract: The subject of quantum computing brings together ideas from classical information theory, computer science, and quantum physics. This review aims to summarise not just quantum computing, but the whole subject of quantum information theory. It turns out that information theory and quantum mechanics fit together very well. In order to explain their relationship, the review begins with an introduction to classical information theory and computer science, including Shannon's theorem, error correcting codes, Turing machines and computational complexity. The principles of quantum mechanics are then outlined, and the EPR experiment described. The EPR-Bell correlations, and quantum entanglement in general, form the essential new ingredient which distinguishes quantum from classical information theory, and, arguably, quantum from classical physics. Basic quantum information ideas are described, including key distribution, teleportation, data compression, quantum error correction, the universal quantum computer and quantum algorithms. The common theme of all these ideas is the use of quantum entanglement as a computational resource. Experimental methods for small quantum processors are briefly sketched, concentrating on ion traps, high Q cavities, and NMR. The review concludes with an outline of the main features of quantum information physics, and avenues for future research.

Introduction

The science of physics seeks to ask, and find precise answers to, basic questions about why nature is as it is. Historically, the fundamental principles of physics have been concerned with questions such as "what are things made of?" and "why do things move as they do?" In his Principia, Newton gave very wide-ranging answers to some of these questions. By showing that the same mathematical equations could describe the motions of everyday objects and of planets, he showed that an everyday object such as a tea pot is made of essentially the same sort of stuff as a planet: the motions of both can be described in terms of their mass and the forces acting on them. Nowadays we would say that both move in such a way as to conserve energy and momentum. In this way, physics allows us to abstract from nature concepts such as energy or momentum which always obey fixed equations, although the same energy might be expressed in many different ways: for example, an electron in the large electron-positron collider at CERN, Geneva, can have the same kinetic energy as a slug on a lettuce leaf.

Another thing which can be expressed in many different ways is information. For example, the two statements "the quantum computer is very interesting" and "l'ordinateur quantique est tres interessant" have something in common, although they share no words. The thing they have in common is their information content. Essentially the same information could be expressed in many other ways, for example by substituting numbers for letters in a scheme such as a → 97, b → 98, c → 99 and so on, in which case the English version of the above statement becomes 116 104 101 32 113 117 97 110 116 117 109... . It is very significant that information can be expressed in different ways without losing its essential nature, since this leads to the possibility of the automatic manipulation of information: a machine need only be able to manipulate quite simple things like integers in order to do surprisingly powerful information processing, from document preparation to differential calculus, even to translating between human languages. We are familiar with this now, because of the ubiquitous computer, but even fifty years ago such a widespread significance of automated information processing was not foreseen.

However, there is one thing that all ways of expressing information must have in common: they all use real physical things to do the job. Spoken words are conveyed by air pressure fluctuations, written ones by arrangements of ink molecules on paper, even thoughts depend on neurons (Landauer 1991). The rallying cry of the information physicist is "no information without physical representation!" Conversely, the fact that information is insensitive to exactly how it is expressed, and can be freely translated from one form to another, makes it an obvious candidate for a fundamentally important role in physics, like energy and momentum and other such abstractions. However, until the second half of this century, the precise mathematical treatment of information, especially information processing, was undiscovered, so the significance of information in physics was only hinted at in concepts such as entropy in thermodynamics. It now appears that information may have a much deeper significance. Historically, much of fundamental physics has been concerned with discovering the fundamental particles of nature and the equations which describe their motions and interactions. It now appears that a different programme may be equally important: to discover the ways that nature allows, and prevents, information to be expressed and manipulated, rather than particles to move. For example, the best way to state exactly what can and cannot travel faster than light is to identify information as the speed-limited entity. In quantum mechanics, it is highly significant that the state vector must not contain, whether explicitly or implicitly, more information than can meaningfully be associated with a given system. Among other things this produces the wavefunction symmetry requirements which lead to Bose Einstein and Fermi Dirac statistics, the periodic structure of atoms, and so on.

The programme to re-investigate the fundamental principles of physics from the standpoint of information theory is still in its infancy. However, it already appears to be highly fruitful, and it is this ambitious programme that I aim to summarise.

Historically, the concept of information in physics does not have a clear-cut origin. An important thread can be traced if we consider the paradox of Maxwell's demon of 1871 (Fig. 1) (see also Brillouin 1956). Recall that Maxwell's demon is a creature that opens and closes a trap door between two compartments of a chamber containing gas, and pursues the subversive policy of only opening the door when fast molecules approach it from the right, or slow ones from the left. In this way the demon establishes a temperature difference between the two compartments without doing any work, in violation of the second law of thermodynamics, and consequently permitting a host of contradictions.

Fig. 1. Maxwell's demon. In this illustration the demon sets up a pressure difference by only raising the partition when more gas molecules approach it from the left than from the right. This can be done in a completely reversible manner, as long as the demon's memory stores the random results of its observations of the molecules. The demon's memory thus gets hotter. The irreversible step is not the acquisition of information, but the loss of information if the demon later clears its memory.

A number of attempts were made to exorcise Maxwell's demon (see Bennett 1987), such as arguments that the demon cannot gather information without doing work, or without disturbing (and thus heating) the gas, both of which are untrue. Some were tempted to propose that the 2nd law of thermodynamics could indeed be violated by the actions of an "intelligent being." It was not until 1929 that Leo Szilard made progress by reducing the problem to its essential components, in which the demon need merely identify whether a single molecule is to the right or left of a sliding partition, and its action allows a simple heat engine, called Szilard's engine, to be run. Szilard still had not solved the problem, since his analysis was unclear about whether or not the act of measurement, whereby the demon learns whether the molecule is to the left or the right, must involve an increase in entropy.

A definitive and clear answer was not forthcoming, surprisingly, until a further fifty years had passed. In the intermediate years digital computers were developed, and the physical implications of information gathering and processing were carefully considered. The thermodynamic costs of elementary information manipulations were analysed by Landauer and others during the 1960s (Landauer 1961, Keyes and Landauer 1970), and those of general computations by Bennett, Fredkin, Toffoli and others during the 1970s (Bennett 1973, Toffoli 1980, Fredkin and Toffoli 1982). It was found that almost anything can in principle be done in a reversible manner, i.e. with no entropy cost at all (Bennett and Landauer 1985). Bennett (1982) made explicit the relation between this work and Maxwell's paradox by proposing that the demon can indeed learn where the molecule is in Szilard's engine without doing any work or increasing any entropy in the environment, and so obtain useful work during one stroke of the engine. However, the information about the molecule's location must then be present in the demon's memory (Fig. 1). As more and more strokes are performed, more and more information gathers in the demon's memory. To complete a thermodynamic cycle, the demon must erase its memory, and it is during this erasure operation that we identify an increase in entropy in the environment, as required by the 2nd law. This completes the essential physics of Maxwell's demon; further subtleties are discussed by Zurek (1989), Caves (1990), and Caves, Unruh and Zurek (1990).

The thread we just followed was instructive, but to provide a complete history of ideas relevant to quantum computing is a formidable task. Our subject brings together what are arguably two of the greatest revolutions in twentieth-century science, namely quantum mechanics and information science (including computer science). The relationship between these two giants is illustrated in Figure 2.

Fig. 2. Relationship between quantum mechanics and information theory. This diagram is not intended to be a definitive statement, the placing of entries being to some extent subjective, but it indicates many of the connections discussed in the article.

Classical information theory is founded on the definition of information. A warning is in order here. Whereas the theory tries to capture much of the normal meaning of the term 'information', it can no more do justice to the full richness of that term in everyday language than particle physics can encapsulate the everyday meaning of 'charm'. 'Information' for us will be an abstract term. Much of information theory dates back to seminal work of Shannon in the 1940's (Slepian 1974). The observation that information can be translated from one form to another is encapsulated and quantified in Shannon's noiseless coding theorem (1948), which quantifies the resources needed to store or transmit a given body of information. Shannon also considered the fundamentally important problem of communication in the presence of noise, and established Shannon's main theorem which is the central result of classical information theory. Error-free communication even in the presence of noise is achieved by means of 'error-correcting codes', and their study is a branch of mathematics in its own right. Indeed, the journal IEEE Transactions on Information Theory is almost totally taken up with the discovery and analysis of error-correction by coding. Pioneering work in this area was done by Golay (1949) and Hamming (1950).

The foundations of computer science were formulated at roughly the same time as Shannon's information theory, and this is no coincidence. The father of computer science is arguably Alan Turing (1912-1954), and its prophet is Charles Babbage (1791-1871). Babbage conceived of most of the essential elements of a modern computer, though in his day there was not the technology available to implement his ideas. A century passed before Babbage's Analytical Engine was improved upon when Turing described the Universal Turing Machine in the mid 1930s. Turing's genius (see Hodges 1983) was to clarify exactly what a calculating machine might be capable of, and to emphasise the role of programming, i.e. software, even more than Babbage had done. The giants on whose shoulders Turing stood in order to get a better view were chiefly the mathematicians David Hilbert and Kurt Gödel. Hilbert had emphasised between the 1890s and 1930s the importance of asking fundamental questions about the nature of mathematics. Instead of asking "is this mathematical proposition true?" Hilbert wanted to ask "is it the case that every mathematical proposition can in principle be proved or disproved?" This was unknown, but Hilbert's feeling, and that of most mathematicians, was that mathematics was indeed complete, so that conjectures such as Goldbach's (that every even number can be written as the sum of two primes) could be proved or disproved somehow, although the logical steps might be as yet undiscovered.

Gödel destroyed this hope by establishing the existence of mathematical propositions which were undecidable, meaning that they could be neither proved nor disproved. The next interesting question was whether it would be easy to identify such propositions. Progress in mathematics had always relied on the use of creative imagination, yet with hindsight mathematical proofs appear to be automatic, each step following inevitably from the one before. Hilbert asked whether this 'inevitable' quality could be captured by a 'mechanical' process. In other words, was there a universal mathematical method, which would establish the truth or otherwise of every mathematical assertion? After Gödel, Hilbert's problem was re-phrased into that of establishing decidability rather than truth, and this is what Turing sought to address.

In the words of Newman, Turing's bold innovation was to introduce 'paper tape' into symbolic logic. In the search for an automatic process by which mathematical questions could be decided, Turing envisaged a thoroughly mechanical device, in fact a kind of glorified typewriter (Fig. 3). The importance of the Turing machine (Turing 1936) arises from the fact that it is sufficiently complicated to address highly sophisticated mathematical questions, but sufficiently simple to be subject to detailed analysis. Turing used his machine as a theoretical construct to show that the assumed existence of a mechanical means to establish decidability leads to a contradiction. In other words, he was initially concerned with quite abstract mathematics rather than practical computation. However, by seriously establishing the idea of automating abstract mathematical proofs rather than merely arithmetic, Turing greatly stimulated the development of general purpose information processing. This was in the days when a "computer" was a person doing mathematics.

Fig. 3. The Turing Machine. This is a conceptual mechanical device which can be shown to be capable of efficiently simulating all classical computational methods. The machine has a finite set of internal states, and a fixed design. It reads one binary symbol at a time, supplied on a tape. The machine's action on reading a given symbol s depends only on that symbol and the internal state G. The action consists in overwriting a new symbol s' on the current tape location, changing state to G', and moving the tape one place in direction d (left or right). The internal construction of the machine can therefore be specified by a finite fixed list of rules of the form (s,G → s', G', d). One special internal state is the 'halt' state: once in this state the machine ceases further activity. An input 'programme' on the tape is transformed by the machine into an output result printed on the tape.

Modern computers are neither Turing machines nor Babbage engines, though they are based on broadly similar principles, and their computational power is equivalent (in a technical sense) to that of a Turing machine. I will not trace their development here, since although this is a wonderful story, it would take too long to do justice to the many people involved. Let us just remark that all of this development represents a great improvement in speed and size, but does not involve any change in the essential idea of what a computer is, or how it operates. Quantum mechanics raises the possibility of such a change, however.

Quantum mechanics is the mathematical structure which embraces, in principle, the whole of physics. We will not be directly concerned with gravity, high velocities, or exotic elementary particles, so the standard non-relativistic quantum mechanics will suffice. The significant feature of quantum theory for our purpose is not the precise details of the equations of motion, but the fact that they treat quantum amplitudes, or state vectors in a Hilbert space, rather than classical variables. It is this that allows new types of information and computing.

There is a parallel between Hilbert's questions about mathematics and the questions we seek to pose in quantum information theory. Before Hilbert, almost all mathematical work had been concerned with establishing or refuting particular hypotheses, but Hilbert wanted to ask what general type of hypothesis was even amenable to mathematical proof. Similarly, most research in quantum physics has been concerned with studying the evolution of specific physical systems, but we want to ask what general type of evolution is even conceivable under quantum mechanical rules.

The first deep insight into quantum information theory came with Bell's 1964 analysis of the paradoxical thought-experiment proposed by Einstein, Podolsky and Rosen (EPR) in 1935. Bell's inequality draws attention to the importance of correlations between separated quantum systems which have interacted (directly or indirectly) in the past, but which no longer influence one another. In essence his argument shows that the degree of correlation which can be present in such systems exceeds that which could be predicted on the basis of any law of physics which describes particles in terms of classical variables rather than quantum states. Bell's argument was clarified by Bohm (1951, also Bohm and Aharonov 1957) and by Clauser, Holt, Horne and Shimony (1969), and experimental tests were carried out in the 1970s (see Clauser and Shimony (1978) and references therein). Improvements in such experiments are largely concerned with preventing the possibility of any interaction between the separated quantum systems, and a significant step forward was made in the experiment of Aspect, Dalibard and Roger (1982), (see also Aspect 1991) since in their work any purported interaction would have either to travel faster than light, or possess other almost equally implausible qualities.

The next link between quantum mechanics and information theory came about when it was realised that simple properties of quantum systems, such as the unavoidable disturbance involved in measurement, could be put to practical use, in quantum cryptography (Wiesner 1983, Bennett et al. 1982, Bennett and Brassard 1984; for a recent review see Brassard and Crepeau 1996). Quantum cryptography covers several ideas, of which the most firmly established is quantum key distribution. This is an ingenious method in which transmitted quantum states are used to perform a very particular communication task: to establish at two separated locations a pair of identical, but otherwise random, sequences of binary digits, without allowing any third party to learn the sequence. This is very useful because such a random sequence can be used as a cryptographic key to permit secure communication. The significant feature is that the principles of quantum mechanics guarantee a type of conservation of quantum information, so that if the necessary quantum information arrives at the parties wishing to establish a random key, they can be sure it has not gone elsewhere, such as to a spy. Thus the whole problem of compromised keys, which fills the annals of espionage, is avoided by taking advantage of the structure of the natural world.

While quantum cryptography was being analysed and demonstrated, the quantum computer was undergoing a quiet birth. Since quantum mechanics underlies the behaviour of all systems, including those we call classical ("even a screwdriver is quantum mechanical", Landauer (1995)), it was not obvious how to conceive of a distinctively quantum mechanical computer, i.e. one which did not merely reproduce the action of a classical Turing machine. Obviously it is not sufficient merely to identify a quantum mechanical system whose evolution could be interpreted as a computation; one must prove a much stronger result than this. Conversely, we know that classical computers can simulate, by their computations, the evolution of any quantum system... with one reservation: no classical process will allow one to prepare separated systems whose correlations break the Bell inequality. It appears from this that the EPR-Bell correlations are the quintessential quantum-mechanical property (Feynman 1982).

In order to think about computation from a quantum-mechanical point of view, the first ideas involved converting the action of a Turing machine into an equivalent reversible process, and then inventing a Hamiltonian which would cause a quantum system to evolve in a way which mimicked a reversible Turing machine. This depended on the work of Bennett (1973; see also Lecerf 1963) who had shown that a universal classical computing machine (such as Turing's) could be made reversible while retaining its simplicity. Benioff (1980, 1982) and others proposed such Turing-like Hamiltonians in the early 1980s. Although Benioff's ideas did not allow the full analysis of quantum computation, they showed that unitary quantum evolution is at least as powerful computationally as a classical computer.

A different approach was taken by Feynman (1982, 1986) who considered the possibility not of universal computation, but of universal simulation -- i.e. a purpose-built quantum system which could simulate the physical behaviour of any other. Clearly, such a simulator would be a universal computer too, since any computer must be a physical system. Feynman gave arguments which suggested that quantum evolution could be used to compute certain problems more efficiently than any classical computer, but his device was not sufficiently specified to be called a computer, since he assumed that any interaction between adjacent two-state systems could be 'ordered', without saying how.

In 1985 an important step forward was taken by Deutsch. Deutsch's proposal is widely considered to represent the first blueprint for a quantum computer, in that it is sufficiently specific and simple to allow real machines to be contemplated, but sufficiently versatile to be a universal quantum simulator, though both points are debatable. Deutsch's system is essentially a line of two-state systems, and looks more like a register machine than a Turing machine (both are universal classical computing machines). Deutsch proved that if the two-state systems could be made to evolve by means of a specific small set of simple operations, then any unitary evolution could be produced, and therefore the evolution could be made to simulate that of any physical system. He also discussed how to produce Turing-like behaviour using the same ideas.

Deutsch's simple operations are now called quantum 'gates', since they play a role analogous to that of binary logic gates in classical computers. Various authors have investigated the minimal class of gates which are sufficient for quantum computation.

The two questionable aspects of Deutsch's proposal are its efficiency and realisability. The question of efficiency is absolutely fundamental in computer science, and on it the concept of 'universality' turns. A universal computer is one that not only can reproduce (i.e. simulate) the action of any other, but can do so without running too slowly. The 'too slowly' here is defined in terms of the number of computational steps required: this number must not increase exponentially with the size of the input. Deutsch's simulator is not universal in this strict sense, though it was shown to be efficient for simulating a wide class of quantum systems by Lloyd (1996). However, Deutsch's work has established the concepts of quantum networks (Deutsch 1989) and quantum logic gates, which are extremely important in that they allow us to think clearly about quantum computation.

In the early 1990's several authors (Deutsch and Jozsa 1992, Berthiaume and Brassard 1992, Bernstein and Vazirani 1993) sought computational tasks which could be solved by a quantum computer more efficiently than any classical computer. Such a quantum algorithm would play a conceptual role similar to that of Bell's inequality, in defining something of the essential nature of quantum mechanics. Initially only very small differences in performance were found, in which quantum mechanics permitted an answer to be found with certainty, as long as the quantum system was noise-free, where a probabilistic classical computer could achieve an answer 'only' with high probability. An important advance was made by Simon (1994), who described an efficient quantum algorithm for a (somewhat abstract) problem for which no efficient solution was possible classically, even by probabilistic methods. This inspired Shor (1994) who astonished the community by describing an algorithm which was not only efficient on a quantum computer, but also addressed a central problem in computer science: that of factorising large integers.

Shor discussed both factorisation and discrete logarithms, making use of a quantum Fourier transform method discovered by Coppersmith (1994) and Deutsch. Further important quantum algorithms were discovered by Grover (1997) and Kitaev (1995).

Just as with classical computation and information theory, once theoretical ideas about computation had got under way, an effort was made to establish the essential nature of quantum information -- the task analogous to Shannon's work. The difficulty here can be seen by considering the simplest quantum system, a two-state system such as a spin half in a magnetic field. The quantum state of a spin is a continuous quantity defined by two real numbers, so in principle it can store an infinite amount of classical information. However, a measurement of a spin will only provide a single two-valued answer (spin up/spin down) -- there is no way to gain access to the infinite information which appears to be there, therefore it is incorrect to consider the information content in those terms. This is reminiscent of the renormalisation problem in quantum electrodynamics. How much information can a two-state quantum system store, then? The answer, provided by Jozsa and Schumacher (1994) and Schumacher (1995), is one two-state system's worth! Of course Schumacher and Jozsa did more than propose this simple answer, rather they showed that the two-state system plays the role in quantum information theory analogous to that of the bit in classical information theory, in that the quantum information content of any quantum system can be meaningfully measured as the minimum number of two-state systems, now called quantum bits or qubits, which would be needed to store or transmit the system's state with high accuracy.

Let us return to the question of realisability of quantum computation. It is an elementary, but fundamentally important, observation that the quantum interference effects which permit algorithms such as Shor's are extremely fragile: the quantum computer is ultra-sensitive to experimental noise and impression. It is not true that early workers were unaware of this difficulty, rather their first aim was to establish whether a quantum computer had any fundamental significance at all. Armed with Shor's algorithm, it now appears that such a fundamental significance is established, by the following argument: either nature does allow a device to be run with sufficient precision to perform Shor's algorithm for large integers (greater than, say, a googol which is 1 followed by 100 zeroes) or there are fundamental natural limits to precision in real systems. Both eventualities represent an important insight into the laws of nature.

At this point, ideas of quantum information and quantum computing come together. For, a quantum computer can be made much less sensitive to noise by means of a new idea which comes directly from the marriage of quantum mechanics with classical information theory, namely quantum error correction. Although the phrase 'error correction' is a natural one and was used with reference to quantum computers prior to 1996, it was only in that year that two important papers, of Calderbank and Shor, and independently Steane, established a general framework whereby quantum information processing can be used to combat a very wide class of noise processes in a properly designed quantum system. Much progress has since been made in generalising these ideas (Knill and Laflamme 1997, Ekert and Macchiavello 1996, Bennett et al. 1996b, Gottesman 1996, Calderbank et al. 1997). An important development was the demonstration by Shor (1996) and Kitaev (1996) that correction can be achieved even when the corrective operations are themselves imperfect. Such methods lead to a general concept of 'fault tolerant' computing, of which a helpful review is provided by Preskill (1997).

If, as seems almost certain, quantum computation will only work in conjunction with quantum error correction, it appears that the relationship between quantum information theory and quantum computers is even more intimate than that between Shannon's information theory and classical computers. Error correction does not in itself guarantee accurate quantum computation, since it cannot combat all types of noise, but the fact that it is possible at all is a significant development.

A computer which only exists on paper will not actually perform any computations, and in the end the only way to resolve the issue of feasibility in quantum computer science is to build a quantum computer. To this end, a number of authors proposed computer designs based on Deutsch's idea, but with the physical details more fully worked out (Teich et al. 1988, Lloyd 1993, Berman et al. 1994, DiVincenco 1995b). The great challenge is to find a sufficiently complex system whose evolution is nevertheless both coherent (i.e. unitary) and controllable. It is not sufficient that only some aspects of a system should be quantum mechanical, as in solid-state 'quantum dots', or that there is an implicit assumption of unfeasible precision or cooling, which is often the case for proposals using solid-state devices. Cirac and Zoller (1995) proposed the use of a linear ion trap, which was a significant improvement in feasibility, since heroic efforts in the ion trapping community had already achieved the necessary precision and low temperature in experimental work, especially the group of Wineland who demonstrated cooling to the ground state of an ion trap in the same year (Diedrich et al. 1989, Monroe et al. 1995). More recently, Gershenfeld and Chuang (1997) and Cory et al. (1996,1997) have shown that nuclear magnetic resonance (NMR) techniques can be adapted to fulfill the requirements of quantum computation, making this approach also very promising. Other recent proposals of Privman et al. (1997) and Loss and DiVincenzo (1997) may also be feasible.

As things stand, no quantum computer has been built, nor looks likely to be built in the author's lifetime, if we measure it in terms of Shor's algorithm, and ask for factoring of large numbers. However, if we ask instead for a device in which quantum information ideas can be explored, then only a few quantum bits are required, and this will certainly be achieved in the near future. Simple two-bit operations have been carried out in many physics experiments, notably magnetic resonance, and work with three to ten qubits now seems feasible. Notable recent experiments in this regard are those of Brune et al. (1994), Monroe et al. (1995b), Turchette et al. (1995) and Mattle et al. (1996).

A. M. Steane, summer 1997