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.
Just what Google needs: more computer power with which to monetize the details of your private life.
I'm having trouble visualizing just how fast one of these computers would be.
If I were to buy one of these computers, would it be fast enough to run Firefox at a reasonable speed?
Light bulb found to light up a room over 99% closer to the speed of light as a simulated lightbulb took to run a simulation of the same on our desktop computer.
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."
Provided by the objective function is parallelization yes. Because SA is not.
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.
Actually, it is not. For specialized things, analog computers have always been vastly faster than digital ones. This thing may still turn out to not even be a specialized quantum computer.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
It does not shut anybody down that actually understand the subject matter. (You do not.) This thing is not a quantum computer. It is a special-purpose analog computer that happens to use some quantum effects. And (again) it looks like they have made the comparison as unfair, and hence as meaningless, as possible.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
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).
Balderdash. There is no heating up involved to collapse the superconductivity. Rather the flux is read-out/measured via SQUID and as with any measurement it collapses the quantum mechanical superposition - in this case spin up and down magnetic fluxes in the same Josephson junction.
Never took QM 101, did you?
"the solution would be found effectively instantly ....since the atoms go through all possible quantum states simultaneously."
This is not the way a Quantum Computer works. You invoke the quantum parallel fallacy that that Scott Aaranson devotes an entire book to.
NP complete problems can be encoded in a quantum hamiltonian, but that does not mean at all that an adiabatic quantum computer could find the minima instantaneously.
Generally quantum computer are not expected to find solutions to NP complete problems in poly-linear time.
Sounds like something a Luddite would say.
No, "Quantum Computer" isn't a really well-defined term - it's basically "Sufficiently Advanced Technology Using Handwavium". It's usually used to mean "Quantum Computer that can execute Shor's Algorithm", which can solve a few problems like factoring which would make it extremely disruptive to cryptography. D-Wave has been upfront for a long time about how their computer doesn't do that - it does something much more specialized and handwavy, and this is the first article I've seen that indicates that there's a problem it can actually solve that is significantly faster than conventional computer technology.
And no, a single-core process isn't the fastest way to solve something that's reasonably parallelizable - you can pile up lots of cores and get a proportional speedup (if you don't have dependencies or too much communication overhead.) But if this is 10**8 times as fast as a single core, and the biggest computers out there are around 10**4-10**5 cores and frightfully expensive, that says there's a problem space for which it might be worth some organization's money to actually buy one to use, instead of buying for speculative research.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
You didn't read the GP's post properly. He said that the critics claimed it never showed any quantum effects. Whether it's a full Turing complete computer is immaterial to that. It's a special purpose computational element which does, despite the critics' claims to actually use quantum effects for a very substantial speed up.
It's not a full quantum computer by any stretch of the imagination. I don't entirely understand it, but from my understanding it's not even especially useful unless your cost function fits a -very- specific form.
Nonetheless, it appears that if you have a real thing for ising models the D-Wave can now find a good minima somewhat faster than classical systems.
So yay. That's pretty cool if true. An actual problem solved with quantum computing based techniques faster than classical solutions. It's a start and an interesting step forwards, since so far they've not been able to beat a simulation of their system running on a PC and now they can. If it's really 10^8 times faster, it would even be faster than a custom classical annealing ASIC built on the same area of silicon.
That makes the result interesting, because it's the first time classical computation has ever been beaten, and that's with vast resources invested in it.
SJW n. One who posts facts.
No, this proves that in some applications, D-Wave's machine offers considerable speedup over intentionally de-optimized alternatives. From the blog post:
We should note that there are algorithms, such as techniques based on cluster finding, that can exploit the sparse qubit connectivity in the current generation of D-Wave processors and still solve our proof-of-principle problems faster than the current quantum hardware.
In other words, the current D-Wave machine requires that problems have a particular, very restricted structure and they're only 10^8 times faster when competing with poorly-optimised solvers that don't take advantage of that special structure. if you use a properly optimised conventional solver, the D-Wave machine is actually slower. Google are hoping that future, more densely connected versions that don't exist yet will somehow retain the same speed while conventional code will get bogged down, but those don't exist and may never meet the performance promises that Google are hoping for.