Quantum Computing

“Every so often,” says Isaac Chuang, sitting in his office at IBM’s Almaden Research Center in San Jose, “something new comes along in physics, and everybody says Wow!’ Then they get caught up in a whirlwind.” In the 1970s, the whirlwind was chaos theory. In the late 1980s, it was high-temperature superconductivity. And now?

“Quantum computing,” says Chuang, a slender, soft-spoken physicist who has already emerged as one of the leaders in this esoteric-sounding field with potentially enormous impact.

A quantum computer operates by the rules of quantum weirdness, down in the subatomic realm where our everyday intuitions are violated wholesale. This is a world in which an electron can be in two places at once, in which an atomic nucleus can be spinning clockwise and counterclockwise at the same time. It is a bizarre world in which matter itself dissolves into a ghostly blur of possibilities as soon as you try to look at it.

And yet this surreal world is one in which you can do computing, insists Chuang, whose group at Almaden is one of several that have demonstrated the basic principles in the lab. If he and his fellow researchers can ever scale up their demonstrations into practical machines, the payoff will be enormous. Quantum computers could tackle problems that would stymie their conventional counterparts-easily cracking, for instance, the most sophisticated encryption schemes now in use.

Hence the new whirlwind. “It’s easy for quantum computing to sound like a fanciful theorist’s dream,” says physicist Neil Gershenfeld of the MIT Media Lab. “But just extrapolating Moore’s Law, the scaling relation that says microchips shrink by a factor of two every two years or so, somewhere around the year 2020 or 2030 is when we hit one bit per atom-and when a new semiconductor fabrication plant will cost the gross national product of the planet. So if we really want to keep getting faster, there aren’t many other places to turn. Quantum weirdness is essentially the only resource we have that’s still untapped for computing. It’s the only big thing that’s left in the universe.”

Actually, when quantum computing started out, it was a fanciful theorist’s dream-the late Richard Feynman’s, most notably. The famously whimsical Nobel laureate first started pushing the idea in 1981, following an earlier suggestion by Argonne National Laboratory physicist Paul Benioff. Others quickly followed Feynman’s lead. And by the time Ike Chuang first encountered quantum computing in the late 1980s, shortly after receiving his undergraduate physics degree from MIT, a cadre of at least half a dozen physicists and computer scientists were actively working in the field.

Certainly Chuang was smitten. “I’ve always wanted to know what information is in a physical sense-and to understand what physics is in terms of information,” he says. Quantum computing seemed like a completely new way to understand them both.

Take this business of encoding information, he says: The subatomic world is full of yes-no choices that make it downright easy. Most particles-including electrons, protons and even the ephemeral packets of light called photons-possess a kind of built-in rotary motion known as “spin.” So if your subatomic computer used electrons, for example, you could say that an electron spinning in one direction represented a binary 1, while an electron spinning in the opposite direction represented a 0. And once you encode the information, says Chuang, the subatomic world also offers any number of ways to process it. By manipulating the magnetic environment of electrons, say, or by routing photons through an array of polarizers, mirrors and beam splitters, you could subject your quantum bits to all the operations required by a digital computer.

But there would also be a critical difference. Conventional computers followed the rules of binary logic, governed by an ironclad either-or distinction: Each bit of information is either true or false, on or off, one or zero. To enforce this distinction, conventional machines represent each bit as the presence or absence of a few zillion electrons collected in a tiny silicon transistor, so that the zillions are either there or they are not.

But once you get down to the level of individual particles, says Chuang, almost nothing is absolute. An electron, for example, could be spinning one way or the other-but it could also exist as a kind of mixture of spins. According to the laws of quantum physics, you could say the electron has a probability of spinning one way or the other. But unless you actually made a measurement and forced the issue, you couldn’t know which it was; in a sense, the electron itself would be undecided. And that, in turn, means that each bit of quantum information could be undecided. Instead of being either-or, a quantum “qubit” could be both-and: representing 0 and 1 simultaneously.

This ambiguity has a powerful consequence that becomes more apparent when you think of not one but two qubits. These qubits could simultaneously exist as a combination of all possible two-bit numbers: (00), (01), (10) and (11). Add a third qubit and you could have a combination of all possible three-bit numbers: (000), (001), (010), (011), (100), (101), (110) and (111). This kind of system scales exponentially: n qubits can stand for 2n numbers at once. Line up a mere 40 qubits, and you could represent every binary number from zero to more than a trillion-simultaneously.

Furthermore, says Chuang, just as a collection of quantum qubits could represent a huge array of numbers simultaneously, a quantum computer could process every possible input simultaneously-the most perfect form of parallel processing imaginable. Given the right kind of problem and a sufficient supply of qubits, a quantum computer could outpace its conventional counterparts by many orders of magnitude. “I read about all this,” says Chuang, remembering his first encounter with Feynman’s articles around 1987 or so, “and from then on, I wanted to build a quantum computer.”

But how? Feynman and the other theoreticians had focused on quantum computing as a mathematical abstraction-and with good reason. “Building a real quantum computer is a viciously difficult task,” says Chuang. Everything depends on making sure the qubits retain their incredibly fragile quantum-mechanical mix of 1 and 0-what physicists refer to as staying “coherent.” One bump from a stray air molecule, one twitch in the magnetic field, one ricochet of a random photon, and coherency vanishes. Let that happen in a quantum computer and your qubits will instantly collapse from both-and to either-or-meaning that you will suddenly find yourself looking at an ordinary computer full of ordinary 1s and 0s.

“Quantum mechanics goes away when you look at it,” sighs Chuang. “So you have to make sure that the computer is extremely well isolated from the rest of the world.” But the isolation can’t be total, either, since you still need to put data in and read out the results. “This,” Chuang declares, “is the discord that stalks quantum computing. How can you control it if, at the same time, you have to leave it alone?”

As the 1980s became the 1990s, many researchers continued to grapple with the problem. Chuang even made it the subject of his doctoral dissertation at Stanford. But nothing they proposed seemed feasible. And with no compelling application at hand, quantum computing seemed destined for the same cul-de-sac as countless other exotic pieces of science.

Two developments-one theoretical, one practical-have rescued quantum computing from irrelevancy, explains MIT physicist Seth Lloyd. On the theoretical side, it was a factoring algorithm discovered by Peter Shor of AT&T Research labs-an achievement that went right to the heart of modern cryptography. In most current encryption schemes, including those used to send credit-card numbers and other sensitive information across the Internet, an eavesdropper can break the code of a given message only by factoring a very large number. Now, factoring small numbers is trivial-grade school kids learn that 12 = 2 x 2 x 3. But factoring large numbers is one of the quintessentially hard problems in computer science. No matter how clever the algorithms, in fact, the time required to factor larger and larger numbers grows exponentially. Go beyond a few hundred digits, and even the fastest machines in the world will be overwhelmed: The factoring time will vastly exceed the lifetime of the universe.

Or rather, it will with a conventional computer. Shor proved that a quantum computer could factor large numbers in a time that increases only as some power of the numbers’ size-rapid growth, to be sure, but not remotely as explosive as exponential growth. Indeed, a conventional computer would need to crank away for billions of years to factor a 400-digit number. A quantum machine could do the job in about a year. The implication was that “unbreakable” codes might now be breakable. And with that announcement, the National Security Agency, the Pentagon, the cryptography community, and indeed, the whole computer community woke up to the fact that quantum computing wasn’t a theorist’s plaything anymore. Peter Shor was holding out the possibility of a real and critically important application.

Meanwhile, on the experimental side, quantum computing was beginning to look much more possible in the lab. In 1993, for example, Lloyd brought the mathematical abstractions down to earth when he showed how quantum computation could be carried out by qubits arranged in a regular array-just the kind of quantum computer that might actually get built. Then in 1996, Chuang and MIT’s Gershenfeld made things even more concrete when they suddenly saw a way to build it.

“I went into Ike’s office on a Monday and didn’t emerge until Friday,” laughs Gershenfeld, thinking back to the quantum computing conference that brought him to the University of California at Santa Barbara and the Institute for Theoretical Physics, where Chuang had a postdoc appointment. “We got this feeling that comes along only rarely, that there was this beautiful structure already existing in the world, and that we were seeing it for the first time.”

Nuclear qubits were appealing for several reasons. First, you can make a perfectly fine qubit out of any nuclear isotope that has a spin-as many do. Second, says Gershenfeld, “this is the most coherent system in the universe.” Every nucleus is protected from outside disturbances by its dense cloud of electrons. That means that once you get its spin lined up, it will stay that way for hours or days-an eon in computer time. Third, nuclear qubits are incredibly easy to assemble. “Instead of trying to nanofabricate nanostructures,” says Gershenfeld, “we can just use the ones nature gave us: molecules.” Moreover, he points out, the nuclear spins inside a given molecule tend to interact nicely. Take chloroform, for example, a molecule consisting of a carbon atom attached to three chlorine atoms and one hydrogen atom: When the hydrogen nucleus and the carbon nucleus are spinning the same way, their energy levels will be measurably different from when they are spinning opposite from one another.

Finally, says Gershenfeld, the technology for manipulating these nuclear spins is already very mature. It’s called nuclear magnetic resonance, or NMR, and it is routinely used in chemical analysis and in hospital magnetic resonance imaging scanners. It’s a simple matter to adapt commercial NMR spectrometers to do quantum computing.

Say you want to carry out a logical operation using chloroform-something like, “If carbon is 1, then hydrogen is 0.” You just suspend the chloroform molecules in a solvent, and put a sample in the spectrometer’s main magnetic field to line up the nuclear spins. Then you hit the sample with a brief radio-frequency pulse at just the right frequency. The hydrogen spin will either flip or not flip, depending on what the carbon is doing-exactly what you want for an if-then operation. By hitting the sample with an appropriately timed sequence of such pulses, moreover, you can carry out an entire quantum algorithm-without ever once having to peek at the nuclear spins and ruin the quantum coherence.

So there it was, Chuang and Gershenfeld realized: NMR was a natural for quantum computing. They were not alone. Chuang remembers being “surprised and delighted” to learn that Harvard University NMR expert David Cory and his colleagues were independently making exactly the same proposal. For researchers of Cory’s caliber to enter the field constituted more of an endorsement of the NMR idea than a rivalry, Chuang believed. In any case, there was plenty of work to go around. By this point, Lloyd recalls, with researchers having identified a real application for quantum computing plus a feasible technique for making it work, “all hell was breaking loose” in the field. “All of a sudden there was this wonderful new game to play.”

The game has only gotten better. In just the past few years, for example, Shor and others have shown that quantum computers needn’t be as fragile as researchers once feared; a variety of quantum error-correction schemes will allow the devices to undo the damage caused by environmental perturbations and restore their qubits to full coherence. Lov Grover of Lucent Technologies’ Bell Labs has discovered a quantum search algorithm that is substantially faster than its best classical counterpart. Chuang himself has used NMR to demonstrate Grover’s algorithm, first on a two-qubit quantum computer-a chloroform molecule-and more recently on a three-qubit molecule. Along the way, Chuang and Gershenfeld’s partnership has expanded into a nationwide consortium for quantum computing research, including members from MIT, Stanford, the University of California at Berkeley, IBM and several other industrial partners. Cory’s team, which is working on an NMR demonstration of Shor’s algorithm, has likewise broadened into a Harvard-MIT collaboration. Both groups are among those getting money from the Defense Advanced Research Projects Agency-the arm of the Defense Department that essentially invented the Internet-as part of the first significant federal funding initiative for quantum computing.

None of this means that we’ll be trading in our PCs for quantum laptops anytime soon. Quantum computing is barely into its proof-of-principle stage, with a long way to go before it evolves even to the qubit equivalent of World War II-era vacuum-tube machines like the ENIAC. Much more likely are quantum add-ons to conventional machines-“coprocessors” that will perform specific tasks in the same way that a graphics card takes over the most difficult display chores.

What exactly those tasks will be, however, is an unsettled question. MIT physicist Edward Farhi points out that the study of quantum algorithms is still in its infancy. The two best ones discovered so far-Shor’s and Grover’s-will doubtless be followed by many more, opening up applications that go well beyond factoring and searching. Nonetheless, says Farhi, “a quantum computer isn’t necessarily fast. It’s a device that attacks problems in a different way. We’re still trying to understand what makes a problem amenable to that kind of attack. You have to choose your problem carefully to take advantage of the quantum magic.”

In practice, adds Farhi, how quantum coprocessors are used could depend a lot on how much they cost. And that’s a complicated issue. At IBM Almaden, for example, the core of Chuang’s quantum computer is small and inexpensive: qubit-containing molecules dissolved in a few drops of colorless solvent, encased in a glass tube smaller than his little finger. But the NMR spectrometer that makes the computer go is a silvery, 10-foot-tall cylinder surrounded by great thickets of wires and plumbing-most of it required to service the liquid helium that chills the spectrometer’s superconducting magnets. If future quantum coprocessors follow this pattern, they will be huge, multimillion-dollar behemoths that fill up whole rooms, and that only governments can afford. In that case, quantum computers may well be restricted to hard-core national security tasks such as cryptography and intelligence-gathering.

But such an outsized contraption may not be inevitable. Gershenfeld’s group at the MIT Media Lab is working on a compact, room-temperature NMR computer. They hope this device will be a prototype of a quantum coprocessor that will power inexpensive little gadgets-peripherals that will sit on the desktop like a modern-day printer or scanner. If that proves to be the pattern, then we could see a new generation of quantum hackers going to work in much the same way their forebears did at the beginning of the personal computer revolution, creating a profusion of innovative quantum software.

In the meantime, however, Chuang and his fellow experimenters are far less concerned with their machines’ physical size than with their qubit count. “The first year we had lots of wonderful one-qubit machines popping up all over the place,” he says. “Now at IBM we have a three-qubit computer, and we’re planning even larger computers.” In March, Los Alamos National Laboratory announced a seven-qubit NMR computer, and Chuang is confident that one lab or another will soon be demonstrating molecules with as many as 10 qubits. He concedes that this will be a tricky task, however. “Say I want a molecule with certain properties. When I draw it and go to the chemists, they just laugh: ‘That’s not real!’ They call it a ‘physicist’s molecule.’” One complication is that carbon, the key ingredient of all complex molecules, almost invariably occurs as the isotope carbon-12-which is spinless. Chuang’s chloroform computer worked only because its molecules were made with the rare and expensive isotope carbon-13, which does spin.

The myriad possibilities are limited only by your imagination, says Gershenfeld-which is precisely why quantum computing has stirred up so much excitement. “This has the feel of being a whole new science,” he declares. “Computer scientists are having to learn physics, and that doesn’t quite fit into their intellectual framework. Physicists are having to learn computer science, and that doesn’t quite fit into their framework. Quantum computing breaks down the institutional boundaries at almost any institution you can name. And every side is the richer for learning a new language for describing the world.”

But perhaps an even deeper reason for the excitement is the way quantum computing expands our intellectual horizons. “I’m not just doing this for the sake of quantum computing,” says Chuang. “I’m doing it because so little is known about computing in general. For 50 years we’ve just focused on one technique in computing”: that is, microchips based on the on-off dichotomy of binary logic. The pursuit of quantum computing, Chuang believes, addresses a fundamental issue: “What does it take to perform a computation-and how can we manipulate nature’s laws to perform the computation we want? That is the more basic question that quantum computing brings out.”

On the Quantum Quest Organization Key Researchers Focus IBM/MIT/Berkeley/Stanford Isaac Chuang (IBM)
Neil Gershenfeld (MIT) “Enabling technology” for NMR-based quantum computing; scale up to 10-40 qubits Harvard/MIT/Los Alamos David Cory (Harvard) Quantum algorithms and NMR-based systems NIST Christopher R. Monroe Ion-trap quantum computing; demonstrated a two-qubit device using trapped barium ions Caltech/MIT/USC Seth Lloyd (MIT)
M. Despain (USC)
H. Jeff Kimble, John Preskill, and Steven Koonin (Caltech) Algorithms and quantum error correction Oxford University David Deutsch, Jonathan Jones Ion-trap and NMR implementations; quantum information theory