Slashdot Mirror
Google Finds D-Wave Machine To Be 10^8 Times Faster Than Simulated Annealing (blogspot.ca)
An anonymous reader sends this report form the Google Research blog on the effectiveness of D-Wave's 2X quantum computer:
We found that for problem instances involving nearly 1000 binary variables, quantum annealing significantly outperforms its classical counterpart, simulated annealing. It is more than 10^8 times faster than simulated annealing running on a single core. We also compared the quantum hardware to another algorithm called Quantum Monte Carlo. This is a method designed to emulate the behavior of quantum systems, but it runs on conventional processors. While the scaling with size between these two methods is comparable, they are again separated by a large factor sometimes as high as 10^8.
A more detailed paper is available at the arXiv.
Despite being a computing device that relies on quantum effects, D-Wave's machine is not a "quantum computer" as that term is defined by computer scientists.
Commendably, Google's blog post calls the device a "quantum annealer", rejecting D-Wave's self-label of "quantum computer" which is a misleading marketing ploy. Perhaps if D-Wave's device had come before theoretical CS researcher defined their computational model, the term "quantum computer" would have taken a different meaning, but as things stand the meaning of "quantum computer" was fixed well before D-Wave was founded.
This finally proves that, in some applications, D-Wave's machine offers considerable speedup over alternatives. It also confirms that D-Wave's machine uses quantum effects to speed up computation, but this point was never in dispute.
However, the term "quantum computer" has a very specific meaning (just like "Turing machine" has a specific meaning), and D-Wave's machine isn't a quantum computer. They use that label, pretending that they mean the literal reading but hoping you get confused and think of the technical one.
Simulated annealing? I guess it's the most direct comparison but that is a terribly inefficient optimizer.
Do you know of any algorithms that are more efficient while still offering the same finite-time guarantee (of finding the optimal solution) that simulated annealing does?
This is one of the key points. More efficient methods are frequently more efficient because they wont search the entire space no matter how long you let them run. While simulated annealing wont search the entire space in practice, the operator has control over how much of the space gets sampled by altering the rate of convergence (the "cooling" rate)
The "more efficient method" that you mentioned, particle swarms, is only more efficient when such a finite-time guarantee is left behind. The finite-time guaranteed version of particle swarms is not more efficient, instead being equally as efficient.
"His name was James Damore."
It also confirms that D-Wave's machine uses quantum effects to speed up computation, but this point was never in dispute.
Boy, are you wrong on that count.
As to the term quantum computer. It computes with qubits, it's not universal, but in that it resembles some of the analog computers of yore.
D-Wave has published about chip architecture for quite some time now. You must be frequenting the wrong science sites.
Google for instance is following their overall approach but throw in hardware error correction. The latter has to be implemented via software on the D-Wave chip, which in essence is nothing more than a bunch of coupled josephson junctions (I heinously oversimplify of course, but there are now dozens of publication like this since D-Wave left the stealth mode).