AQC - 2016 Quantum vs. Classical Optimization - A Status Report on the Arms Race

A Google TechTalk, June 27, 2016, presented by Helmut Katzgraber (Texas A&M) ABSTRACT: To date, a conclusive detection of quantum speedup remains elusive. However, recent results from quantum Monte Carlo simulations, as well as the D-Wave 2X quantum annealer show a scaling that clearly outperforms state-of-the-art classical simulated annealing. In this talk an overview of recent benchmarks, as well as attempts to "tickle" any quantumness out of quantum annealing machines is given. Furthermore, we present a generic framework to validate benchmarks and to detect parameter regimes where quantum annealing might excel over classical heuristics. As such, we provide capabilities to aide in the search for the "killer" application for quantum optimization technologies. Finally, an overview of different sequential, non-tailored, as well as specialized tailored classical state-of-the-art algorithms is given. Current quantum annealing technologies must outperform these to claim the crown in the race for quantum speedup. Presented at the Adiabatic Quantum Computing Conference, June 26-29, 2016, at Google's Los Angeles office.