Stories
Slash Boxes
Comments

SoylentNews is people

posted by martyb on Friday December 11 2015, @01:23AM   Printer-friendly
from the making-progress dept.

Google Research Blog has reported a 100 million times (108) speedup when using D-Wave quantum annealing systems to solve certain optimization problems versus a single classical processor core. Note that D-Wave systems are said to cost $10 million, far more than a single core:

During the last two years, the Google Quantum AI team has made progress in understanding the physics governing quantum annealers. We recently applied these new insights to construct proof-of-principle optimization problems and programmed these into the D-Wave 2X quantum annealer that Google operates jointly with NASA. The problems were designed to demonstrate that quantum annealing can offer runtime advantages for hard optimization problems characterized by rugged energy landscapes.

We found that for problem instances involving nearly 1000 binary variables, quantum annealing significantly outperforms its classical counterpart, simulated annealing. It is more than 108 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 108.

[More after the break.]

While these results are intriguing and very encouraging, there is more work ahead to turn quantum enhanced optimization into a practical technology. The design of next generation annealers must facilitate the embedding of problems of practical relevance. For instance, we would like to increase the density and control precision of the connections between the qubits as well as their coherence. Another enhancement we wish to engineer is to support the representation not only of quadratic optimization, but of higher order optimization as well. This necessitates that not only pairs of qubits can interact directly but also larger sets of qubits. Our quantum hardware group is working on these improvements which will make it easier for users to input hard optimization problems.

From the arXiv paper "What is the Computational Value of Finite Range Tunneling?":

To illustrate how dramatic this effect can be, when we ran smaller instances of the weak-strong cluster networks on the older D-Wave Vesuvius chips we predicted that at 1000 variables DWave would be 104 times faster than [simulated annealing]. In fact, we observed a speedup of more than a factor of 108.

Update: Experts, including longtime D-Wave critic Scott Aaronson, are not impressed with Google's claims. Perhaps Rose's Law will take care of that. Via NextBigFuture.


Original Submission

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 2) by Covalent on Friday December 11 2015, @02:03AM

    by Covalent (43) on Friday December 11 2015, @02:03AM (#274759) Journal

    Cost is irrelevant to a company like Google, particularly when this much of a speed-up is possible. There are a huge number of problems that Google would like to tackle that it simply can't right now. But 8 zeros is a game changer.

    It might even be possible to pass the Turing test with something like this. Right now, computers can guess at the meaning of a sentence (watch Watson playing Jeopardy), but they're pretty bad at it. Part of the problem is that they simply cannot search and analyze enough information fast enough to make sense of the words they're reading in a reasonable time. But conducting one hundred million times as many calculations in that same 2 seconds might be enough to make it happen.

    Exciting stuff.

    --
    You can't rationally argue somebody out of a position they didn't rationally get into.
    Starting Score:    1  point
    Karma-Bonus Modifier   +1  

    Total Score:   2  
  • (Score: 0) by Anonymous Coward on Friday December 11 2015, @02:11AM

    by Anonymous Coward on Friday December 11 2015, @02:11AM (#274764)

    The human brain doesn't need quantum annealing or whatever to pass a Turing test.

    1)- Why would quantum annealing help? This seems to be in at least large part a software problem.
    2)- This isn't a general purpose speedup, why would it help with AI? The problems quantum computers are meant to help with aren't ones that classical computing (including brains) are good at, so why would the quantum annealing thing be some special exception?

    • (Score: 4, Informative) by takyon on Friday December 11 2015, @02:26AM

      by takyon (881) <reversethis-{gro ... s} {ta} {noykat}> on Friday December 11 2015, @02:26AM (#274769) Journal

      We need GPUs because they do certain tasks faster than CPUs. It's the same with quantum computing. Whether that's useful is another question.

      There seems to be machine learning applications [medium.com] for quantum computing, which explains why Google is interested. Quantum computing could be a shortcut to making a brain-like system.

      I can't tell you what the more limited quantum annealing is useful for, but D-Wave has done enough to convince Google, NASA, Lockheed Martin, University of Southern California, 1QB Information Technologies [wikipedia.org], and recently Los Alamos National Laboratory [hpcwire.com].

      --
      [SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
      • (Score: 2) by bzipitidoo on Friday December 11 2015, @03:40AM

        by bzipitidoo (4388) on Friday December 11 2015, @03:40AM (#274793) Journal

        There has been some controversy around D-Wave, doubts that their hardware really does quantum computing, and isn't just so much snake oil. Quantum computing is the cold fusion of computer science. Maybe they've really done it. If so, buckle up, it will be revolutionary.

        For starters, the RSA public key encryption will no longer be secure, as a quantum computer can factor huge integers quickly, That is no wussy 10^8 speedup either (trust the media to blunder the reporting of that detail). it's a speed up in algorithmic time. With classical computers there is no known way to factor a big compound integer quickly, it has to be done with brute force methods. none of which get anywhere close to log n time. I don't recall if Diffie-Hellman will also be broken, but I think so.

        Whether the infamous NP complete problems can be solved quickly is not known. No one knows whether a quantum computer can do it. Most computer scientists strongly suspect NP > P, but no one has been able to prove it. The thinking is that QP, the set of problems that can be solved in polynomial time by a quantum algorithm, lies somewhere between NP and P, that is NP > QP > P.

        • (Score: 2) by takyon on Friday December 11 2015, @04:06AM

          by takyon (881) <reversethis-{gro ... s} {ta} {noykat}> on Friday December 11 2015, @04:06AM (#274798) Journal

          D-Wave is admittedly not a "universal quantum computer". It is a "quantum annealer", capable of solving a much narrower class of problems. It won't be able to break RSA.

          The true universal quantum computers may begin to rocket from a handful of qubits to thousands and millions in a very short time. Why? Because they have now been built out of silicon [soylentnews.org]. If they can be built using existing fabs, the same techniques used to make chips with billions of transistors will be able to make chips with millions of qubits.

          it's a speed up in algorithmic time

          When you solve an exponential, you get... a number. 108 is the number in this story, and D-Wave currently has around 1,152 qubits. What happens when D-Wave has 4,096 or 8,192 qubits? It remains to be seen if it gets faster for the same problem sizes, but bigger problem sizes could be tackled far faster than classical computers.

          --
          [SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
          • (Score: 2) by linuxrocks123 on Friday December 11 2015, @04:46AM

            by linuxrocks123 (2557) on Friday December 11 2015, @04:46AM (#274808) Journal

            Have they solved the decoherence problem yet? No? Then I don't care if they're building them out of rose petals and unicorn farts. They're not getting anywhere.

        • (Score: 0) by Anonymous Coward on Friday December 11 2015, @05:57AM

          by Anonymous Coward on Friday December 11 2015, @05:57AM (#274824)

          I don't recall if Diffie-Hellman will also be broken [by a quantum computer], but I think so.

          Shor's algorithm works for both integer factorization and and discrete logarithms (upon which the security of Diffie-Hellman is based). So it will break Diffie-Hellman too. The two problems are widely believed to be equivalent (polynomial-time reducible to each other), but as far as I know this remains an open question in mathematics.

        • (Score: 4, Informative) by SubiculumHammer on Friday December 11 2015, @06:01AM

          by SubiculumHammer (5191) on Friday December 11 2015, @06:01AM (#274826)

          http://www.scottaaronson.com/blog/?p=2555 [scottaaronson.com]

          Has a great post talking about what has and hasn't been shown in the new Google paper.

          • (Score: 2) by bzipitidoo on Friday December 11 2015, @04:09PM

            by bzipitidoo (4388) on Friday December 11 2015, @04:09PM (#275006) Journal

            Yes, as I thought. Thanks for the informative link. Ample reason for caution about what D-Wave has really accomplished. They have NOT demonstrated an asymptotic speedup over the best classical algorithms. It's still quite possible, even probable, just that D-Wave has not really done it, not yet. Perhaps D-Wave will manage it soon, or perhaps other groups will do it.

            Fantastic claims should be treated with great caution. Investors, stake-holders, and managers can exert a lot of unfair pressure on scientists and engineers, make it very painful to stay honest. The pain of telling them what they want to hear when it is a lie is worse, if not so immediate. It is extremely important for a researcher working for a business to have means to resist. Even when they do, management may distort, twist, and outright lie about what researchers really said. Add to that media's penchant to dramatize, and we end up with these fantastic claims that if true, would profoundly alter things. Compared to all that, Publish or Perish isn't so bad.

            Steve Jurvetson, huh? I remember him, though I doubt he remembers me.