What is the Computational Value of Finite-Range Tunneling?
Top Cited Papers
Open Access
- 1 August 2016
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review X
- Vol. 6 (3), 031015
- https://doi.org/10.1103/physrevx.6.031015
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.
Keywords
This publication has 57 references indexed in Scilit:
- Anderson localization makes adiabatic quantum optimization failProceedings of the National Academy of Sciences of the United States of America, 2010
- Probing Noise in Flux Qubits via Macroscopic Resonant TunnelingPhysical Review Letters, 2008
- A physicist's approach to number partitioningTheoretical Computer Science, 2001
- Random Costs in Combinatorial OptimizationPhysical Review Letters, 2000
- Quantum Annealing of a Disordered MagnetScience, 1999
- Phase Transition in the Number Partitioning ProblemPhysical Review Letters, 1998
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- The Asymptotic Theory of Extreme Order StatisticsTechnometrics, 1990
- Quantum tunnelling in a dissipative systemAnnals of Physics, 1983
- Optimization by Simulated AnnealingScience, 1983