Programming the Universe

by Seth Lloyd

  There is no known easy way to use a classical computer to factor a 400-digit number. One of the largest classical computations ever performed was factoring a 128-digit number a few years ago. The computation used hundreds of classical computers linked by the Internet and required trillions of logical operations to be performed on billions of bits. More recently, a 200-digit number was factored. Factoring a 400-digit number using conventional techniques is likely to remain out of reach for many years.

  The apparent difficulty of factoring large numbers is the basis for a powerful method for protecting information. Whenever you use your bank card or buy anything over the Internet, the security of your transaction is protected by a technique called public key cryptography. Suppose you wish to use your credit card to buy extra copies of this book from Amazon.com. Amazon sends you a “public key” consisting of a large number that is the product of two smaller prime numbers. Your computer then uses this public key to scramble or “encode” the information you send to Amazon, including your credit card information. To decode that information, Amazon uses the “private key,” consisting of the two prime numbers that, multiplied, give the public key. Thus anyone who possesses the public key can encode information, but to decode it requires the private key, consisting of its factors. Public key cryptography is clearly a useful trick, and its security depends on factoring being hard. Public keys of 256 digits are very hard to crack by classical computation and are currently considered more than adequate to protect most forms of information.

  In 1994, however, Peter Shor at AT&T Laboratories showed that even a relatively small quantum computer, with only a few thousand qubits, could factor 400-digit numbers with ease. In effect, he orchestrated the computation so that the actual factors could be identified over the noisy background of potential factors. To see how factors can be identified by combining their waves in a quantum computation, again think of a symphony: if Beethoven orchestrates his theme to be played by violin, cello, piccolo, and trombone, you will hear that theme no matter what the rest of the orchestra is playing.

  Suppose that while the quantum computer is exploring all possible factors, you rudely go in and measure the quantum computer’s qubits to find out what the computer is doing. Its answer will be “Oh, I was just looking at [some pair of 200-digit numbers] to see if, when multiplied, they gave the right answer.” Most of the time, the numbers don’t. Measuring a quantum computer while it’s exploring all possible solutions to the factoring problem is no different from picking one of those possible solutions at random. To get the full benefit of the computation, you must not disturb the computer while it’s computing. You must let each of the parallel computations take its course, interfering with the others; only then can the symphonic nature of quantum computation help you find the factors.

  Searching

  Factoring is not the only hard problem that quantum computers are potentially good at solving. In 1996, Lov Grover, of Bell Laboratories, showed that quantum computers were better at searching than classical computers. Suppose you don’t remember in which of your four pockets you put your wallet. First you check one pocket, then another. In the worst case, you need to root around in all four pockets to find your wallet; on average, you need to check two. But suppose you could use quantum parallelism to check all your pockets at once. Grover showed that you need make only one quantum search to come up with the wallet.

  Needless to say, Grover’s algorithm works with more than four options. If you’re looking for something that could be in 100 possible places, you need to perform only 10 quantum searches to find it, compared with an average of 50 classical searches. If you’re looking for something in a million possible spots, you need to perform only 1,000 quantum searches, compared with half a million classical ones. In general, the number of quantum searches required to locate what you’re looking for is the square root of the number of places in which it could be.

  What other problems can quantum computers solve more efficiently than classical computers? In order to exploit the symphonic nature of quantum parallelism, you must allow all the parts of the quantum computation to interfere with one another. But like writing a symphony, arranging the necessary quantum interference is tricky, so much so that there are only a few quantum algorithms, such as factoring and searching, that are currently better than their classical analogs.

  Building Quantum Computers

  In the fall of 1994, I received a call from Jeff Kimble, a professor of physics at the California Institute of Technology. Jeff had read a couple of my papers on quantum computation and wanted to discuss the possibility of constructing quantum logic gates using photons.

  Jeff Kimble is a tall Texan who has a way with atoms and light. He was introduced to me as the man who had “squeezed light more than it had ever been squoze before,” and if that light felt anything like my hand after he had shaken it, I was inclined to believe this description. When we began talking, I noticed two things. The first was that Jeff tells you without hesitation what he thinks. If he looks at your calculation and says in his soft Texas accent, “There’s trouble in River City,” that means you’re in trouble. The second was that as he described his experiments, I didn’t understand more than one word in three of what he was saying.

  Week by week that fall, as I spent more time talking with Jeff and his students, the picture became clearer. He was taking individual photons and making them interact strongly with individual atoms. Basically, he was putting a photon in a can with an atom and shaking them about. The “can” was an optical cavity consisting of two mirrors a few millimeters apart. The photon bounced back and forth between the mirrors tens of thousands of times before eventually getting free. Jeff would drip cesium atoms into the cavity while sending in the photons from his lasers and then see what came out. Because each photon and each atom spent a substantial fraction of a second confined together in a small space, they had plenty of time to interact.

  Whereas an atom is tiny, one ten-billionth of a meter across, a photon can be a whole lot bigger. Recall that photons are particles of light, arising out of wiggles in the electromagnetic field. Because of the Heisenberg uncertainty principle, there is a trade-off between the rate at which the electromagnetic field is wiggling and the volume the photon occupies: the better defined the field’s wiggle rate, the larger the volume of space the photon occupies. In Jeff Kimble’s optical cavities, the photons that can get in have a very well defined frequency and are long and skinny—100 meters long! But the cavity itself is only a few millimeters in length. How can something 100 meters long fit into a container so much smaller? It took me some time to bend my mind around this question. The answer is that the photon goes into the cavity the way a snake goes into a coffee can: It gets doubled back and forth thousands of times. Because of all of those doublings, the strength of the electromagnetic field that corresponds to a single photon is thousands of times higher inside the cavity than outside. As a result, a photon in the cavity interacts very strongly with an atom in the cavity.

  Jeff and his graduate students Quentin Turchette, Christina Hood, and Hideo Mabuchi were then performing experiments in which they sent two photons through the optical cavity in the presence of an atom and looked at what had happened to the photons when they came out. Because both photons interacted strongly with the atom, they interacted strongly with each other as well. But was that interaction enough to construct a quantum logic gate, such as a controlled-NOT gate? When we started, they didn’t know from quantum logic gates, and I didn’t know from photons. When we were done, I had shown that almost any interaction between photons sufficed to construct a quantum logic gate, and they had exhibited the first photonic quantum logic gate.

  At the same time, Dave Wineland and Chris Monroe at the National Institute for Standards and Technology (NIST) in Boulder performed an experimental realization of a proposal by Ignacio Cirac and Peter Zoller of the University of Innsbruck for an architecture for quantum computers, based on trapping ions using osci
llating electromagnetic fields and then zapping them with lasers. These ions were atoms that had been stripped of an electron and thus had a net positive charge, allowing them to be trapped with relative ease. (Old physics joke: Two atoms walk into a bar. One atom looks down at himself and says, “Hey, I lost an electron.” The other atom says, “Are you sure?” The first atom replies, “I’m positive!”) Once the ions were trapped, they could be cooled to very low temperatures and zapped with lasers to make them interact and perform quantum logic operations.

  Both Kimble’s and Wineland’s experiments were performed by modifying existing experimental setups. The relative ease with which the first quantum logic operations were performed made it plausible that quantum computers could in fact be constructed.

  When I joined the faculty of MIT in December 1994, I began working with scientists and engineers from all over the world to build quantum computers. David Cory, a professor of nuclear engineering at MIT, with his colleagues Tim Havel and Amir Fami, had shown how nuclear spins could be made to compute using the atom-zapping techniques described above; when applied to nuclear spins, these atom-zapping techniques are called “nuclear magnetic resonance,” or NMR. Shortly afterward, Neil Gershenfeld at the MIT Media Lab independently discovered how to use NMR to compute, and I began working with Neil and Isaac Chuang to perform simple quantum computations using NMR. With only a two-bit quantum computer, we were able to provide demonstrations of quantum parallelism by making it perform several tasks simultaneously. Later, Chuang would build larger and larger NMR quantum computers, culminating, a few years ago, in a seven-qubit computer that could perform a simple version of Shor’s algorithm. Chuang used this computer to factor the number 15. Clearly, there is still a long way to go before we have quantum computers that can factor 400-digit numbers!

  Figure 12. A Simple Quantum Computer

  A simple quantum computer can be constructed out of a chain of nuclear spins in a molecule. Here the nuclear spins are spin up, up, down, down, up: that is, the spins register the quantum bits 00110.

  In addition to continuing to collaborate with Jeff Kimble on storing and transporting quantum bits on photons, I began working with scientists at MIT on making light interact with atoms. Jeffrey Shapiro, Franco N. C. Wong, and Selim Shahriar, all of the Research Laboratory of Electronics, were keen to explore the possibilities for quantum communication, and we soon wrote a proposal for constructing the world’s brightest source of entangled photons, together with a method for catching those photons using atoms trapped in optical cavities. These techniques, along with related techniques proposed by Kimble, Cirac, and Zoller, form the basis for an attempt to construct a quantum internet—a network of quantum computers linked together optically. (I am currently working to design a quantum Internet search engine, provisionally called “Quoogle.”)

  At the same time, I began to collaborate with Hans Mooij, of the Delft University of Technology, on the possibility of constructing quantum computers using superconducting systems. In a superconductor, electrons encounter almost no resistance as they move from place to place. Such a flow of superconducting electrons is called a supercurrent. Another way of thinking about superconductivity is that the atoms in the materials through which the electrons move have a hard time grabbing hold of the electrons. This means that the electrons can move through the material in a way that preserves quantum coherence: they stay entangled. Mooij and other workers on superconductivity had pointed out that it might be possible to use this slippery feature of superconducting electrons to perform quantum computation. If you construct a superconducting loop of material and interrupt it in the right places with very thin pieces of non-superconducting material called Josephson junctions, the resulting device can support supercurrents that go either clockwise or counterclockwise around the loop. Such a device could easily store one bit of information: identify counterclockwise supercurrents with the state 0 and clockwise supercurrents with the state 1.

  Such a superconducting quantum system can register not just a bit but a qubit. We calculated that if we designed the superconducting bit very carefully, in order to reduce interactions between the supercurrent and its surroundings to the absolute minimum, then the supercurrent could be put in a quantum-mechanical superposition of circulating clockwise and counterclockwise at once. At some level, the ability of a supercurrent to exhibit such a quantum superposition should not be surprising; after all, a supercurrent consists of electrons, and an individual electron has no trouble being in two places at once. But a supercurrent can consist of billions of electrons, and the loop around which it circulates clockwise and counterclockwise at the same time is almost large enough to be seen with the naked eye. Such macroscopic quantum coherence is indeed surprising, and researchers had been trying for decades to exhibit it without success. With Terry Orlando at MIT, Mooij and I began a research collaboration that resulted a few years later in the demonstration by Mooij’s student Caspar van der Wal of quantum bits that could be put in just such a macroscopic quantum superposition. (James Lukens’s group at Stony Brook independently exhibited macroscopic quantum superpositions at the same time.) Over the past several years, Mooij and other researchers have built and exhibited the coherent control of superconducting qubits. Simple quantum computers consisting of several coupled superconducting qubits are currently being built and tested. I am now working in Japan with Jaio-Shen Tsai, Yasunobu Nakamura, and Tsuyoshi Yamamoto at NEC, trying to perform the first simple quantum computations on superconducting qubits.

  Over the last decade, I have been lucky enough to work with some of the world’s greatest experimental scientists to build quantum computers and quantum communication systems. The degree of their intimacy with nature is not something I can truly comprehend, let alone hope to emulate. These experimentalists possess the deepest possible theoretical understanding of quantum mechanics—the understanding needed to forge brand-new ways of talking to atoms and photons and convincing them to do what they have never done before.

  CHAPTER 7

  The Universal Computer

  Simulating the Universe

  We’ve shown how the laws of physics can be used to perform quantum computations in an efficient fashion. Now, let’s consider how a quantum computer can efficiently simulate the operation of the laws of physics.

  “Quantum simulation” is a process in which a quantum computer simulates another quantum system. Because of the various types of quantum weirdness, classical computers can simulate quantum systems only in a clunky, inefficient way. But because a quantum computer is itself a quantum system, capable of exhibiting the full repertoire of quantum weirdness, it can efficiently simulate other quantum systems. Every part of the quantum system to be simulated is mapped onto a collection of qubits in the quantum computer, and interactions between those parts become a sequence of quantum logic operations. The resulting simulation can be so accurate that the behavior of the computer will be indistinguishable from the behavior of the simulated system itself.

  Recall that if two information-processing systems can simulate each other efficiently, they are logically equivalent. Because the universe can perform quantum computation and a quantum computer can simulate the universe, the universe and a quantum computer have the same information-processing power: they are essentially identical.

  Quantum simulation is one of the most remarkable experimental demonstrations of the power of quantum computation to date—and the application of quantum computation that is most relevant to understanding the computational universe. It is because they tend to be doing many things at once that quantum systems are hard to simulate classically. Simulating a single nuclear spin, which can do two things in quantum parallel, is not so bad, but 10 spins can be doing 1,024 things at once and 20 spins can be doing 1,048,576 things at once, etc.

  In general, to follow the dynamics of a quantum system, a classical computer has to assign a subcomputation to each piece of the quantum wave function, but the number of things the quantum
system is doing grows very rapidly as the size of the quantum system increases. To simulate the dynamics of even a relatively small quantum system consisting of 300 nuclear spins is, as we’ve established, entirely unmanageable.

  But a quantum computer has no trouble performing many subcomputations in quantum parallel. In 1982, the Nobel laureate Richard Feynman proposed a hypothetical device he called a universal quantum simulator. To simulate 300 nuclear spins, the universal quantum simulator would require only 300 quantum bits. As long as you could program the interactions between the 300 qubits so that they imitated the interactions between the 300 spins, then the dynamics of the qubits could simulate the dynamics of the spins.

  Feynman merely noted the possible existence of universal quantum simulators; he gave no clue as to how they might be built. In 1996, I showed that conventional quantum computers were themselves universal quantum simulators; that is, any desired set of quantum-mechanical interactions could be programmed into a quantum computer and the quantum simulation could then take place by the repeated application of quantum logic operations on the computer’s qubits.10 (Techniques for performing quantum simulation were also derived independently around the same time by Christof Zalka of the University of Bern and Stephen Wiesner of Tel Aviv University.) Moreover, I was able to show that the quantum simulation was efficient, in that (a) the number of qubits needed to perform the simulation was equal to the number of bits in the system to be simulated, and (b) the number of ops the quantum computer required to perform the simulation was proportional to the various lengths of time over which the system was to be simulated.