Skip to content
The methodOpen data
Back to the collection

What is the Computational Value of Finite Range Tunneling?

Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov

Show all 8 authors

Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, Hartmut Neven

2015 · arXiv

PhysicsAlgorithmsStatistics & probability
Read the paper
HN score
0
Mentions
4
Readers
4
Months
3
What’s in a score?

From the abstract

Quantum annealing (QA) has been proposed as a quantum enhanced optimization heuristic exploiting tunneling. Here, we demonstrate how finite range tunneling can provide considerable computational advantage. For a crafted problem designed to have tall and narrow energy barriers separating local minima, the D-Wave 2X quantum annealer achieves significant runtime advantages relative to Simulated Annealing (SA). For instances with 945 variables, this results in a time-to-99%-success-probability that is $\sim 10^8$ times faster than SA running on a single processor core. We also compared physical QA with Quantum Monte Carlo (QMC), an algorithm that emulates quantum tunneling on classical processors. We observe a substantial constant overhead against physical QA: D-Wave 2X again runs up to $\sim 10^8$ times faster than an optimized implementation of QMC on a single core. We note that there exist heuristic classical algorithms that can solve most instances of Chimera structured problems in a timescale comparable to the D-Wave 2X. However, we believe that such solvers will become ineffective for the next generation of annealers currently being designed. To investigate whether finite range tunneling will also confer an advantage for problems of practical interest, we conduct numerical studies on binary optimization problems that cannot yet be represented on quantum hardware. For random instances of the number partitioning problem, we find numerically that QMC, as well as other algorithms designed to simulate QA, scale better than SA. We discuss the implications of these findings for the design of next generation quantum annealers.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

4 selected excerpts · 4 total mentions

eghad
Neutral mention · rule
It is indeed, correct. The annealing example I linked is from his team (here's another one with full citation with Martinis at the end there [0]). And if you want further proof that Martinis and the Google Quantum team are pursing quantum annealing look no further than the Adiabtic Quantum Computing Conference that was held this summer where their team held several talks including "Building Quantum Annealer v2.0" [1]. And I didn't touch on your earlier (erroneous) comment on the scientific community's perception of D-Wave, but I think it needs to be said that in actual professional circles the research they're performing isn't met with as much derision as they seem to…
Read the full comment
garner in these more causally informed settings. It's hyped and a difficult subject to understand, so that's fair, but I suggest really informing yourself if you're going to go out there and make the claims you're making. [0] http://research.google.com/pubs/pub44292.html [1] https://aqccreg2016.eventfarm.com/events/index/7fff5387-0000... http://1qbit.com/insights-inside-googles-annual-adiabatic-qu... [2] (Another article reviewing QA with Martinis and team) http://arxiv.org/abs/1512.02206
Original comment D-Wave Founder's New Startup Combines AI, Robots, and Monkeys in Exo-Suits
eveningcoffee
Neutral mention · rule
If we compare single core CPU performance against heavily motivated special solution, then it is not (it does not follow that the same method can be applied in this case, but then again, a better classical algorithm on single core beats the reported quantum result according to the paper (PS. this is in the paper, not on the graph)). Here is comparison http://bitcoin.stackexchange.com/questions/36412/what-is-the... between GPU and ASIC bitcoin mining and here is https://en.bitcoin.it/wiki/Non-specialized_hardware_comparis... GPU and CPU comparison. From this the difference between between GPU and ASIC solution is about 10^4. Google tested against Intel(R) Xeon(R) CPU…
Read the full comment
E5-1650 single core, so it would be roughly 10^2 slower than GPU. So one could say that ASIC solution for bitcoin mining is about 10^6 times faster than single core CPU solution. Million times difference is of course not 100 million times difference, but it is still a lot and then again, alternative classical algorithms would beat current result: Based on the results presented here, one cannot claim a quantum speedup for D-Wave 2X, as this would require that the quantum processor in question outperforms the best known classical algorithm. ... This is because a va- riety of heuristic classical algorithms can solve most in- stances of Chimera structured problems much faster than SA, QMC, and the D-Wave 2X (from http://arxiv.org/abs/1512.02206). I think that this is an important and an interesting result, but it is in my opinion not that impressive that it may appear to look.
Original comment Google, D-Wave, and the case of the factor-10^8 speedup
ivan_ah
Neutral mention · rule
> from the paper http://arxiv.org/abs/1512.02206 : we report the total computational effort of QMC in standard units of time per single core. That's an interesting way to compare quantum and classical computer "substrates" on the same footing: running time. > Based on the results presented here, one cannot claim a quantum speedup [...] as this would require that the quantum processor [to] outperform the best known classical algorithm. This is not the case... because a variety of heuristic classical algorithms can solve most instances of Chimera structured problems much faster than SA, QMC, and the D-Wave 2X So no quantum revolution yet, but potentially for larger problems and when the quantum "substrate" becomes more expressive, we'll see classical heuristics fail and quantum annealing win.
Original comment When can Quantum Annealing win?

Keep following the thread.

More in Physics

More from the same topics.