by David Deutsch and Artur Ekert

Many milestones in the history of technology have involved the discovery of new ways of harnessing nature --- exploiting various physical resources such as materials, forces, and sources of energy. In the twentieth century information was added to this list when the invention of computers allowed complex information processing to be performed outside human brains. The history of computer technology has itself involved a sequence of changes from one type of physical realisation to another --- from gears to relays to valves to transistors, integrated circuits and so on. Today’s advanced lithographic techniques can etch logic gates and wires less than a micron across onto the surfaces of silicon chips. Soon they will yield even smaller components, until we reach the point where logic gates are so small that they consist of only a few atoms each.

On the scale of human perception and above, classical (non-quantum) laws of physics are good phenomenological approximations, but on the atomic scale the laws of quantum mechanics become dominant, and they have quite a different character. If computers are to continue to become faster (and therefore smaller), new, quantum technology must replace or supplement what we have now, but it turns out that such technology can offer much more than smaller and faster microprocessors. It can support entirely new modes of computation, with new quantum algorithms that do not have classical analogues.

The potential power of quantum phenomena to perform computations was first adumbrated in a talk given by Richard Feynman at the First Conference on the Physics of Computation held at MIT in 1981. He observed that it appeared to be impossible in general to simulate a evolution of a quantum system on a classical computer in an efficient way. The computer simulation of quantum evolution typically involves an exponential slowdown in time, compared with the natural evolution, essentially because the amount of classical information required to describe the evolving quantum state is exponentially larger than that required to describe the corresponding classical system with a similar accuracy. However, instead of viewing this intractability as an obstacle, Feynman regarded it as an opportunity. He pointed out that if it requires that much computation to work out what will happen in a multi-particle interference experiment, then the very act of setting up such an experiment and measuring the outcome is equivalent to performing a complex computation.

The foundations of the quantum theory of computation were laid down in 1985 when David Deutsch of the University of Oxford published a crucial theoretical paper in which he described a universal quantum computer. Since then, the hunt has been on for interesting things for quantum computers to do, and at the same time, for the scientific and technological advances that could allow us to build quantum computers.

What makes quantum computers so different from their classical counterparts? Let us take a closer look at the basic unit of information: the bit. From a physical point of view a bit is a two-state system: it can be prepared in one of two distinguishable states representing two logical values --- no or yes, false or true, or simply 0 or 1. For example, in digital computers, the voltage between the plates of a capacitor can represent a bit of information: a charge on the capacitor denotes 1 and the absence of charge denotes 0. One bit of information can be also encoded using, for instance, two different polarisations of light or two different electronic states of an atom. Now, quantum mechanics tells us that if a bit can exist in either of two distinguishable states, it can also exist in coherent superpositions of them. These are further states, which in general have no classical analogues, in which the atom represents both values, 0 and 1, simultaneously. To get used to the idea that a physical quantity can have two values at once, it is helpful to consider the experiment in Fig. A.

A half—silvered mirror is one that reflects half the light that impinges upon it, while allowing the remaining half to pass through unaffected. Let us aim a single photon at such a mirror, as in Fig.A. What happens? One thing we know is that the photon doesn’t split in two: we can place photodetectors wherever we like in the apparatus, fire in a photon, and verify that if any of the photodetectors registers a hit, none of the others do. In particular, if we place a photodetector behind the mirror in each of the two possible exit beams, the photon is detected with equal probability at either detector. So does the photon leave the first mirror in one of the two possible directions, at random? It does not! It may seem obvious that at the very least, the photon is either in the transmitted beam or in the reflected beam during any one run of this experiment. But that is not so either. In fact the photon takes both paths at once, as can be demonstrated with the help of the apparatus shown in Fig. B.

Two normal mirrors are placed as so that both paths intersect at a second half—silvered mirror. With this setup we can observe the astonishing, purely quantum phenomenon of single-particle interference. Suppose that a particular photon was reflected after striking the first half—silvered mirror and followed the corresponding path to the second half—silvered mirror. Then (by comparison with Fig. A.) we should find that the two detectors registered hits with equal probability. Exactly the same would be observed if the photon were transmitted after striking the first half—silvered mirror and followed the other path. Hence if it were really the case that the photon takes exactly one path through the apparatus --- no matter which one --- detectors 1 and 2 would on average each fire on half the occasions when the experiment is performed. However, that is not what happens. It turns out that in the arrangement shown, the photon always strikes detector 2 and never detector 1.

It seems inescapable that the photon must, in some sense, have actually travelled both routes at once for if an absorbing screen is placed in the way of either of the two routes, then it becomes equally probable that detector 1 or 2 is reached (Fig. C). Blocking off one of the paths actually allows detector 1 to be reached; with both routes open, the photon somehow knows that it is not permitted to reach detector 1, so it must have actually felt out both routes. It is therefore perfectly legitimate to say that between the two half-silvered mirrors the photon took both the transmitted and the reflected paths or, using more technical language, we can say that the photon is in a coherent superposition of being in the transmitted beam and in the reflected beam.

By the same token an atom can be prepared in a superposition of two different electronic states, and in general a quantum two state system, called a quantum bit or a qubit, can be prepared in a superposition of its two logical states 0 and 1. That is the sense in which a qubit can store both 0 and 1 simultaneously, in arbitrary proportions. But note that just as the photon, if measured, will be detected on only one of the two paths, so if the qubit is measured, only one of the two numbers it holds will be detected, at random: not a very useful property in itself.

But now let us push the idea of superpositions of numbers a little further. Consider a register composed of three physical bits. A classical 3-bit register can store exactly one of eight different numbers i.e the register can be in one of the eight possible configurations 000, 001, 010, ..., 111, representing the numbers 0 to 7. But a quantum register composed of three qubits can simultaneously store up to eight numbers in a quantum superposition. It is quite remarkable that eight different numbers can be physically present in the same register; but it should be no more surprising than the numbers 0 and 1 both being present in the same qubit. If we add more qubits to the register its capacity for storing quantum information increases exponentially: four qubits can store 16 different numbers at once, and in general L qubits can store up to 2^L numbers at once. A 250-qubit register --- essentially made of 250 atoms, say --- would be capable of holding more numbers simultaneously than there are atoms in the known universe. Even so, if we measure the register’s contents, we will see only one of those numbers. However, now we can start doing some non-trivial quantum computation, for once the register is prepared in a superposition of many different numbers, we can perform mathematical operations on all of them at once. For example, if the qubits are atoms then suitably tuned laser pulses affect their electronic states and evolve initial superpositions of encoded numbers into different superpositions. During such an evolution each number in the superposition is affected, so we are performing a massive parallel computation. Thus a quantum computer can in a single computational step perform the same mathematical operation on, say, 2^L different input numbers, and the result will be a superposition of all the corresponding outputs. In order to accomplish the same task any classical computer has to repeat the computation 2^L times, or has to use 2L different processors working in parallel. In this way a quantum computer offers an enormous gain in the use of computational resources such as time and memory --- though only in certain types of computation.

What types? As we have said, ordinary information storage is not one of them, for although the computer now holds all the outcomes of 2^L computations, the laws of physics only allow us to see one of them. However, just as the single answer in the experiment of Fig. B depends on information that travelled along each of two paths, quantum interference now allows us to obtain a single, final result that depends logically on all 2^L of the intermediate results.

Grover's search

This is how a remarkable quantum algorithm discovered by Lov Grover of AT&T’s Bell Laboratories in New Jersey achieves the mind-boggling feat of searching an unsorted list of N items in only the square root of N or so steps. Consider, for example, searching for a specific telephone number in a directory containing a million entries, stored in the computer’s memory in alphabetical order of names. It is easily proved (and obvious) that no classical algorithm can improve on the brute-force method of simply scanning the entries one by one until the given number is found, which will, on average, require 500,000 memory accesses. A quantum computer can examine all the entries simultaneously, in the time of a single access. However, if it is merely programmed to print out the result at that point, there is no improvement over the classical algorithm: only one of the million computational paths would have checked the entry we are looking for, so there would be a probability of only one in a million that we would obtain that information if we measured the computer’s state. But if we leave that quantum information in the computer, unmeasured, a further quantum operation can cause that information to affect other paths, just as in the simple interference experiment described above. In this way the information about the desired entry is spread, through quantum interference, to more paths. It turns out that if this interference generating operation is repeated about 1000 times, (in general, the square root of N times) the information about which entry contains the desired number will be accessible to measurement with probability 0.5. Therefore repeating the entire algorithm a few more times will find the desired entry with a probability overwhelmingly close to 1. In addition to finding the entry with a given property, variations on Grover’s algorithm can also find the largest or smallest value in a list, or the modal value, and so on, so it is a very versatile searching tool.

Shor's factoring

The difference in performance between the quantum and classical algorithms can be even more spectacular. This is the case of the quantum factoring algorithm, discovered in 1994 by Peter Shor, also of AT&T’s Bell Laboratories in New Jersey.

Mathematicians believe (firmly, though they have not actually proved it) that in order to factorise a number with N decimal digits, any classical computer needs a number of steps that grows exponentially with N: that is to say, adding one extra digit to the number to be factorised generally multiplies the time required by a fixed factor. Thus, as we increase the number of digits, the task rapidly becomes intractable. No one can even conceive of how one might factorise, say, thousand-digit numbers by classical means; the computation would take many times as long the estimated age of the universe. In contrast, quantum computers could factor thousand-digit numbers in a fraction of a second --- and the execution time would grow only as the cube of the number of digits. You can find more information on the mathematics behind Shor's algorithm here.

Now, the intractability of factorisation underpins the security of what are currently the most trusted methods of encryption, in particular of the RSA (Rivest, Shamir and Adelman) system, which is often used to protect electronic bank accounts. Once a quantum factorisation engine (a special-purpose quantum computer for factorising large numbers) is built, all such cryptographic systems will become insecure. Indeed, in one sense they are already insecure: any RSA-encrypted message that is recorded today will become readable moments after the first quantum factorisation engine is switched on, and therefore RSA cannot be used for securely transmitting any information that will still need to be secret on that happy day.

Admittedly, that day is probably decades away, but can anyone prove, or give any reliable assurance, that it is? Confidence in the slowness of technological progress is all that the security of the RSA system now rests on. What quantum computation takes away with one hand, it returns, at least partially, with the other. Quantum cryptography provides perfect security because unlike all classical cryptography it relies on the laws of physics rather than on ensuring that successful eavesdropping would require excessive computational effort.

Potential use of quantum computation for code-breaking purposes has raised an obvious question --- what about building a quantum computer?

In principle we know how to build a quantum computer; we start with simple quantum logic gates and connect them up into quantum networks (circuits). A quantum logic gate, like a classical gate, is a very simple computing device that performs one elementary quantum operation, usually on one or two qubits, in a given time (cf. gates). Of course, quantum logic gates differ from their classical counterparts in that they can create, and perform operations, on quantum superpositions.

However as the number of quantum gates in a network increases, we quickly run into some serious practical problems. The more interacting qubits are involved, the harder it tends to be to engineer the interaction that would display the quantum interference. Apart from the technical difficulties of working at single-atom and single-photon scales, one of the most important problems is that of preventing the surrounding environment from being affected by the interactions that generate quantum superpositions. The more components there are, the more likely it is that quantum information will spread outside the quantum computer and be lost into the environment, thus spoiling the computation. This process is called decoherence. Thus our task is to engineer sub-microscopic systems in which qubits affect each other but not the environment. In order to achieve this we will have to use stabilizing techniques known as quantum error correction and fault tolerant computation.

We know how to handle errors due to decoherence provided that they satisfy some assumptions, e.g. that errors occur independently on each of the qubits, that the performance of gate operations on some qubits do not cause decoherence in other qubits, that reliable quantum measurements can be made so that error detection can take place, and that systematic errors in the operations associated with quantum gates can be made very small. If all these assumptions are satisfied, then the fault-tolerant quantum computation is possible. That is, efficient, reliable quantum-coherent quantum computation of arbitrarily long duration is possible, even with faulty and decohering components. Thus, errors can be corrected faster than they occur, even if the error correction machinery is faulty.

So, many experimentalists do not give up. The current challenge is not to build a full quantum computer right away but rather to move from the experiments in which we merely observe quantum phenomena to experiments in which we can control these phenomena. This is a first step towards quantum logic gates and simple quantum networks. But can we then control nature at the level of single photons and atoms? Yes, to some degree we can! You will find more information about experiments with photons and atoms on our research pages.

When the physics of computation was first investigated systematically in the 1970s, the main fear was that quantum-mechanical effects might place fundamental bounds on the accuracy with which physical objects could realise the properties of bits, logic gates, the composition of operations, and so on, which appear in the abstract and mathematicallysophisticated theory of computation. Thus it was feared that the power and elegance of that theory, its deep concepts such as computational universality, its deep results such as Turing’s halting theorem, and the more modern theory of complexity, might all be mere figments of pure mathematics, not really relevant to anything in nature.

Those fears have not only been proved groundless by the research we have been describing, but also, in each case, the underlying aspiration has been wonderfully vindicated to an extent that no one even dreamed of just twenty years ago. As we have explained, quantum mechanics, far from placing limits on what classical computations can be performed in nature, permits them all, and in addition provides whole new modes of computation, including algorithms that perform tasks that no classical computer can perform at all. As far as the elegance of the theory goes, researchers in the field have now become accustomed to the fact that the real theory of computation hangs together better, and fits in far more naturally with fundamental theories in other fields, than its classical approximation could ever have been expected to. Even at the simplest level, the very word ‘quantum’ means the same as the word ‘bit’ --- an elementary chunk --- and this reflects the fact that fully classical physical systems, being subject to the generic instability known as ‘chaos’, would not support digital computation at all (so even Turing machines, the theoretical prototype of all classical computers, were secretly quantum-mechanical all along!). The Church-Turing hypothesis in the classical theory (that all ‘natural’ models of computation are essentially equivalent to each other), was never proved. Its analogue in the quantum theory of computation (the Turing Principle, that the universal quantum computer can simulate the behaviour of any finite physical system) was straightforwardly proved in Deutsch’s 1985 paper. A stronger result (also conjectured but never proved in the classical case), namely that such simulations can always be performed in a time that is at most a polynomial function of the time taken for the physical evolution, has since been proved in the quantum case.

Experimental and theoretical research in quantum computation is accelerating world-wide. New technologies for realising quantum computers are being proposed, and new types of quantum computation with various advantages over classical computation are continually being discovered and analysed and we believe some of them will bear technological fruit. From a fundamental standpoint, however, it does not matter how useful quantum computation turns out to be, nor does it matter whether we build the first quantum computer tomorrow, next year or centuries from now. The quantum theory of computation must in any case be an integral part of the world view of anyone who seeks a fundamental understanding of the quantum theory and the processing of information.