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 times faster than SA running on a single processor core. We also compare physical QA with the quantum Monte Carlo algorithm, 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 times faster than an optimized implementation of the quantum Monte Carlo algorithm on a single core. We note that there exist heuristic classical algorithms that can solve most instances of Chimera structured problems in a time scale comparable to the D-Wave 2X. However, it is well known that such solvers will become ineffective for sufficiently dense connectivity graphs. 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 algorithms designed to simulate QA scale better than SA. We discuss the implications of these findings for the design of next-generation quantum annealers.
5 More- Received 4 March 2016
DOI:https://doi.org/10.1103/PhysRevX.6.031015
This article is available under the terms of the Creative Commons Attribution 3.0 License. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.
Published by the American Physical Society
Physics Subject Headings (PhySH)
Popular Summary
A better understanding of the physics governing quantum annealers has long been a goal of the scientific community. Here, we apply new insights to construct proof-of-principle optimization problems and program them into the D-Wave 2X quantum annealer. These problems are designed to demonstrate quantum runtime advantages for hard-optimization problems characterized by rugged energy landscapes. For instances involving nearly 1000 binary variables, we find that quantum annealing outperforms single-core simulated annealing by a factor of . While simulated annealing requires that energy barriers be climbed over, quantum annealing allows barriers to be tunneled through. We also compare the D-Wave 2X quantum annealer with quantum Monte Carlo, which emulates the behavior of quantum systems on classical processors. While the scaling with size is similar to that of D-Wave, the runtimes are differentiated again by large factors (i.e., up to ) because of the overhead of simulating quantum tunneling classically.
We note that there are algorithms—such as techniques based on cluster finding—that can exploit the almost-planar connectivity in the current generation of D-Wave processors and still solve problems faster than D-Wave. However, with sufficiently denser connectivity of next-generation annealers, we expect that those methods will become ineffective. Even though our results are encouraging, turning quantum-enhanced optimization into a practical technology requires more work. Next-generation annealers should increase the coherence, density, and control precision of qubits and make it possible to embed higher-order problems of practical relevance. Such problems stand to benefit from quantum optimization because quantum tunneling facilitates traversing tall and narrow barriers in the energy landscape.
We are optimistic that the significant runtime gains we have recovered will carry over to commercially relevant problems that occur in tasks relevant to machine intelligence.