As reported on Wired.
BY CADE METZ
The D-Wave computer housed at the USC-Lockheed Martin Quantum Computing Center in Marina del Rey, California.Photo: Mae Ryan/Wired
Google bought one. So did Lockheed Martin, one of the world’s largest defense contractors. But we still can’t agree on what it is they bought.
D-Wave, the company that built the thing, calls it the world’s first quantum computer, a seminal creation that foretells the future of mathematical calculation. But many of the world’s experts see it quite differently, arguing the D-Wave machine is something other than the computing holy grail the scientific community has sought since the mid-1980s.
No doubt, the argument will continue. But today, researchers at the University of Southern California published a paper that comes that much closer to showing the D-Wave is indeed a quantum computer. USC houses and operates the D-Wave system owned by Lockheed, and the researchers — led by Daniel Lidar, a professor of electrical engineering, chemistry, and physics — say they have at least shown the machine is not using a computing model known as “simulated annealing,” which obeys the laws of classical physics (the physics of everyday life) rather than the more elusive properties of quantum physics.
“[Our research] rules out one type of classical model that has been argued as a proper description of the D-Wave machine,” Lidar says. “A lot of people thought that when D-Wave came on the market their machine was just doing that, [but] we ruled that out.”
The paper, Experimental Signature of Programmable Quantum Annealing, appears in the well-respected academic journal Nature Communications. Quantum annealing is a computing model that, yes, operates in the quantum realm, and according to Lidar, the team’s research shows “a very great agreement” between quantum annealing and the way the D-Wave system operates.
First proposed in 1985 by British physicist David Deutsch, a quantum computer is a machine that operates according to the mind-bending principles of quantum mechanics, the physics of very small things like electrons and photons. With a classical computer, a transistor stores a single “bit” of information. If the transistor is “on,” it holds a “1.” If it’s “off,” it holds a “0.” With quantum computer, information is held in a system that can an exist in two states at the same time, thanks to what’s called the superposition principle of quantum mechanics.
This “qubit” can store a “0″ and “1″ simultaneously. If you build two qubits, they can hold four values at once — 00, 01, 10, and 11. As you tack on additional qubits, you can fashion a machine exponentially more powerful than a classical computer.
The rub is building even a single qubit is difficult. When you look at — i.e. read information from — a quantum system, it decoheres. In other words, it turns into an ordinary bit capable of holding only a single value. It ceases to be a quantum computer.
There are many ways around this problem, and the minds at D-Wave, including founder and CTO Geordie Rose, believe they’ve found one. In 2007, the company released what it called a 16-qubit quantum computer, and the company’s current model is billed as a 512-qubit machine. This is what Google is using.
According to D-Wave, the machine contains 512 superconducting circuits, each a tiny loop of flowing current. These are cooled to almost absolute zero, the company says, so they enter a quantum state where the current flows both clockwise and counterclockwise at the same time. When you feed the machine a task, it uses a set of algorithms to map a calculation across these qubits — and then execute that calculation. Basically, this involves determining the probability that a given set of circuits will emerge in a particular pattern when the temperature inside the system is raised.
But scientists such as Greg Kuperberg, a math professor at the University of California, Davis, are skeptical. “D-Wave’s technology has been an enigma, in a negative sense,” he told us last year. The USC paper gets us a little closer to the truth, though Lidar and his team still leave room for doubt over the way the machine operates.
What they can say for sure is that the system doesn’t use simulated annealing, which is essentially a means of searching for a mathematical solution. According to Lidar, simulated annealing is akin to looking for the lowest possible point in a vast landscape.
“We call it an energy landscape,” he says. “There is a solution hiding somewhere in that landscape, and you can imagine that solution is hiding at the lowest point on the surface. You’re trying to find that lowest point.” This is done by randomly traveling across the landscape, moving down “hills” and back up them, until you locate the deepest valley.
This strategy relies purely on classical physics, not quantum physics. But Lidar says the D-wave is “consistent” with quantum annealing. This is similar to simulated annealing — except you can, in essence,go through the hills rather than over them. “You can take advantage of a quantum phenomenon called tunneling,” Lidar says. “It’s like a quantum shortcut.” He’s careful to say that he and his team have not proven that the D-Wave uses quantum annealing, but the system certainly appears to use it.
Dr. Daniel Lidar, a professor of electrical engineering and chemistry at the University of Southern California, whose research focuses on quantum computing and the machine built by D-Wave. Photo: Mae Ryan/Wired
Even if they did prove the machine operates in this way, it wouldn’t exactly prove it’s a quantum computer. When those in the scientific community hear the term, they tend to think of a “universal quantum computer,” a quantum computer that can handle any task. The D-Wave doesn’t work that way — it’s geared to particular calculations — but according to Lidar, the concepts behind it could be use, in theory, to build an universal quantum computer.
Whatever you call it, the D-Wave is useful, helping to solve what are known as combinatorial optimization problems, which turn up in everything from genome sequence analysis and protein folding to risk analysis. In announcing its use of the D-Wave machine last month, Google said it would use the system to help advance machine learning — i.e. efforts to create computing systems that can learn in much the same way people do.
“We believe quantum computing may help solve some of the most challenging computer science problems, particularly in machine learning,” Hartmut Neven, a Google director of engineering, wrote in ablog post. “Machine learning is all about building better models of the world to make more accurate predictions.”
For what it’s worth, Google is matter-of-fact in calling the D-Wave a quantum computer. And it should come as no surprise that it just hired Sergio Boixo, one of the researchers behind the USC paper. The machine is housed at NASA’s Ames Research Center, not far from Google’s headquarters, in a place the company calls the Quantum Artificial Intelligence Lab. At Google, the semantics aren’t nearly as important as the task at hand.