A comprehensive new test that pits the performance of traditional computers against quantum ones reveals that the machine marketed as the first commercially available quantum computer holds no speed advantage in its ability to solve a certain type of problem.
Since the 1980s, physicists have aspired to build a quantum computer. Using quantum bits, or qubits, which can be both 0 and 1 simultaneously, these computers should be capable of performing certain tasks far faster than traditional computers (SN: 3/10/12, p. 26).
Due to numerous technical and basic physics challenges, such devices are decades away at least. Nonetheless, D-Wave Systems of Burnaby, Canada, decided to build the best quantum computer it could with current technology. D-Wave One, introduced in 2010, and the recently released D-Wave Two are made up of small superconducting circuits that serve as qubits. The computers perform an algorithm that the company says capitalizes on two properties of quantum mechanics, entanglement and tunneling.
The algorithm should excel at solving a certain class of problems that require picking the best possible solution out of an exhaustive list of potential solutions. Tackling these optimization problems quickly could prove useful in image detection, data mining and financial analysis. Google was intrigued enough to team up with NASA and the Universities Space Research Association to buy the roughly $15 million D-Wave Two.
Whether the machine actually exhibits quantum entanglement and tunneling is up for debate; several recent studies provide some evidence that it does. “But those studies don’t address whether the computer is actually better,” says Matthias Troyer, a computational physicist at the Swiss Federal Institute of Technology in Zurich.
So Troyer and his colleagues set up a speed test between a quantum algorithm running on a 503-qubit D-Wave Two computer (owned by Lockheed Martin) at the University of Southern California and a classical version of the same algorithm running on a traditional computer.
The primary goal wasn’t to see which solved problems faster — that would depend on factors such as processing speed. Instead, the researchers wanted to know how each computer would do as the problems got harder. Traditional computers take exponentially longer to solve optimization problems as more variables are added. The solving time for a quantum computer, however, should rise much more slowly.
After running multiple iterations of several problems, Troyer and his colleagues found no evidence of a D-Wave Two advantage, they report June 19 in Science. While the machine scaled better than the traditional computer for a small fraction of tasks, says study coauthor Daniel Lidar of USC, it actually did worse for the vast majority of problems.
Colin Williams, D-Wave’s director of business development and a quantum physicist, says that Troyer’s team chose the wrong kinds of problems for the test. “The problems were simply too easy,” Williams says. “They didn’t allow [the quantum algorithm] to show an advantage.” Lidar acknowledges that in hindsight, he and his colleagues would have chosen a different set of problems. But he says that researchers have yet to find any problem that D-Wave’s computer can provably solve faster than a traditional computer as the problem gets harder.
Itay Hen, a USC computer scientist not involved with the new work, is looking for such problems, and he says that he has found some intriguing possibilities. He plans to use the methods detailed in the Science paper to test the most promising candidates.
The mystery should become easier to solve once D-Wave produces a computer with more qubits and more reliable hardware. As D-Wave machines become capable of tackling larger problems, any advantage they have should become more easily distinguishable. “We’re basically redesigning the chip three to four times a year,” Williams says.