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?
So is this finally proof that D-Wave has actually produced a real working quantum processor and isn't just pulling the wool over everyone's eyes? Every other story I've heard of D-Wave is that nobody is allowed to see inside the black box and that nobody can actually get any significant speedup out of using the black box, which of course D-Wave attributed to "poor optimization".
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.
1) Simulated annealing? I guess it's the most direct comparison but that is a terribly inefficient optimizer. I'm not sure what to make of this news in that regard, but it is definitely impressive in any case. Why not run some more advanced particle swarm algorithms in a direct head-to-head on a well-understood problem?
2) How accurate are these results for practical application? I can give you answers REALLY fast, but good luck verifying their accuracy.
1) D-Wave is a specialized quantum computing device which even in theory isn't as powerful as the devices usually hypothesized. It can only run a subset of quantum algorithms. This is what the post is referring to when discussing the interconnectedness of the qubits. 2) The first D-Wave computers had a much smaller number of qubits, and even the 2X doesn't have that many.
Thus, especially with the first generation even the theoretical performance of the D-Wave wasn't much greater than a modern classical CPU. So it was difficult to provide skeptics results which reflected actual quantum computing performance. It looks like the 2X is powerful enough to provide some empirical results to address the skeptics.
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.
The trick was getting them stable, something D-Wave seems to have achieved
Note, this is a single SINGLE core doing ONLY quantum annealing simulation and NOT running a CPU optimized algorithm to get the desired answer AND they ignored a "bug" in the D-Wave "quantum annealing machine" because otherwise it wouldn't be "Fair".
Still seems to be a lot of conditions for it to be so fast. A couple of which I can't even decipher, we could start with the single-core comparision. I have a hard time believing a single core process is the next best choice. Of course the article actually admits to better alternate processes too.
They use that label, pretending that they mean the literal reading but hoping you get confused and think of the technical one.
Thought to be fair, anyone that wants a quantum computer will certainly know that D-Wave's machine is not one upon reading its description.
... of these things
I didn't realize that quantum computers were commercially sold now. I wondered about the price; I wasn't able to find out how much this new computer costs. But per Wikipedia, the first model of this computer sold for about $10 million; and I presume that this new and more powerful version costs more. (The press releases say that this thing computes at extremely low temperatures, so it must include an expensive cooling system.)
Interestingly, the Wikipedia article says that a lot of famous people were dubious about whether these quantum computers would work. A professor from UC Berkeley predicted that the quantum computer would be about as powerful as a cell phone. This result reported by Google would seem to disprove the criticism.
https://en.wikipedia.org/wiki/D-Wave_Systems#Reception
lf(1): it's like ls(1) but sorts filenames by extension, tersely
Way better than fatty stochastic local searching, I can tell you.
I have a hard time believing a single core process is the next best choice.
On 10 cores its still at worst 10^7 times faster, on 100 cores its still at worst 10^6 times faster.
You do not seem to be very bright.
"His name was James Damore."
Provided by the objective function is parallelization yes. Because SA is not.
Annealing? I RTFS and am envisioning repeatedly setting the D-Wave on fire and letting it cool slowly.
After reading the summary on the Google Research Blog...I still get that picture. Not really my field. :-(
Learning HOW to think is more important than learning WHAT to think.
Before we say it's proof, can we at least say that it's faster than traditional processors at solving a particular problem (with the understanding the quantum computers will require different algorithms than linear computers to solve the same problem)?
Help! I'm a slashdot refugee.
And provided you deliberately use a suboptimal classical algorithm (read the paper, where they acknowledge this)
Smells a lot like that big promise. In the backroom is link to Watson...
Shifting goalposts. D-Wave's critics indeed spent years claiming that the machines were hoaxes and offered no quantum effects. Understandable, as extraordinary claims require extraordinary evidence and D-Wave was found wanting for some time. Other critics claimed the entire field of quantum computing was fraudulent--this was a hobby horse of cranks and conspiracy theorists, but unfortunately CS attracts a fair number of those. Google's validation of D-Wave's current technology shuts down both those camps of critics.
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.
No proof at all. This may well just be highly parallelized classical analog computing, the speed-up factor is a bit on the low side. And even if it uses quantum effects, the D-Wave is not a real quantum computer, it is a 1-trick pony and can only do simulated annealing.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
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.
We can say that. We can also remember that the same is true for a host of other computing devices, for example graphics cards, signal processors, specialized analog computers, etc.
This thing is not special, despite what many people believe. It does also not demonstrate that quantum computers are possible.
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).
Wait, are you telling me that nobody is going to put $10M down just to see if they can play their favorite MMOG faster?
Damn, there goes D-Wave's business model ...
You mean, D-Wave, or Google?
They are separate companies, you know, except that the bigger one is a client (and wanna-be competitor) of/to a smaller one.
P.
You claim that it's not a real quantum computer, but your definition of a real quantum computer is a mythical device.
Interesting that it took Google over a year to write a program for this thing, even just a simple one to test its performance.
Google ran the same test on the previous chip, before they committed to buying the machine. This test is for the new ~1K qubit chip.
Other than that, coding for this machine is certainly not straightforward, and it is more an experimental device at this time. Certainly not something that'll give you a price performance advantage over conventional hardware, but as they keep doubling their qubit density every 15 months this may change in the not too distant future.
Google, or D-Wave?
Separate companies, you know...
No, simulated annealing and Monte Carlo are both basically brute force algos for finding a maximum of a function.
So a computer simulation of brute force is slower than a computer designed to do brute force in hardware.
DWave is an analogue computer, if it was a quantum computer (as per Feyman) then the solution would be found effectively instantly and it would always be the best solution since the atoms go through all possible quantum states simultaneously.
It does not always find the best solution, and its faster than a digital computer, but shows no quantum speedup. So no.
Most likely hiding inside is sources of Johnson–Nyquist noise and a configurable circuit for the equation, which would make it an analogue computer.
Keep in mind you wouldn't use simulated annealing to find maxima usually anyway, its basically brute force with a cut off that reduces over time to narrow down the threshold till you hone in on a solution (which may be sub-optimal). Monte-Carlo has a similar issue.
There are better techniques for optimization on digital computers, one was covered quite recently on Slashdot:
http://science.slashdot.org/story/15/10/24/2059238/new-algorithm-provides-huge-speedups-for-optimization-problems
---
As to whether its a quantum computer, no, but their marketing men claim it is:
So marketing:
"Rather than store information as 0s or 1s as conventional computers do, a quantum computer uses qubits – which can be a 1 or a 0 or both at the same time. This “quantum superposition”, along with the quantum effects of entanglement and quantum tunnelling, enable quantum computers to consider and manipulate all combinations of bits simultaneously, making quantum computation powerful and fast. "
If you actually read their paper, you are configuring a circuit which is magnetic in nature:
http://www.dwavesys.com/sites/default/files/Map%20Coloring%20WP2.pdf
It's cooled till it super-conducts, then it's warmed up till the superconductivity collapses, and the circuit settles to a state which must fit the configured constraints defined by the circuit.
It's not always an optimal one though, sometimes its a local maxima.
Except your privates don't have much of a life at all.
Great, just what MS/Apple needs: another paid shill that repeats the same BS ad nauseam.
I never said it was proof, I said "empirical results to address the skeptics".
For the skeptics, there will never be proof because they'll never buy one and disassemble it themselves. And because quantum annealing is fundamentally incapable of achieving the more amazing feats that a universal quantum computer can, there'll always be room for doubt and for moving the goal posts.
But if it's a scam, it's an incredible scam. They're up front about the limitations. Nothing about the claims conflict with known physics or even engineering capability. It's not like the device is an untouchable black box like the Fusion Catalyzer. Even if you can't crack open the tiny component with the qubits, a skilled electrical engineer should be able to satisfy himself that the relevant results are being generated in that one tiny component. If they could squeeze the power of several top-of-the-line Intel Xeons into something that small, that would seem to me more problematic.
The D-Wave people seem to be pragmatic. They asked themselves, "given the current state of the art, what can we achieve?" The result appears to be the D-Wave.
It's limited, of course. But outside some NSA skunkworks team, they've become the most experienced engineers on the planet at building commercial quantum devices. This experience will likely be priceless down the road, and I'm pretty sure that was part of their plan--to have a running start when universal quantum computing becomes practical.
Sounds like something a Luddite would say.
The actual true competition would be a custom FPGA/ASIC. Oh, wait, that's all D-Wave is anyway!
They idea that this is a scam is indeed laughable. Let's forget for a moment that in comparison to the chip they are running a classical chip would have a very different heat signature. The company would also have gone to incredible length to produce niobium lithographic processes to produce fake chips like the one on display in their reception area. And then they would have produced several peer reviewed articles on a technology that doesn't exist.
Then again I know people who believe the Boston marathon bombing was a hoax. The ability of the human mind for self-delusion is apparently limitless.
I have never understood why they don't use the plethora of mixed signal processors that are out there instead of insanely expensive machines. I know they have issues with noise, but I've heard the D-wave needs to do loads of passes on a computation and then use stats to get the "correct" answer.
May as well design a "processor" for each problem and then use it to compute.
I mean, I get that this is how you might eventually get a really really fast "quantum" computer, but there are a lot of alternative approaches that are the definition of quantum computers that should probably get more attention... Fair enough, they're not out of the lab, or even working, but this D-wave really does look a bit flimsy. It has taken ?5? years to find an algorithm that it can process faster...
Please let me know how I'm wrong, this was a post out of curiosity and an attempt to learn.
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
If it is annealing through quantum effects, then it is quantum annealing. It is not simulated annealing.
Because it is actual annealing through quantum effects, like actual annealing with cooling metals.
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.
However a few million dollar is very cheap as insurance for Google.
There is absolutely no firm scientific evidence that anything is actually being computed by so called quantum computers, hence Google hedging its language.
If I remember correctly, their test results for the previous chip were later demonstrated to be rather misleading. The previous chip was indeed faster at solving the particular problem class it was hardwired for than a particular general-purpose solver running on a conventional computer, but someone managed to come up with an optimised solver that was faster than D-Wave at solving the exact problem class D-Wave was made to solve, on a normal general-purpose PC. It's not clear if the same applies to the new chip.
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.
Real hardware runs faster than emulated hardware who'd have guessed?
Build a Man a Fire, and He'll Be Warm for a Day. Set a Man on Fire, and He'll Be Warm for the Rest of His Life.
It wasn't so much the test results that were misleading, then the way it was presented. The same applies to this test i.e. this is not comparing to an optimized solver.
Or am I way off base? Isn't the eventual path of quantum computing to almost simultaneously discover all remaining Bitcoins and render digital encryption useless?
"So is the BSD licence even more 'free' (than GPLv2)? Yes. Unquestionably." --Linus Torvalds (TinyURL.com/2vugzl)
so what you are saying is that it is misleading. How else, other than presentation, would you expect something to be misleading?
Adorbs? Are you fucking serious? Jesus christ, go kill yourself you idiot.
The underlying scientific paper could already be misleading. But in both cases, as far as I can tell, this wasn't the case.
As to the presentation, it's the kind of typical marketing spin that you get anywhere in the IT industry.
If you want the truth and look at the papers, the truth you'll get.
Also remember they got funding from the CIA's tech front company. https://en.wikipedia.org/wiki/... I don't think you scam those guys and get away with it.
https://www.fsf.org/associate/support_freedom
Good point :-)
I am no expert in any of this, but it seems to me that the author of the Shetl-Optimized blog understands this quite well, and explains it as well: http://www.scottaaronson.com/b....
Some in the scientific community considers a quantum computer "real" only if it can solve ALL types of problem. That's hogwash and not very scientific. Any computer that use quantum mechanics to achieve a computation IS a real quantum computer, however limited. By this technical definition, D-Wave is a REAL quantum computer.
There's strong evidence that D-Wave is using quantum mechanics to achieve computation and it's not just an analog computer. The goal-post is now it should have a "speedup" over regular computers as the ultimate proof that it is quantum. But is speed-up a good benchmark for a quantum computer? I think a quantum computer doesn't need speed-up (due to noise/imperfections) to have an advantage over ordinary computers.
I have. There are different critics out there that say different things.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
And there is something wrong with being a Luddite?
Birds are not dinosaur descendants;birds are dinosaurs, for all useful meanings of "birds", "are" and "dinosaurs"
The thing is, it doesn't matter if it gets developed for computing bomb trajectories or for computing consumer spending habits. Technology is fucking awesome and can be re-purposed to make our lives better. Even the atomic bomb gave us insight into construction of a nuclear reactor.
I think you exactly identified the disconnect between the scientists and the business crowd. Scientifically it would be quite significant to see true quantum speed-up, as it'll confirm what theory predicts, i.e. that quantum resources can be harnessed to perform better than any Turing machine or classical computer could.
For the business crowd any practical speed up will do - quantum be damned.
Traveling Salesman Problem is NP-complete, so not only is this machine not going to solve it exactly, neither is Shor's model, even though that one does solve factoring, trashing most of the public-key crypto systems.
But there are lots of heuristics for approximate solutions to TSP, and many of them are "create some complete tour of the network, then randomly perturb it a bunch of times to see if you can get any better results", i.e., simulated annealing, so a quantum annealing machine might turn out to be quite helpful. Until about 5 years ago, Christofides's algorithm, which guarantees a solution that's no worse than 50% longer than the optimum (and usually does better than that) was about the best polynomial-time heuristic there was, so you'd start with that and anneal the results until you were bored.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Have you ever worked in industry. There is a huge amount of "you can't do this until you've done that, that, that, the other, some of this, and then moved those out of the way. You don't do that while learning a technology, you do it after learning the technology.
How long does it take from negotiating for land purchases to the first chips coming out of your fab? 5 years? 8 years?
Birds are not dinosaur descendants;birds are dinosaurs, for all useful meanings of "birds", "are" and "dinosaurs"
This is a comparison of the D-Wave with a simulation of the Quantum Algorithm on a classical computer.
This is nonsense! You really have to compare the best known algorithms for each machine in order to get any meaningful results. Turns out that that the classical algorithm still wipes the floor with the D-Wave on a moderately powerful single core PC when the comparison is fair.
This factor is not even a strong proof that the D-Wave is using quantum effects, just that it simulates them very well.
The truly pathetic thing here is the press, which has not caught on to this misdirection, despite this being the second or third time they have done such worthless comparisons and this being stated clearly in the paper.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Ah quantum computers, the definition of quantum computers being: the psychiatrists trying to understand their own brain, and in the process killing themselves.