Jun 20, 2014
A team of quantum-computing experts in the US and Switzerland has published a paper in Science that casts doubt over the ability of the D-Wave Two quantum processor to perform certain computational tasks. The paper, which first appeared as a preprint earlier this year, concludes that the processor – built by the controversial Canadian firm D-Wave Systems – offers no advantage over a conventional computer when it is used to solve a benchmark computing problem.
While the researchers say that their results do not rule out the possibility that the processor can outperform conventional computers when solving other classes of problems, their work does suggest that evaluating the performance of a quantum computer could be a much trickier task than previously thought. D-Wave has responded by saying that the wrong benchmark problem was used to evaluate its processor, while the US–Swiss team now intends to do more experiments using different benchmarks.
D-Wave Two is the second generation of quantum processors sold by D-Wave Systems and one of the devices is owned by NASA, Google and the Universities Space Research Association. The company has also sold a system – claimed to be the world's first commercially available quantum computer – to Lockheed Martin. The tests on D-Wave Two were carried out by Matthias Troyer and colleagues at ETH Zurich, the University of Southern California (USC), the University of California Santa Barbara, Google and Microsoft.
Containing 512 quantum bits (qubits), the D-Wave Two processor was designed specifically to perform a process called "quantum annealing", which is a technique for finding the global minimum of a complicated mathematical function. Unlike "conventional" quantum computers – which are kept in a fragile quantum state throughout the calculation – quantum annealing involves making a transition from a quantum to classical system. As a result, D-Wave's approach might be more immune to noise, which can destroy conventional quantum calculations. However, a quantum annealing processor is not a universal computer like a PC and cannot be programmed to perform a range of tasks.
Fiendishly difficult calculation
Troyer's team tested the processor by using it to solve a particularly difficult task from condensed-matter physics involving "Ising spin glasses". A spin glass is a magnetic material in which the individual magnetic moments – or spins – interact with each other and are also located randomly throughout the material. This is unlike conventional models of magnetic materials, in which the spins are arranged on a regular lattice and tend to all point in specific directions. Instead, the spin glass has an extremely complicated spin configuration that is fiendishly difficult to calculate for large numbers of spins. "Ising spin-glass problems are the 'native' problem that the [D-Wave Two] is designed for," Troyer explained to physicsworld.com.
To evaluate the performance of D-Wave Two, the team measured how long it took the processor to solve an Ising spin-glass problem and compared this with the time it takes with a conventional, classical computer. This ratio, known as the "quantum speed-up", is expected to be around one for small problems – meaning classical devices can do the job just as well – but it should grow in size as the problem becomes larger. In its test, the team carried out lots of quantum and classical simulations on different spin glasses, in which the number of spins and the interaction strengths were varied systematically.
No speed-up found
The results, however, reveal no clear evidence of speed-up. While the D-Wave Two processor was sometimes 10 times faster than the classical computer, it was also sometimes more than 100 times slower. Troyer and colleagues put forth several possible explanations for why speed-up was not seen. One is that although D-Wave Two functions as a quantum processor, quantum annealing offers no advantage over classical methods. Another possibility is that noise or other operational problems mean that the device is not operating as a quantum processor.
A third, intriguing prospect put forth by Troyer and colleagues is that speed-up could still be seen when D-Wave Two is used to solve other types of problems, even if it was not observed in the current test. Indeed, D-Wave itself claims that research done by a team led by Helmut Katzgraber at Texas A&M University suggests that Ising spin-glass problems cannot be solved quicker using quantum annealing. Moreover, Jeremy Hilton – D-Wave's vice-president for processor development – points out more recent work done by Itay Hen of USC and colleagues, which – he says – shows that "a new benchmark has demonstrated better performance of the D-Wave 512 qubit processor over the simulated annealing algorithm developed by Troyer et al."
"Katzgraber argues that 3D spin glasses may be better test cases that 'might' be better suited," says Troyer. "We have found a way to implement such problems and are testing it now. Researchers at Google and NASA are also searching if there are problem classes that may show quantum speed-up."
Troyer adds that the fundamental importance of the work presented in Science is that it describes a method for measuring quantum speed-up for devices with unknown potential, such as the D-Wave devices. With physicists worldwide focused on making larger and more complex quantum processors, such measurement techniques will become increasingly important.
The benchmark testing is described in Science.