What is the Computational Value of Finite Range Tunneling?
arXiv:1512.02206 · doi: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 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 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.
arXiv comment17 pages, 13 figures. Edited for clarity, in part in response to comments. Added link to benchmark instances
References in corpus (40)
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum random walks - an introductory overview
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing and Analog Quantum Computation
- Defining and detecting quantum speedup
- Experimental signature of programmable quantum annealing
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Anderson localization casts clouds over adiabatic quantum optimization
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Quantum Optimization of Fully-Connected Spin Glasses
- Phase Transition in the Number Partitioning Problem
- Entanglement in a quantum annealing processor
- Experimental Demonstration of a Robust and Scalable Flux Qubit
- Probing for quantum speedup in spin glass problems with planted solutions
- Optimized simulated annealing for Ising spin glasses
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Random Costs in Combinatorial Optimization
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Reexamining classical and quantum models for the D-Wave One processor
- Quantum Annealing Correction with Minor Embedding
- A physicist's approach to number partitioning
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Probing Noise in Flux Qubits via Macroscopic Resonant Tunneling
- The many-body localized phase of the quantum random energy model
- MAX 2-SAT with up to 108 qubits
- Macroscopic Resonant Tunneling in the Presence of Low Frequency Noise
- Maximum-Entropy Inference with a Programmable Annealer
- Reexamination of the evidence for entanglement in the D-Wave processor
- Heavy tails in the distribution of time-to-solution for classical and quantum annealing
- From local to global ground states in Ising spin glasses
- Open system quantum annealing in mean field models with exponential degeneracy
- Quantum and Classical in Adiabatic Computation
- Hearing the Shape of the Ising Model with a Programmable Superconducting-Flux Annealer
- Application of the discrete Wentzel-Kramers-Brillouin method to spin tunneling
- Phase transition and landscape statistics of the number partitioning problem
Cited by in corpus (141)
- A Quantum Engineer's Guide to Superconducting Qubits
- Noisy intermediate-scale quantum (NISQ) algorithms
- Adiabatic Quantum Computing
- Quantum information processing with superconducting circuits: a review
- Quantum optimization using variational algorithms on near-term quantum devices
- Perspectives of quantum annealing: Methods and implementations
- A blueprint for demonstrating quantum supremacy with superconducting qubits
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Quantum Annealing for Industry Applications: Introduction and Review
- A Survey on Quantum Channel Capacities
- Quantum computing for finance
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Efficient partition of integer optimization problems with one-hot encoding
- Expanding the horizon of automated metamaterials discovery via quantum annealing
- Nonnegative/binary matrix factorization with a D-Wave quantum annealer
- Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
- Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Quantum Computation Based on Quantum Adiabatic Bifurcations of Kerr-Nonlinear Parametric Oscillators
- Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
- Coherent coupled qubits for quantum annealing
- Modernizing Quantum Annealing using Local Searches
- Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
- Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
- Quantum bits with Josephson junctions
- Leveraging Quantum Annealing for Large MIMO Processing in Centralized Radio Access Networks
- Scaling and diabatic effects in quantum annealing with a D-Wave device
- Quantum Image Matching
- Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
- Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
- A deceptive step towards quantum speedup detection
- Autonomous Probabilistic Coprocessing with Petaflips per Second
- Dissipation in adiabatic quantum computers: Lessons from an exactly solvable model
- Multilevel Combinatorial Optimization Across Quantum Architectures
- Global warming: Temperature estimation in annealers
- Building an iterative heuristic solver for a quantum annealer
- Boundaries of quantum supremacy via random circuit sampling
- Open quantum generalisation of Hopfield neural networks
- Non-ergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
- Scalable Emulation of Sign-ProblemFree Hamiltonians with Room Temperature p-bits
- Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
- Low depth mechanisms for quantum optimization
- Readiness of Quantum Optimization Machines for Industrial Applications
- Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Challenges of variational quantum optimization with measurement shot noise
- Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
- Model Predictive Control for Finite Input Systems using the D-Wave Quantum Annealer
- Adiabatic optimization versus diffusion Monte Carlo
- Why and when is pausing beneficial in quantum annealing?
- Quantum Monte Carlo tunneling from quantum chemistry to quantum annealing
- Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
- Quantum neural networks to simulate many-body quantum systems
- An Application of Quantum Annealing Computing to Seismic Inversion
- Solving NP-hard problems with bistable polaritonic networks
- The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
- Boosting quantum annealer performance via sample persistence
- Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
- Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
- On the optimal working point in dissipative quantum annealing
- Scaling Advantage in Approximate Optimization with Quantum Annealing
- Adiabatic Quantum Search in Open Systems
- Fast optimization algorithms and the cosmological constant
- Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks
- Quantum adiabatic machine learning with zooming
- Towards Hybrid Classical-Quantum Computation Structures in Wirelessly-Networked Systems
- Nested Quantum Annealing Correction at Finite Temperature: -spin models
- Optimally Stopped Optimization
- Benchmarking quantum annealing dynamics: the spin-vector Langevin model
- Optimal working point in digitized quantum annealing
- Assessment of Quantum Annealing for the Construction of Satisfiability Filters
- Networked Quantum Services
- Energy landscapes of combinatorial optimization in Ising machines
- Practical designs for permutation symmetric problem Hamiltonians on hypercubes
- Breakdown of the weak coupling limit in quantum annealing
- Heterogeneous Quantum Computing for Satellite Constellation Optimization: Solving the Weighted K-Clique Problem
- Quantum optics and frontiers of physics: The third quantum revolution
- Possible Ergodic-nonergodic regions in the quantum Sherrington-Kirkpatrick spin glass model and quantum annealing
- Viewing Vanilla Quantum Annealing Through Spin Glasses
- Noise Dynamics of Quantum Annealers: Estimating the Effective Noise Using Idle Qubits
- Quantum Isomer Search
- Mediator assisted cooling in quantum annealing
- Classical simulation and theory of quantum annealing in a thermal environment
- Mean-Field Solution of the Weak-Strong Cluster Problem for Quantum Annealing with Stoquastic and Non-Stoquastic Catalysts
- Phase transition of Frustrated Ising model via D-wave Quantum Annealing Machine
- Effectiveness of quantum annealing for continuous-variable optimization
- Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA
- A Josephson Parametric Oscillator-Based Ising Machine
- Accuracy of the adiabatic-impulse approximation for closed and open quantum systems
- Defence against adversarial attacks using classical and quantum-enhanced Boltzmann machines
- Quantum accelerated approach to the thermal state of classical spin systems with applications to pattern-retrieval in the Hopfield neural network
- A comparison between D-wave and a classical approximation algorithm and a heuristic for computing the ground state of an Ising spin glass
- On the dynamics of Simulated Quantum Annealing in random Ising chains
- Towards Transfer Learning for Large-Scale Image Classification Using Annealing-based Quantum Boltzmann Machines
- Exploration of new chemical materials using black-box optimization with the D-wave quantum annealer
- Unfolding as Quantum Annealing
- Tunneling in projective quantum Monte Carlo simulations with guiding wave functions
- Dynamics of Order Parameters of Non-stoquastic Hamiltonians in the Adaptive Quantum Monte Carlo Method
- Quadrature Histograms in Maximum Likelihood Quantum State Tomography
- Balancing coherent and dissipative dynamics in a central-spin system
- A small-world search for quantum speedup: How small-world interactions can lead to improved quantum annealer designs
- Quantum annealing in spin-boson model: from a perturbative to a ultrastrong mediated coupling
- Efficient quantum and simulated annealing of Potts models using a half-hot constraint
- Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
- Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
- Forbidden subspaces for level-1 QAOA and IQP circuits
- Reconstructing the ideal results of a perturbed analog quantum simulator
- Dissipative failure of adiabatic quantum transport as a dynamical phase transition
- Verifying the output of quantum optimizers with ground-state energy lower bounds
- Incentivising Demand Side Response through Discount Scheduling using Hybrid Quantum Optimization
- C-Nash: A Novel Ferroelectric Computing-in-Memory Architecture for Solving Mixed Strategy Nash Equilibrium
- Quantum computing for genomics: conceptual challenges and practical perspectives
- Dynamics of strongly coupled disordered dissipative spin-boson systems
- Difference between quantum annealing by imaginary-time and real-time Schrödinger equation of Grover's search
- Annealing for prediction of grand canonical crystal structures: Efficient implementation of n-body atomic interactions
- Load Balancing For High Performance Computing Using Quantum Annealing
- Optimization with delay-induced bifurcations
- Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
- Understanding the physics of D-Wave annealers: From Schrödinger to Lindblad to Markovian Dynamics
- Propagation of quantum fluctuations in quantum Ising model
- Mapping State Transition Susceptibility in Quantum Annealing
- Exponential speedup of incoherent tunneling via dissipation
- Quantum Phase Transition in Fully-Connected Quantum Wajnflasz-Pick Model
- A Lattice-Reduction Aided Vector Perturbation Precoder Relying on Quantum Annealing
- A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing---Abridged Version
- Posiform Planting: Generating QUBO Instances for Benchmarking
- Using copies to improve precision in continuous-time quantum computing
- Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
- Impact of nonlocal electrodynamics on flux noise and inductance of superconducting wires
- Absence of small-world effects at the quantum level and stability of the quantum critical point
- Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
- Correspondence between excited energy eigenstates and local minima of energy landscape in quantum spin systems
- Transfer Learning for Deep-Unfolded Combinatorial Optimization Solver with Quantum Annealer
- Calculating Nash Equilibrium on Quantum Annealers
- Subsampling Factorization Machine Annealing
- The Perturbed Ferromagnetic Chain: A Tuneable Test of Quantum Hardness in the Transverse-Field Ising Model
- Classical Simulated Annealing Using Quantum Analogues
- Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
- Quantum-inspired search method for low-energy states of classical Ising Hamiltonians
- Lack of a thermodynamic finite-temperature spin-glass phase in the two-dimensional randomly-coupled ferromagnet
- Solving the Turbine Balancing Problem using Quantum Annealing