Breaking D-Wave

Cracking a code is essentially like trying to guess a number between one and a trillion (the harder the code, the bigger the number). While a classical computer would have to try each number in succession until it found the right one, a quantum computer could try all the numbers at once. This popular explanation of how a quantum computer works, however, isn’t quite right. After all, if you ask a trillion questions at once (“Is zero through a trillion the right password? “), the answer you get back (“Yes”) isn’t very useful. Shor’s algorithm does indeed involve manipulating qubits that represent many numbers simultaneously, but it requires a more circuitous search for patterns that enable it to reject the wrong passwords and spit out only the right one.

However you think about it, the result is a computer that can do things that were previously impossible, such as factoring huge numbers quickly. But factoring is far from the only application of quantum computing, though it has dominated the agenda thanks to the nsa’s interest and bankroll. “I’ve always thought that Shor’s algorithm has been a very big negative overall for quantum computing, because it’s thrown everybody off track,” D-Wave’s Rose says. “The really valuable applications are not in code-breaking — those are not interesting from an industrial perspective, because they don’t lead to recurring large markets.”

The most radical application for quantum computers is something called quantum simulation. If you wanted to know whether a certain complicated molecule would make a good drug, you could, in theory, solve the quantum-mechanical equations that govern the motion of all the electrons and protons and other components of the molecule, which would tell you exactly how it will behave. But the math is too complex for us to puzzle out. Because qubits follow the same quantum mechanical rules that electrons and protons do, a quantum computer actually embodies those equations and can solve them effortlessly. If the computer is powerful enough, it could model just about anything in the universe. “This is not like going from the Pentium II to the Pentium III,” says Ray Laflamme, director of Waterloo’s Institute for Quantum Computing, the world’s largest dedicated quantum-computing research centre. “It’s fundamentally different.”

The difference is such that no one has really been sure how to build a quantum computer. The qubit has to be something that can physically take on two values representing zero and one, and there are wildly different ideas about what that should be. The computer that factored fifteen in 2001 was a seven-qubit system that used nuclear magnetic resonance (the same process used for mri imaging) to toggle the spins of a test tube of carbon and fluorine atoms. This approach is great for toy-sized computers, but seemingly impossible to scale up to the thousands or millions of qubits needed for a useful quantum computer. The opposite is true for superconductor-based systems in which zero and one are sometimes represented by electrical currents flowing either clockwise or counter-clockwise around a loop of superconducting metal. Building even a few superconducting qubits has proven to be exceptionally challenging, but if that hurdle is cleared, it should be relatively straightforward to scale the system up using production techniques already developed by the computer industry.

D-Wave’s demonstration system is a sixteen-qubit superconductor-based machine. This is remarkable because, of all the groups around the world working on superconducting qubits, none have succeeded in operating more than two qubits together. The problem is that the quantum state that allows zero and one to exist simultaneously is extremely sensitive to outside perturbations. Noise from the outside environment, stray electrical signals, and tiny temperature fluctuations can all cause the qubit to lose its quantum-mechanical properties, a process known as decoherence. For scientists confronted with D-Wave’s claims that they’ve operated a sixteen-qubit computer, the immediate question is: how did they overcome decoherence? “If you go and ask anybody in the world who’s leading in putting qubits together, the first thing you’ll ask them is, ‘What is the decoherence time?’” says Laflamme. “And if they say ‘I don’t know,’ you’ll be very skeptical of the rest of the thing.”

D-Wave has certainly met with skepticism, but Rose, who won three Canadian wrestling titles before starting his Ph.D. in theoretical physics at ubc, seems to relish the fight. D-Wave, he explains, has adopted a modified quantum-computer architecture that, while not capable of executing Shor’s algorithm, has the advantage of being less sensitive to decoherence and can still tackle a number of other commercially interesting algorithms. He insists that the emphasis on the computer’s building blocks is a diversion from the real test of a quantum computer, which is how much time it needs to tackle problems of various sizes. “That’s really the only smoking gun for quantum computation,” he says. The current six-teen-qubit system is too small to test performance on large problems, but D-Wave’s ambitious road map calls for a thirty-two-qubit system by the end of this year, and 1,024 qubits by the third quarter of 2008. While scientists are clamouring for evidence that D-Wave’s computer is truly quantum, as far as Rose is concerned, the question will be answered purely on the basis of the computer’s performance within the next year. “And you know, it could turn out that the whole thing won’t work,” he says. “That’s always a risk. But it won’t be for lack of effort, I’ll tell you that much.”

When I finished my physics Ph.D. and headed out on the post-doctoral job-interview circuit in late 2001, interest in quantum computing was exploding. I added a couple of slides to the end of my standard presentation, drawing an extremely tenuous link between my thesis work and quantum computing, and even went so far as to insert “quantum computing” in the title of a talk I gave at a university in the Netherlands. I finally accepted a position in the quantum-computing group at an nsa lab in Maryland, where, despite the name, the research we did had little connection to the world of qubits. Instead, we were exploring the boundaries between the classical and quantum worlds. We know, for instance, that an atom can be in two places at once, and a baseball can’t. But what about ten atoms? Or 1,000 atoms? Where is the dividing line between atoms and baseballs? You could argue — as we did to our funders — that it would be useful to know this in order to build a quantum computer, but, really, our primary interest was trying to answer one of the great questions of modern physics.

The duplicitous game of justifying fundamental science by promising that it will lead to a magic computing machine or some equivalent is, increasingly, a fact of life for scientists in every field. Forman, the Smithsonian historian, argues that the transition from modernity to postmodernity three decades ago was marked by a dramatic flip in the status of science and technology. Until then, “science was very closely connected with knowledge for its own sake,” he says. Now, the process of scientific inquiry is only justified by its ends: useful gadgets. “Our postmodern perspective really does put the very existence of science into question.” For those of us who view understanding our universe as a worthy goal, we can be grudgingly grateful that the military’s approach to technology development still leaves room, however constrained, for basic science.

There is also room for D-Wave’s purely technological, engineering-style approach. Their glossy demonstration in February may have left some scientists fuming, but it spurred plenty of ideas for applications from potential industry partners, Rose says. As the company forges ahead, intent on doubling and redoubling the number of qubits in its system rather than painstakingly ensuring that the qubits it already has are really behaving as they should, scientists will continue to be irritated. But what D-Wave is trying to do shouldn’t be confused with science: it is simply trying to build a computer, using technology that may or may not be ready for the task. In that spirit, it’s worth remembering Rose’s words as he stood at the podium demonstrating a final sample application: the famously difficult mathematical problem of finding the optimal seating plan for a wedding. The list of guests and their seating requirements was sent from the California auditorium to the system in British Columbia, which churned out the answer. As the giant screen displayed a solution that separated two guests who wanted to sit together, Rose turned to face the audience, eyes blinking innocently, and said, “Sometimes you just can’t satisfy everybody.”