{"id":192505,"date":"2015-07-21T00:00:00","date_gmt":"2015-07-21T13:07:40","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/advances-in-quantum-algorithms-devices-quantum-versus-classical-annealing\/"},"modified":"2016-07-15T15:25:03","modified_gmt":"2016-07-15T22:25:03","slug":"advances-in-quantum-algorithms-devices-quantum-versus-classical-annealing","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/advances-in-quantum-algorithms-devices-quantum-versus-classical-annealing\/","title":{"rendered":"Advances in Quantum Algorithms & Devices: Quantum versus classical annealing"},"content":{"rendered":"<div class=\"asset-content\">\n<p>I will discuss several recent findings about the computational power of quantum annealing, either on quantum hardware or as \u201csimulated quantum annealing\u201d by quantum Monte Carlo (QMC) simulations on a classical computer. The failure to so far observe quantum speedup on D-Wave Two is in contradiction to previous QMC results that indicated quantum speedup for spin glasses. This apparent contradiction can be resolved by taking the continuous time limit in the QMC simulations. We find that continuous time QMC simulations agree with the behavior of d-Wave and show no speedup for 2D spin glasses. However, QMC simulations with large time steps gain further advantage: they \u201ccheat\u201d by ignoring what happens during a (large) time step, and can thus outperform both simulated quantum annealers and classical annealers. While this is good news for the development of quantum inspired classical optimization algorithms, it further raises the bar for quantum annealers.<\/p>\n<p>A second topic that I will discuss is how to optimally run a quantum annealer. Investigating the behavior of the tails of the distribution of runtimes for very hard instances we find that adiabatically slow annealing is far from optimal. On the contrary, many repeated relatively fast annealing runs can be orders of magnitude faster for hard problems. The intuitive explanation is that hard instances, which are stuck in the \u201cwrong\u201d minimum can be solved faster by perturbing them.<\/p>\n<p>Finally, I will discuss the prospects of quantum annealing outperforming classical annealing on hard optimization problems.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>I will discuss several recent findings about the computational power of quantum annealing, either on quantum hardware or as \u201csimulated quantum annealing\u201d by quantum Monte Carlo (QMC) simulations on a classical computer. The failure to so far observe quantum speedup on D-Wave Two is in contradiction to previous QMC results that indicated quantum speedup for [&hellip;]<\/p>\n","protected":false},"featured_media":199144,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-192505","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/UP-aA4EIZ7Y","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/192505","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/192505\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/199144"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=192505"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=192505"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=192505"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=192505"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=192505"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=192505"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=192505"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=192505"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=192505"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=192505"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}