What is the Computational Value of Finite-Range Tunneling?

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...

Full description

Saved in:
Bibliographic Details
Published in:Physical review. X 2016-08, Vol.6 (3), p.031015, Article 031015
Main Authors: Denchev, Vasil S., Boixo, Sergio, Isakov, Sergei V., Ding, Nan, Babbush, Ryan, Smelyanskiy, Vadim, Martinis, John, Neven, Hartmut
Format: Article
Language:English
Subjects:
Algorithms
Computer simulation
Connectivity
Graph theory
Heuristic
Microprocessors
Optimization
Processors
Quantum tunnelling
Qubits (quantum computing)
Run time (computers)
Simulated annealing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ∼108 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 ∼108 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.
ISSN:2160-3308
2160-3308
DOI:10.1103/PhysRevX.6.031015