Demonstration of a scaling advantage for a quantum annealer over simulated annealing

Abstract

The observation of an unequivocal quantum speedup remains an elusive objective for quantum computing. The D-Wave quantum annealing processors have been at the forefront of experimental attempts to address this goal, given their relatively large numbers of qubits and programmability. A complete determination of the optimal time-to-solution (TTS) using these processors has not been possible to date, preventing definitive conclusions about the presence of a scaling advantage. The main technical obstacle has been the inability to verify an optimal annealing time within the available range. Here we overcome this obstacle and present a class of problem instances for which we observe an optimal annealing time using a D-Wave 2000Q processor over a range spanning up to more than $2000$ qubits. This allows us to perform an optimal TTS benchmarking analysis and perform a comparison to several classical algorithms, including simulated annealing, spin-vector Monte Carlo, and discrete-time simulated quantum annealing. We establish the first example of a scaling advantage for an experimental quantum annealer over classical simulated annealing: we find that the D-Wave device exhibits certifiably better scaling than simulated annealing, with $95\%$ confidence, over the range of problem sizes that we can test. However, we do not find evidence for a quantum speedup: simulated quantum annealing exhibits the best scaling by a significant margin. Our construction of instance classes with verifiably optimal annealing times opens up the possibility of generating many new such classes, paving the way for further definitive assessments of scaling advantages using current and future quantum annealing devices.

26 pages, 22 figures. v2: Updated benchmarking results with additional analysis. v3: Updated to published version

References in corpus (20)

• Probing many-body dynamics on a 51-atom quantum simulator
• Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit Quantum Simulator
• Quantum Computational Supremacy
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Experimental implementation of an adiabatic quantum optimization algorithm
• Stochastic series expansion method for quantum Ising models with arbitrary interactions
• Quantum annealing versus classical machine learning applied to a simplified computational biology problem
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• Simple Glass Models and their Quantum Annealing
• Reexamining classical and quantum models for the D-Wave One processor
• Temperature scaling law for quantum annealing optimizers
• Quantum Monte Carlo tunneling from quantum chemistry to quantum annealing
• The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
• Off-Diagonal Expansion Quantum Monte Carlo
• Advantages of Unfair Quantum Ground-State Sampling
• Macroscopic quantum tunneling and quantum-classical phase transitions of the escape rate in large spin systems
• Quantum trajectories for time-dependent adiabatic master equations
• Optimally Stopped Optimization
• Error Suppression for Hamiltonian Quantum Computing in Markovian Environments
• Ground-state statistics from annealing algorithms: Quantum vs classical approaches

Cited by in corpus (103)

• A Quantum Engineer's Guide to Superconducting Qubits
• Perspectives of quantum annealing: Methods and implementations
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
• SU(2) lattice gauge theory on a quantum annealer
• Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
• Multiclass classification using quantum convolutional neural networks with hybrid quantum-classical learning
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Benchmarking Quantum Annealing Controls with Portfolio Optimization
• Demonstration of nonstoquastic Hamiltonian in coupled superconducting flux qubits
• Demonstration of algorithmic quantum speedup
• QFold: Quantum Walks and Deep Learning to Solve Protein Folding
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Boundaries of quantum supremacy via random circuit sampling
• Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability
• Scalable Emulation of Sign-Problem$-$Free Hamiltonians with Room Temperature p-bits
• Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
• Challenges of variational quantum optimization with measurement shot noise
• Scaling overhead of embedding optimization problems in quantum annealing
• Two-parameter counter-diabatic driving in quantum annealing
• Why and when is pausing beneficial in quantum annealing?
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• Quantum annealing for systems of polynomial equations
• Accelerated Quantum Monte Carlo with Probabilistic Computers
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• Charged particle tracking with quantum annealing-inspired optimization
• An Application of Quantum Annealing Computing to Seismic Inversion
• Improved Boltzmann machines with error corrected quantum annealing
• Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks
• Quantum adiabatic machine learning with zooming
• Equation Planting: A Tool for Benchmarking Ising Machines
• Nested Quantum Annealing Correction at Finite Temperature: $p$-spin models
• Blueprint for all-to-all connected superconducting spin qubits
• Computational hardness of spin-glass problems with tile-planted solutions
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Continuous quantum error correction for evolution under time-dependent Hamiltonians
• Improving performance of logical qubits by parameter tuning and topology compensation
• Perils of Embedding for Sampling Problems
• Guided quantum walk
• Few-qubit quantum refrigerator for cooling a multi-qubit system
• Physics-inspired Ising Computing with Ring Oscillator Activated p-bits
• Ising Hamiltonian Minimization: Gain-Based Computing with Manifold Reduction of Soft-Spins vs Quantum Annealing
• An Optimization Case Study for solving a Transport Robot Scheduling Problem on Quantum-Hybrid and Quantum-Inspired Hardware
• Variational quantum iterative power algorithms for global optimization
• Classical simulation and theory of quantum annealing in a thermal environment
• Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
• Phase transition of Frustrated Ising model via D-wave Quantum Annealing Machine
• Deep recurrent networks predicting the gap evolution in adiabatic quantum computing
• Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA
• On the dynamics of Simulated Quantum Annealing in random Ising chains
• Disorder-assisted graph coloring on quantum annealers
• A comparison between D-wave and a classical approximation algorithm and a heuristic for computing the ground state of an Ising spin glass
• Towards an Automatic Framework for Solving Optimization Problems with Quantum Computers
• Advantage of pausing: parameter setting for quantum annealers
• 4-clique Network Minor Embedding for Quantum Annealers
• A Quantum Algorithm for Model-Independent Searches for New Physics
• Localization transition induced by programmable disorder
• Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
• A quantum computing concept for 1-D elastic wave simulation with exponential speedup
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• Improving Schrödinger Equation Implementations with Gray Code for Adiabatic Quantum Computers
• Stochastic Simulated Quantum Annealing for Fast Solution of Combinatorial Optimization Problems
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• Obstacles to quantum annealing in a planar embedding of XORSAT
• Counterdiabatic Driving with Performance Guarantees
• Noise-tolerant quantum speedups in quantum annealing without fine tuning
• A numerical approach for calculating exact non-adiabatic terms in quantum dynamics
• Quantum circuit compilation with quantum computers
• C-Nash: A Novel Ferroelectric Computing-in-Memory Architecture for Solving Mixed Strategy Nash Equilibrium
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Speeding up Quantum Annealing with Engineered Dephasing
• Investigating the potential for a limited quantum speedup on protein lattice problems
• Demonstration of error-suppressed quantum annealing via boundary cancellation
• 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
• Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
• Mapping State Transition Susceptibility in Quantum Annealing
• Posiform Planting: Generating QUBO Instances for Benchmarking
• Entanglement generation and scaling from noisy quenches across a quantum critical point
• Optimization via Quantum Preconditioning
• Computing Canonical Averages with Quantum and Classical Optimizers: Thermodynamic Reweighting for QUBO Models of Physical Systems
• Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo
• Analog Errors in Quantum Annealing: Doom and Hope
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
• A Statistical Analysis for Per-Instance Evaluation of Stochastic Optimizers: Avoiding Unreliable Conclusions
• Quantum Annealing Algorithms for Estimating Ising Partition Functions
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
• Compressed sensing enhanced by quantum approximate optimization algorithm
• Subsampling Factorization Machine Annealing
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• The Perturbed Ferromagnetic Chain: A Tuneable Test of Quantum Hardness in the Transverse-Field Ising Model
• Families of $d=2$ 2D subsystem stabilizer codes for universal Hamiltonian quantum computation with two-body interactions
• Degeneracy Engineering for Classical and Quantum Annealing: A Case Study of Sparse Linear Regression in Collider Physics
• Solving the Turbine Balancing Problem using Quantum Annealing
• Surrogate Modeling via Factorization Machine and Ising Model with Enhanced Higher-Order Interaction Learning
• Quantum speed-up for solving the one-dimensional Hubbard model using quantum annealing
• Programming tools for Analogue Quantum Computing in the High-Performance Computing Context -- A Review