What is the Computational Value of Finite Range Tunneling

By Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov, Nan Ding, Ryan Babbush, Vadim N. Smelyanskiy, John M. Martinis, Hartmut Neven. 2015

427 citations recorded by the source corpus.

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 $\sim 10^8$ times faster than SA running on a single processor core. We also compared physical QA with Quantum Monte Carlo (QMC), 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 $\sim 10^8$ times faster than an optimized implementation of QMC on a single core. We note that there exist heuristic classical algorithms that can solve most instances of Chimera structured problems in a timescale comparable to the D-Wave 2X. However, we believe that such solvers will become ineffective for the next generation of annealers currently being designed. 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 QMC, as well as other algorithms designed to simulate QA, scale better than SA. We discuss the implications of these findings for the design of next generation quantum annealers.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/490e058cdc46ba27ba173cd29b3e1ed7017287f4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

A Survey on Quantum Channel Capacities (2018, background): “The superposition nature of qubits leads to the advent of powerful quantum computing, which is in some cases proved be 100 millions times faster than the classical computer [131].”
Adiabatic Quantum Computing (2016, methodology): “One approach has been to develop “tunneling gadgets”, i.e., small toy Hamiltonians that exhibit tunneling (Boixo et al., 2016), and use these gadgets to construct larger problems (Denchev et al., 2016).”
Quantum annealing for industry applications: introduction and review (2021, neutral): “, [43, 71, 84, 117] and references therein for more detailed discussions).”
Quantum information processing with superconducting circuits: a review (2016, background): “• Even more efficient classical optimisation algorithms exist for these problems (mentioned in [111]), which outperform the current DWave 2X device for most problem instances [498, 500, 501].”
Traffic Flow Optimization Using a Quantum Annealer (2017, background): “It has also been shown how the quantum properties of qubits play a role in the computation of solutions in both sampling and optimization tasks (O’Gorman et al., 2015; Perdomo-Ortiz et al., 2015; Rieffel et al., 2015; Venturelli et al., 2015a,b; Denchev et al., 2016; Los Alamos National Laboratory, ”