The world is currently witnessing a major cross pollination of ideas between two mainstays of scientific knowledge: quantum mechanics and theoretical computer science. The resulting synthesis, the theory of quantum information, is fueling a revolution that promises to take us from the “information age” we currently live in to the “quantum information age”. At the heart of this revolution is the replacement of approximate “classical” laws of physics with the more accurate and powerful quantum laws as the foundation upon which information processing devices (like computers) are built. The classical laws trace their roots back to Newton and Galileo, but at the turn of the 20th century these were superseded by quantum laws, necessary to describe nature at the more fundamental level of atoms and subatomic particles. There is good evidence that using these quantum laws will produce devices with a power and capability unimaginable with today's technology. On the horizon are quantum computers that will be able to perform computations we believe no classical computer would ever be capable of, absolutely secure quantum communication—impervious to eavesdropping, and other fascinating potential technologies. Indeed, many of the basic theoretical principles behind these incipient technologies have already been successfully tested in physics laboratories around the world. Furthermore, the development of the theory of quantum information may significantly deepen our understanding of the very fabric of reality—the fundamental nature of the quantum universe we live in and this is of primary importance at Perimeter Institute.

Why is this revolution happening now?

There are two main factors at work:

1. The Necessity of Quantum Mechanics
   
   We are all aware of the tremendous progress in information technology: each year engineers devise better computers with faster processors and more memory. In fact, this progress has been going on steadily for some time now: since the early 1960s, computer power has routinely doubled about every 18 months, a phenomenon known as Moore’s law. Doubling computer power means doubling the number of computing elements (in this case, transistors) that engineers can fit on a given-sized chip of silicon (or other semiconductor). This requires smaller and smaller transistors. If the current rate of miniaturization keeps up, by about the year 2020 transistors will have become the size of individual atoms. This poses a couple of serious challenges. Firstly, it is likely impossible to build a transistor or any other computing device smaller than this, which represents a roadblock to further progress in information technologies. Secondly, computing elements used today operate on laws of physics called “classical” laws. As indicated above, these laws are completely unable to explain or describe how nature works on very microscopic scales. Computing elements the size of atoms can only be understood using the language and ideas of quantum mechanics. Thus we will soon be forced to use quantum mechanics when thinking about and designing information processing devices. Not only will this enable miniaturization all the way down to the scale of individual atoms, but it is precisely this change in thinking that provides a way around the roadblock posed by not being able to miniaturize indefinitely.
   
   How so? Quantum mechanics is very different from classical mechanics. It is much richer in structure and also quite bizarre, even for “experts”. For instance, in the quantum world a single particle can be in many places at once! (Technically, a system, for example a single particle, can exist in many different states simultaneously, mathematically described as a “superposition state”). Moreover, two or more particles, even if they are separated by vast distances, can nevertheless act in some ways as a single entity—something Einstein called “spooky action at a distance” (and technically referred to as “entanglement”). We will return to superposition and entanglement below. The point here is that the greater richness of the quantum world allows us to invent computing elements of an entirely new kind that are more subtle and more powerful. Thus, rather than being a problem, the limit to miniaturization has instead opened our minds to a whole new world of fascinating possibilities.
   
2. The Superseding of Classical Information Theory
   
   Charles Babbage (1791-1871) is sometimes considered the “father of computing” for his conceptualization of an “analytical machine,” designed to perform mathematical computations. However, modern computer science proper was launched with ideas first put forward by the mathematician Alan Turing in 1936. Turing introduced the idea of what we now call a programmable computer, named the Universal Turing Machine in his honour. He postulated that if a machine could be designed to solve a problem, his Universal Turing Machine could also solve that problem, hence the adjective “universal”. This speculation is closely related to one made independently by the mathematician Alonzo Church, and is thus called the Church-Turing hypothesis. It has been fundamental to the development of computer science.
   
   It is important to understand that the Universal Turing Machine is not merely an abstract idea—it is a machine that can be physically realized using gears and electro-mechanical relays for example, or more modern technology such as an electronic circuit based on transistors. It is a physical device and thus subject to the laws of physics. It represents a model of computing rooted in the laws of nature, in this case the classical laws. In turn, the Church-Turing hypothesis is confined to the framework of a classical (non-quantum) understanding of the nature of the universe. In 1985 the theoretical physicist David Deutsch set out to create a model of computing based instead on the more powerful quantum laws of physics. He devised a quantum analogue of the Universal Turing Machine, called the Universal Quantum Computer, and argued in favour of the quantum analogue of the Church-Turing hypothesis (that the Universal Quantum Computer can simulate the behaviour of any finite physical system). This extremely important work marked the beginning of the “quantum revolution”. For the sake of completeness it should be mentioned that modern quantum mechanics was fully developed by the end of the 1920s. But since then our understanding of the laws of nature has grown still deeper through the development of quantum field theory (the successful marriage of quantum mechanics and Einstein’s theory of special relativity) and quantum gravity (a work still in progress, attempting to unify quantum mechanics and Einstein’s theory of general relativity, i.e. his theory of space, time and gravity). It is conceivable that models of computing based on these deeper theories—quantum field theory, quantum gravity, string theory and so forth—may be even more powerful than Deutsch’s model, but this is a subject for future research, and one of great interest to scientists at Perimeter Institute.

What is a Quantum Computer?

The really exciting idea implied in the previous discussion is that information and its processing are physical, and thus subject to the laws of physics, be those classical laws, quantum laws or something even deeper. This fact was first championed by Rolf Landauer. For example, in a classical (or ordinary) computer, information such as numbers, names and so forth is encoded as a string of “bits”. A single bit is the smallest unit of information and can assume one of two possible values: true or false, or yes or no, or one of the binary digits “0” or “1”. For instance, the numbers 0, 1, 2 and 3 might be represented by the two-bit strings: 00, 01, 10 and 11, respectively. Depending on the design of the computer, the two states 0 and 1 of an individual bit might be represented by two different values of voltage on a capacitor, or two different values of electric current flowing through a transistor, or the presence vs. absence of photons in an optical device; in any case, a bit must be represented in some physical way—it is not merely an abstract entity. Moreover, computing itself is a physical process that involves physical concepts such as energy and entropy. For instance, the (classical) computation 1 + 2 = 3 (equivalently, in terms of strings of bits, 01 + 10 = 11) actually requires energy and involves changes in entropy of the computer and its environment.

A quantum computer is much more subtle. Rather than using classical notions such as voltage on a capacitor or current through a transistor to represent bits, let us consider an electron. An electron is analogous to a tiny perpetually spinning top, whose rate of spin is a universal constant—the same for all electrons. The only thing that can change is the direction in which the spinning top is pointing. It turns out that, due to the peculiar quantum behaviour of the electron (remember: we are now in the very microscopic realm in which everything behaves quantum mechanically), any measurement of its spin always yields only one of two possible values: “spin up” or “spin down”, i.e. the spinning top is pointing up or down (relative to the measuring apparatus). So the electron is a two-state system—ideal for representing one bit of information. Let’s take the spin down state as representing the binary digit “0” and the spin up state as representing the binary digit “1”. Now here’s the really magical part: an electron can exist in the definite state 0 or 1 (like any classical two-state system), but it can also exist in other states: “quantum combinations” of the states 0 and 1, referred to earlier as superposition states, whereby the electron is in two states at once! The spin-state of an electron is one example of a quantum bit (or “qubit”—a term coined by Ben Schumacher). An arbitrarily large amount of information can be encoded in the state of a qubit, however nature only allows one bit of information to be extracted.

Now let’s suppose we put two qubits side-by-side. Rather than merely being able to represent the numbers 0, 1, 2, or 3 individually, the two qubits can be put in a superposition state that represents all four numbers simultaneously. A single quantum computation performed on such a superposition effectively does four separate computations simultaneously, once for each of the numbers 0, 1, 2, and 3. Now let’s increase the number of qubits. Three qubits can represent eight numbers (0 through 7, i.e. 000, 001, 010, 011, 100, 101, 110, 111), and one quantum computation performed on a three-qubit superposition-number is equivalent to eight classical computations done simultaneously; with four qubits one can achieve sixteen simultaneous computations; and so forth. Each additional qubit doubles the number of simultaneous classical computations the quantum computer is able to perform. Thus, because of the uniquely quantum phenomenon of superposition, a quantum computer is able to perform multiple calculations simultaneously, making a quantum computer capable of performing an exponential number of calculations in parallel. There is no known way (and very strong evidence convinces us no such way exists) for a classical computer to efficiently simulate a general quantum computation. The only general purpose way believed to exist for a classical computer to simulate a quantum computer is to perform a separate computation for each of the exponentially many computations that the quantum computer is doing in parallel. With even just 100 qubits, this kind of classical simulation is impossible.

The power of exponential quantum parallelism means that, once implemented, a quantum computer would be able to solve problems that we are convinced a classical computer would never, practically, be able to. Such tremendous computing power has potentially far-ranging practical applications. For example, suppose one wished to construct a fibre optic network that connected every major city in North America. There are many possible networks that could do this, each using a different amount of fibre optic cable. In fact the number of possible networks grows exponentially with the number of cities, so that finding the ideal network that uses the least total length of cable (and hence the most cost effective one) quickly becomes a task out of reach of any classical computer. Using a quantum computer to consider all possible networks simultaneously, the computation time can be reduced to about the square root of the time required by a classical computer. For example, if the task takes 1,000,000 operations to perform on a classical computer, it would take only approximately 1,000 operations on a quantum computer (1,000 x 1,000 = 1,000,000). This would enable us to find much better solutions to these resource allocation problems than our classical computers would permit. The same square root speed up can be obtained for a wide host of optimization problems where the best we know how to do is repeatedly try as many possible configurations as we have time for, and pick the best one. More generally, quantum computers are good for searching for optimal or near-optimal solutions to equations (in the above example, the equation being optimized is the one that calculates the total cable cost).

One can even obtain an immensely greater speed up for some other important computational problems, like the problem of factoring large numbers or the related problem of finding “discrete logarithms”, and other mathematical questions. The mathematical task of factoring a number is a problem that has long baffled computer scientists. Indeed, one of the most commonly-used encryption systems, called RSA encryption, is based on the difficulty associated with factoring large numbers. The more modern elliptic curve cryptography (ECC) relies on the difficulty associated with solving another mathematical problem of finding “discrete logarithms” (the details of the problem are not relevant here – what matters is that is it believed to be a hard computational problem). However, quantum mechanics tells us that these problems are not hard at all once we build quantum computers. Thus, in the future, our information security infrastructure will have to be based the difficulty, or impossibility, of some other information processing task.

For each such potential application, the trick is to discover a suitable quantum algorithm that will give the quantum computer the right instructions to solve the problem in question. What other useful algorithms exist is currently a very active area of research, one in which scientists at Perimeter and other institutions around the world are working.

But the challenges are not only theoretical; many are experimental. The principal difficulty lies in the tremendous delicateness of a quantum superposition state. In classical computing, we can simply look at a bit to determine whether it is in state 0 or state 1. However, with a qubit, we cannot fully examine it to determine its state of superposition. No matter how gently we try to measure the unknown state of a qubit, the extraction of information necessarily causes a quantifiable disturbance in the state of the qubit. This is why we can only extract one bit of information from a qubit. Once we extract one bit, the disturbance caused to the system wipes out any other information that was encoded. This property is very useful if we are trying to perform some cryptographic task (as we discuss below). However, this fragility poses a difficult challenge for the implementation of quantum computers. Nevertheless, physicists and computer scientists have built upon the classical theory of fault-tolerant error correction (necessary to stabilize classical computations running in unstable environments or running for very long periods of time), to develop a set of techniques that allow us to protect quantum information from realistic errors. These techniques require good, but not perfect, control of a quantum mechanical system, and experimental physicists and engineers worldwide are working toward developing such quantum components.

Quantum Communication and Quantum Teleportation

Besides quantum computing, there are other revolutionary applications of the wonders of quantum mechanics just on the horizon, including absolutely secure quantum communication and quantum teleportation. The former relies on the extreme delicacy of a quantum superposition state. The fact mentioned above—that any attempt to measure the state of a qubit destroys its delicate superposition—can be made to work for us. If we encode the information we are transmitting in quantum superposition states, then any attempt by an eavesdropper to read that information will disturb it, and it will be immediately detectable that an unauthorized attempt was made to read the data. We mentioned above that quantum mechanics can be used to devise a computer that would be able to crack the encryption codes we use today, making them useless. But rather than leaving us with no secure way to send data, we see that quantum mechanics also provides us with a new means of communication, whose security is guaranteed by the very laws of nature, rather than clever encryption methods that someone more clever might break. Thus security becomes a question of how deeply we understand the laws of nature.

Finally, we should mention quantum teleportation, which relies on a truly amazing and uniquely quantum phenomenon called entanglement. Consider a pair of classical bits, which noted above can exist in four possible states: 00, 01, 10, or 11. Notice that each bit on its own contains half of the information, e.g. the state 01 means that the first bit is in state 0 (half the information) and the second is in state 1 (the other half of the information). The magic of quantum mechanics is that we can prepare two qubits in an entangled state such that the information in the system (our two qubits) is distributed so that neither qubit on its own carries any information—all of the information is encoded jointly between the two qubits. For example, the entangled state might be a superposition of the 00 and the 11 states, which carries the joint information that both qubits have the same value—both 0 or both 1, although we don’t know if that value is 0 or 1. Measuring either qubit on its own will yield a completely random result, either 0 or 1 (i.e. no information is encoded in the individual qubits), but having measured one qubit we know with certainty that if we measure the other it will yield the same value as the first one did. Furthermore, unlike classical correlations, this very special kind of quantum correlation is “monogamous”, in the sense that if two qubits are maximally entangled, then no other system in the universe can be correlated to the state of those two qubits. In other words, no eavesdropper can be correlated with the entangled qubits, and thus can have no knowledge about what Alice and Bob will each measure.

This entanglement effect does not depend on how far apart the two qubits are. One qubit could be with Alice on the Earth and the other with Bob on Mars. Individually, Alice’s and Bob’s measurements on their own qubit will yield completely random results. But whatever result Alice gets will be the same result that Bob gets, even if these measurements are made simultaneously, i.e. not leaving enough time for a signal of any sort, moving even at the speed of light, to communicate Alice’s result to Bob’s qubit, or vice versa. As noted above, Einstein referred to this as “spooky action at a distance”. While it is beyond the scope set for this essay to explain exactly how, it turns out that entanglement can be used to teleport the full quantum information of a system from one location to another. (Warning: at present, this has only been done for a system consisting of a single photon or a single atom. Whether it is technologically feasible to do this for more complicated systems remains to be seen.) This is remarkable because, as we noted above, it is impossible to measure the full quantum information that exists in any physical system because the delicate superposition information is lost. The key to quantum teleportation is that no attempt is made to actually measure the quantum information; rather, the quantum information is simply transferred from one location to another using entangled qubits at both locations. Teleportation is a very fundamental primitive operation for quantum information processing, since it offers a very reliable way to transport very delicate quantum information, and thus has applications in quantum communication, quantum cryptography, and quantum error correction.

It must be stressed that, unlike as implied in Star Trek, in quantum teleportation the atoms themselves making up the system are not transported, only the quantum information about the system is transported. This quantum information, together with certain classical information sent by conventional means, i.e. no faster than the speed of light, can be used at the “other end” to reconstruct a quantum mechanically exact duplicate of the original system. It should be noted that the information in the original system is destroyed in this whole process—so if you’re being transported to Mars, you’d better hope there are no technical glitches!

Summary

Quantum information —the merging of ideas from quantum mechanics and theoretical computer science—is a very exciting and rapidly growing new field in science. Besides suggesting a number of fascinating potential new technologies, the development of the theory of quantum information provides a tangible example of quantum theory in action, and provides intuition for how quantum mechanics works and what it means. This can help us address other fundamental questions in physics. How should quantum mechanics be interpreted? How does the classical world emerge from the quantum world underlying it? Can ideas about quantum information help us to better understand the fabric of reality? Quantum information scientists at Perimeter have the opportunity to interact with other researchers at the Institute in the strongly overlapping areas of quantum gravity and foundations of quantum theory. Perimeter Institute, together with the University of Waterloo’s new Institute for Quantum Computing (IQC) located nearby is making Waterloo a strong international centre for quantum information.

Additional Reading

For more information on quantum teleportation click here.

For more information on quantum information and quantum computing see the November 2002 issue of Scientific American “Rules for a Complex Quantum World” by Michael A. Nielsen or  “Quantum-enhanced information processing”, in Visions of the Future: Physics and Electronics (ed.: J.M. Thompson), Cambridge University Press (2001) by M. Mosca, R. Jozsa, A. Steane and A. Ekert.