Slashdot is powered by your submissions, so send in your scoop

 



Forgot your password?
typodupeerror
Get HideMyAss! VPN, PC Mag's Top 10 VPNs of 2016 for 55% off for a Limited Time ×
Supercomputing Google Hardware Science Technology

Google Finds D-Wave Machine To Be 10^8 Times Faster Than Simulated Annealing (blogspot.ca) 157

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.
This discussion has been archived. No new comments can be posted.

Google Finds D-Wave Machine To Be 10^8 Times Faster Than Simulated Annealing

Comments Filter:
  • by Anonymous Coward on Tuesday December 08, 2015 @07:48PM (#51085157)

    Just what Google needs: more computer power with which to monetize the details of your private life.

    • Sounds like something a Luddite would say.

      • And there is something wrong with being a Luddite?
        • 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.

          • There is a cart and horse orientation type of error there. The construction and operation of nuclear reactors (starting at a sport ground in Chicago) allowed the collection of the detailed information (neutron capture cross-sections, neutron yield per fission) needed to design a nuclear weapon. Then other nuclear reactors had to be designed to produce the materials needed for the bomb.

            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 othe

    • Real hardware runs faster than emulated hardware who'd have guessed?
  • by Anonymous Coward on Tuesday December 08, 2015 @07:52PM (#51085189)

    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?

    • by ClickOnThis ( 137803 ) on Tuesday December 08, 2015 @08:55PM (#51085447) Journal

      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?

      Given that it's a quantum processor ... yes and no.

      Wait, you said Firefox? Then no.

      • Firefox might run faster, but you might also get webpages from an alternate reality. Of course, that could be good, too, because you might find a better Firefox.

    • by Garridan ( 597129 ) on Tuesday December 08, 2015 @09:38PM (#51085645)
      As somebody who has used a DWave computer... you're asking the wrong question. They cannot run Firefox at any speed. They're analog computers purpose-built to solve extremely specialized optimization problems. But they don't necessarily "solve" problems -- they're likely to find good near-solutions. If you write an LLVM extension for which bitwise operations are computed as a solutions to an Ising spin glass problem, then it'd be waaay faster to run your Firefox port on DWave hardware backend than it would use a simulated annealing backend.

      And that would simply be awful.
    • by cfalcon ( 779563 ) on Tuesday December 08, 2015 @09:54PM (#51085753)

      Sorry, four or more tabs on Firefox is NP Complete. The quantum speed up is only square root of N- not enough for something like that.

    • by gweihir ( 88907 )

      No. These computers cannot be used for general purpose computing. They can only do simulated annealing. Pretty much useless and not even real quantum computers.

      • by daenris ( 892027 ) on Tuesday December 08, 2015 @11:57PM (#51086309)
        You might want to read the article (or even the summary). Google is saying that their results suggest that these computers are NOT just doing simulated annealing, but rather true quantum annealing.
        • You might want to read the article (or even the summary). Google is saying that their results suggest that these computers are NOT just doing simulated annealing, but rather true quantum annealing.

          I can do real annealing with complexity class O(1), with a metal rod, a blow torch, a hammer and a bucket of water.
           

          • by quax ( 19371 )

            If you can do quantum annealing with the same set up I see a Nobel price coming your way :-)

            The q word actually means something.

          • I can do real annealing with complexity class O(1), with a metal rod, a blow torch, a hammer and a bucket of water.

            If you're using the bucket of water, then if you're using iron then you're quenching, not annealing. Not sure why you need the hammer though. Bash the dislocations out of the crystal structure!
             

            • by dfsmith ( 960400 )
              This was posted on Slashdot. The bucket of water is to put out the flames when the poster dropped the blow torch on his Transformer slippers, Googled "foot burn", discovered that keyboards are also flammable, and ran out of the basement. It pays to think ahead and learn from the mistakes of others.
      • They can only do simulated annealing. Pretty much useless and not even real

        That smells like Windows 10

  • 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".

    • 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.

      • by gweihir ( 88907 )

        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.

    • by l2718 ( 514756 ) on Tuesday December 08, 2015 @08:16PM (#51085297)

      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?

      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.

      • by godrik ( 1287354 )

        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.

        • by quax ( 19371 )

          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 ...

      • 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?

        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)?

        • by gweihir ( 88907 )

          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.

      • 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

        • by gweihir ( 88907 )

          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.

          • by serviscope_minor ( 664417 ) on Wednesday December 09, 2015 @05:43AM (#51087177) Journal

            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.

      • by quax ( 19371 ) on Tuesday December 08, 2015 @10:41PM (#51086033)

        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. [wavewatching.net]

        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.

      • by makomk ( 752139 )

        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

    • by gweihir ( 88907 )

      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.

    • by quax ( 19371 ) on Tuesday December 08, 2015 @10:54PM (#51086079)

      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 [wavewatching.net] but throw in hardware error correction. The latter has to be implemented via software on the D-Wave chip [wavewatching.net], 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 [ieee.org] since D-Wave left the stealth mode).

  • by Anonymous Coward on Tuesday December 08, 2015 @07:55PM (#51085201)

    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.

  • by Anonymous Coward

    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.

    • Re:Two questions (Score:4, Informative)

      by Rockoon ( 1252108 ) on Tuesday December 08, 2015 @09:10PM (#51085531)

      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.

      • 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?

        Simulated annealing requires that 1/T be grown logarithmically. In other words, the finite time guarantees are exponential time, just like direct search (i.e. trying every configuration).

        I like simulated annealing, it's simple, easy to implement and easy to apply to a lot of problems. The finite time guarantees are not useful in practice h

    • by gweihir ( 88907 )

      This thing can only do simulated annealing. It is not a quantum computer that can run different algorithms.

  • by l2718 ( 514756 ) on Tuesday December 08, 2015 @08:08PM (#51085259)

    Despite being a computing device that relies on quantum effects, D-Wave's machine is not a "quantum computer [wikipedia.org]" 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.

    • by Anonymous Coward

      This D-Wave thing looks pretty far from a general-purpose computer. I don't claim that I know how it works, but from the description at the corporation's website and the paper draft, it indeed looks like a big chunk of magnet (picturing the Ising model) with programmable coupling among dipolar cells, and a programmable background field. Building that thing may yield many engineering insights and should be lauded as such, but speaking of a computer (or a glorified analog calculator), it probably can't run

      • by quax ( 19371 )

        Yes, it only can optimizing a potential function, but that gives you a lot of mileage, because a huge amount of real world problems can be mapped onto a graph that can be embedded into the Ising spin model.

    • by quax ( 19371 )

      So analog computers then weren't computers either, since they didn't follow Turing's definition?

      It computes with qubits. I think it is perfectly reasonable to call it a special purpose quantum computer.

      • by gweihir ( 88907 )

        It would be far more honest to call is a "limited usefulness single-purpose quantum computing device".

        Incidentally, the Turing definition definition does not apply for analog computers. But a real quantum computer (not this D-Wave con device) _is_ a non-analog computer that can solve discrete problems like factoring numbers.

        • Re: (Score:2, Insightful)

          by quax ( 19371 )

          Look I am quite aware what the gate model quantum computer is and can do, but it is disingenuous to pretend that it is the only game in town, and the only such machine that is allowed to be called a quantum computer.

          Two competing models have been shown to be computationally equivalent, namely quantum cellular automatons and adiabatic quantum computing. The latter you get if the machine can implement an arbitrary Hamiltonian. The D-Wave machine is restricted in that it can only implement spin-glass like Hami

          • you've been posting a lot and seem intent on an assertion that the D-Wave is a "quantum computer" rather than an "analog computer utilizing quantum effect". The thing is, you don't really have anything to back your assertion. You admit that it is very limited and narrowly focused, but seem to believe that those facts are irrelevant because it utilizes a quantum effect.

            Do you accept a flashlight as being a digital computer? It uses an on-off (digital) switch. Is any circuit board a digital computer by virtue

            • by quax ( 19371 )

              I believe in the descriptiveness of language. Does it compute? Yes, in the case of the D-Wave. No, in case of the flash light.

              Does it utilize qubits as basic information processing unite? Yes, again in case of the D-Wave.

              Hence, it is justified to call it a quantum computer. Albeit, it should be qualified as a restricted adiabatic quantum computer, or quantum annealer.

              Until we know what kind of quantum computing architecture will win, it is ludicrous to pretend that there is just one way to do quantum compu

              • by gweihir ( 88907 )

                Sorry, but the flashlight does compute. Its function is an approximation of "battery not empty" AND "lightbulb not broken" AND "switch on" THEN "shine light".

                This should amply demonstrate that your definition of "computer" is so broad it is completely meaningless and hence useless.

                • by quax ( 19371 )

                  Please ask a any first grader if this amounts to the kind of complexity that is meant when people use the word "compute".

                  • by gweihir ( 88907 )

                    It is not. That is my whole point. But even more so, it is not the amount of universality and flexibility expected.

          • by gweihir ( 88907 )

            The problem is that this gets misunderstood. The "Quantum Computer" is the magic machine that can break encryption, compute everything massively faster, etc. The D-Wave is not that machine.

            • by quax ( 19371 )

              I regard this as an opportunity to educate the masses that Quantum Computers are not magical machines, and that the qubits aren't fairy dust. I.e. you can have a machine like D-Wave that utilizes them, yet is still fundamentally limited in what it can do.

      • by l2718 ( 514756 )

        Analog computers are computers, of course -- they just aren't Turing machines. In TCS, "computer" is not the name of any model of computation -- unlike "Turing machine", "register machine", "pushdown automaton" and "quantum computer". So the word "computer" retains its everyday meaning.

        On the other hand, you wouldn't call a device with a stack a "pushdown automaton" unless it actually was a pushdown automaton, right? Similarly, I wouldn't call something a "quantum computer" unless it really corresponds t

  • 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 dubi

    • by Tablizer ( 95088 )

      I didn't realize quantum computers were commercially sold now.

      Only if you observe them being sold.

    • by quax ( 19371 )

      They sold the D-Wave One for about $10M to Lockheed. Figure that'll still get you a current model.

  • 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. :-(

    • by Jeremi ( 14640 )

      Annealing? I RTFS and am envisioning repeatedly setting the D-Wave on fire and letting it cool slowly.

      As I recall, the Pentium 4 chip worked along those same lines.

  • 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.

  • 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 pat

The next person to mention spaghetti stacks to me is going to have his head knocked off. -- Bill Conrad

Working...