What is the Computational Value of Finite Range Tunneling?
Venue
Physical Review X, vol. 6 (2016), pp. 031015
Publication Year
2016
Authors
Vasil Denchev, Sergio Boixo, Sergei Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, Hartmut Neven
BibTeX
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 ~1e8 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 ~ 1e8 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.
