Defining and detecting quantum speedup

Abstract

The development of small-scale digital and analog quantum devices raises the question of how to fairly assess and compare the computational power of classical and quantum devices, and of how to detect quantum speedup. Here we show how to define and measure quantum speedup in various scenarios, and how to avoid pitfalls that might mask or fake quantum speedup. We illustrate our discussion with data from a randomized benchmark test on a D-Wave Two device with up to 503 qubits. Comparing the performance of the device on random spin glass instances with limited precision to simulated classical and quantum annealers, we find no evidence of quantum speedup when the entire data set is considered, and obtain inconclusive results when comparing subsets of instances on an instance-by-instance basis. Our results for one particular benchmark do not rule out the possibility of speedup for other classes of problems and illustrate that quantum speedup is elusive and can depend on the question posed.

References in corpus (21)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Strengths and Weaknesses of Quantum Computing
• Quantum annealing with more than one hundred qubits
• Theory of Quantum Annealing of an Ising Spin Glass
• Experimental signature of programmable quantum annealing
• Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Adiabatic Quantum Computation in Open Systems
• Error corrected quantum annealing with hundreds of qubits
• Quantum Speedup by Quantum Annealing
• A scalable control system for a superconducting adiabatic quantum optimization processor
• Optimized simulated annealing for Ising spin glasses
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Pretending to factor large numbers on a quantum computer
• Absence of an Almeida-Thouless line in Three-Dimensional Spin Glasses
• A scalable readout system for a superconducting adiabatic quantum optimization system
• MAX 2-SAT with up to 108 qubits
• Measures of quantum computing speedup
• Comment on: "Classical signature of quantum annealing"

Cited by in corpus (300)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• Probing many-body dynamics on a 51-atom quantum simulator
• Adiabatic Quantum Computing
• Superconducting Qubits: Current State of Play
• Microwave photonics with superconducting quantum circuits
• Quantum algorithms: an overview
• Quantum information processing with superconducting circuits: a review
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Network of Time-Multiplexed Optical Parametric Oscillators as a Coherent Ising Machine
• Quantum spin dynamics and entanglement generation with hundreds of trapped ions
• Perspectives of quantum annealing: Methods and implementations
• Limits on Fundamental Limits to Computation
• High-dimensional quantum communication: benefits, progress, and future challenges
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Quantum Annealing for Industry Applications: Introduction and Review
• Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
• Harnessing disordered quantum dynamics for machine learning
• What is the Computational Value of Finite Range Tunneling?
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• Quantum Computer Systems for Scientific Discovery
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network: Toward quantum soft computing
• A case study in programming a quantum annealer for hard operational planning problems
• Quantum Optimization of Fully-Connected Spin Glasses
• The prospects of quantum computing in computational molecular biology
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• When does a physical system compute?
• Efficient partition of integer optimization problems with one-hot encoding
• Quantum versus Classical Annealing of Ising Spin Glasses
• Expanding the horizon of automated metamaterials discovery via quantum annealing
• Open source software in quantum computing
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Challenges and Opportunities in Quantum Optimization
• Application of Quantum Annealing to Training of Deep Neural Networks
• Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
• Probing for quantum speedup in spin glass problems with planted solutions
• Quantum annealing versus classical machine learning applied to a simplified computational biology problem
• Searching for quantum speedup in quasistatic quantum annealers
• Scaling advantage in quantum simulation of geometrically frustrated magnets
• Optimized simulated annealing for Ising spin glasses
• Nonnegative/binary matrix factorization with a D-Wave quantum annealer
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Quantum-inspired algorithms in practice
• Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
• Beyond-classical computation in quantum simulation
• 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-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
• Quantum annealing correction for random Ising problems
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Coherent coupled qubits for quantum annealing
• A NASA Perspective on Quantum Computing: Opportunities and Challenges
• Modernizing Quantum Annealing using Local Searches
• Quantum Machine Learning: from physics to software engineering
• Reexamining classical and quantum models for the D-Wave One processor
• Quantum Annealing Correction with Minor Embedding
• Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
• Finite-range interacting Ising quantum magnets with Rydberg atoms in optical lattices - From Rydberg superatoms to crystallization
• Bayesian Network Structure Learning Using Quantum Annealing
• Biology and medicine in the landscape of quantum advantages
• How "Quantum" is the D-Wave Machine?
• Quantum bits with Josephson junctions
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Experimental statistical signature of many-body quantum interference
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Scaling and diabatic effects in quantum annealing with a D-Wave device
• A 16-bit Coherent Ising Machine for One-Dimensional Ring and Cubic Graph Problems
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Benchmarking a quantum annealing processor with the time-to-target metric
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Geometric quantum speed limits: a case for Wigner phase space
• Benchmarking Quantum Annealing Controls with Portfolio Optimization
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• Recent progress in quantum simulation using superconducting circuits
• NISQ Computers: A Path to Quantum Supremacy
• Low-Latency Digital Signal Processing for Feedback and Feedforward in Quantum Computing and Communication
• A deceptive step towards quantum speedup detection
• Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Temperature scaling law for quantum annealing optimizers
• Applying quantum algorithms to constraint satisfaction problems
• Genome assembly using quantum and quantum-inspired annealing
• Unraveling Quantum Annealers using Classical Hardness
• Demonstration of algorithmic quantum speedup
• Dissipation in adiabatic quantum computers: Lessons from an exactly solvable model
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Global warming: Temperature estimation in annealers
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• A quantum annealer with fully programmable all-to-all coupling via Floquet engineering
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Benchmarking neural networks for quantum computation
• Building an iterative heuristic solver for a quantum annealer
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Boundaries of quantum supremacy via random circuit sampling
• Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Programmable Quantum Annealing Architectures with Ising Quantum Wires
• Uncertain fate of fair sampling in quantum annealing
• Quantum annealing for the number partitioning problem using a tunable spin glass of ions
• Maximum-Entropy Inference with a Programmable Annealer
• Experimental characterization of the energetics of quantum logic gates
• Readiness of Quantum Optimization Machines for Industrial Applications
• Quantum processor-inspired machine learning in the biomedical sciences
• Enhancing Quantum Annealing Performance for the Molecular Similarity Problem
• Qubit-efficient encoding schemes for binary optimisation problems
• 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
• Predicting quantum advantage by quantum walk with convolutional neural networks
• Scaling overhead of embedding optimization problems in quantum annealing
• From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
• Thermalization, freeze-out and noise: deciphering experimental quantum annealers
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• A Framework for Demonstrating Practical Quantum Advantage: Racing Quantum against Classical Generative Models
• Chaos in spin glasses revealed through thermal boundary conditions
• Heavy tails in the distribution of time-to-solution for classical and quantum annealing
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Performance of two different quantum annealing correction codes
• The Power of Adiabatic Quantum Computation with No Sign Problem
• Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions
• Mean Field Analysis of Quantum Annealing Correction
• Why and when is pausing beneficial in quantum annealing?
• Advances in quantum machine learning
• Comparative Study of the Performance of Quantum Annealing and Simulated Annealing
• Efficient verification of Boson Sampling
• Evidence against a mean field description of short-range spin glasses revealed through thermal boundary conditions
• From classical to quantum non-equilibrium dynamics of Rydberg excitations in optical lattices
• Relaxation vs. adiabatic quantum steady state preparation: which wins?
• Quantum annealing for systems of polynomial equations
• Number Partitioning with Grover's Algorithm in Central Spin Systems
• A dissipative environment may improve the quantum annealing performances of the ferromagnetic p-spin model
• Algorithm for the solution of the Dirac equation on digital quantum computers
• Assessing the quantumness of a damped two-level system
• Practical engineering of hard spin-glass instances
• Accelerated Quantum Monte Carlo with Probabilistic Computers
• Charged particle tracking with quantum annealing-inspired optimization
• From local to global ground states in Ising spin glasses
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Stability of the quantum Sherrington-Kirkpatrick spin glass model
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• Eigenstate Tracking in Open Quantum Systems
• High-quality Thermal Gibbs Sampling with Quantum Annealing Hardware
• Improved Boltzmann machines with error corrected quantum annealing
• An Application of Quantum Annealing Computing to Seismic Inversion
• Analog Nature of Quantum Adiabatic Unstructured Search
• Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
• The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Boosting quantum annealer performance via sample persistence
• Degeneracy, degree, and heavy tails in quantum annealing
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
• Quantum-assisted associative adversarial network: Applying quantum annealing in deep learning
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Resource estimate for quantum many-body ground-state preparation on a quantum computer
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• A Performance Estimator for Quantum Annealers: Gauge selection and Parameter Setting
• Simulated quantum annealing of double-well and multi-well potentials
• Effects of setting the temperatures in the parallel tempering Monte Carlo algorithm
• Quantum adiabatic machine learning with zooming
• Nested Quantum Annealing Correction at Finite Temperature: $p$-spin models
• How to test the "quantumness" of a quantum computer?
• Optimally Stopped Optimization
• Computational Overhead of Locality Reduction in Binary Optimization Problems
• Adiabatic Quantum Optimization for Associative Memory Recall
• Fast Quantum Methods for Optimization
• Computational hardness of spin-glass problems with tile-planted solutions
• Error Reduction in Quantum Annealing using Boundary Cancellation: Only the End Matters
• Assessment of Quantum Annealing for the Construction of Satisfiability Filters
• Practical Verification of Quantum Properties in Quantum Approximate Optimization Runs
• Understanding Quantum Tunneling using Diffusion Monte Carlo Simulations
• Quantum Annealing - Foundations and Frontiers
• Guiding Principle for Minor-Embedding in Simulated-Annealing-Based Ising Machines
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Networked Quantum Services
• Continuous quantum error correction for evolution under time-dependent Hamiltonians
• Ferromagnetically shifting the power of pausing
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• Dynamics of the quantum search and quench-induced first-order phase transitions
• Error suppression in adiabatic quantum computing with qubit ensembles
• Energy landscapes of combinatorial optimization in Ising machines
• Improving performance of logical qubits by parameter tuning and topology compensation
• Breakdown of the weak coupling limit in quantum annealing
• High-Dimensional Similarity Search with Quantum-Assisted Variational Autoencoder
• Fair sampling of ground-state configurations of binary optimization problems
• Quantum Annealing for Neural Network optimization problems: a new approach via Tensor Network simulations
• Accessible coherence in open quantum system dynamics
• Quantum optics and frontiers of physics: The third quantum revolution
• Viewing Vanilla Quantum Annealing Through Spin Glasses
• Diabatic Quantum Annealing for the Frustrated Ring Model
• Counterdiabatic Reverse Annealing
• Minimal Constraints in the Parity Formulation of Optimization Problems
• Patch-planting spin-glass solution for benchmarking
• A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing
• Towards Prediction of Financial Crashes with a D-Wave Quantum Computer
• 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
• Cluster state generation in one-dimensional Kitaev honeycomb model via shortcut to adiabaticity
• Deep learning optimal quantum annealing schedules for random Ising models
• Disorder-assisted graph coloring on quantum annealers
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Realization of programmable Ising models in a trapped-ion quantum simulator
• On the dynamics of Simulated Quantum Annealing in random Ising chains
• Supervised learning of random quantum circuits via scalable neural networks
• Tunneling in projective quantum Monte Carlo simulations with guiding wave functions
• Information Theoretical Limits for Quantum Optimal Control Solutions: Error Scaling of Noisy Channels
• Advantage of pausing: parameter setting for quantum annealers
• Quantum-enhanced learning of rotations about an unknown direction
• Graph Coloring with Quantum Annealing
• Frustrated polaritons
• A Quantum Algorithm for Model-Independent Searches for New Physics
• Efficient quantum and simulated annealing of Potts models using a half-hot constraint
• Semiclassical approach to finite temperature quantum annealing with trapped ions
• Beyond Quantum Annealing: Optimal control solutions to MaxCut problems
• Sampling diverse near-optimal solutions via algorithmic quantum annealing
• OIM: Oscillator-based Ising Machines for Solving Combinatorial Optimisation Problems
• How Quantum is the Speedup in Adiabatic Unstructured Search?
• Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer
• Quantum Monte Carlo Annealing with Multi-Spin Dynamics
• Reconstructing the ideal results of a perturbed analog quantum simulator
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• Path-Integral Quantum Monte Carlo simulation with Open-Boundary Conditions
• From quantum-enhanced to quantum-inspired Monte Carlo
• Diagrammatic description of a system coupled strongly to a bosonic bath
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Unraveling Reverse Annealing: A Study of D-Wave Quantum Annealers
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• The Roles of Kerr nonlinearity in a Bosonic Quantum Neural Network
• Experimental pairwise entanglement estimation for an N-qubit system :A machine learning approach for programming quantum hardware
• Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems
• A numerical approach for calculating exact non-adiabatic terms in quantum dynamics
• Quantum computing for data science
• Difference between quantum annealing by imaginary-time and real-time Schrödinger equation of Grover's search
• Applications of Quantum Annealing in Statistics
• Exact expression of the energy gap at first-order quantum phase transitions of a non-stoquastic Hamiltonian
• Understanding the physics of D-Wave annealers: From Schrödinger to Lindblad to Markovian Dynamics
• Investigating the potential for a limited quantum speedup on protein lattice problems
• Quantum annealing of Cayley-tree Ising spins at small scales
• Propagation of quantum fluctuations in quantum Ising model
• Adding color: Visualization of energy landscapes in spin glasses
• Demonstration of error-suppressed quantum annealing via boundary cancellation
• Discriminating Non-Isomorphic Graphs with an Experimental Quantum Annealer
• Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
• Quantum simulation of macro and micro quantum phase transition from paramagnetism to frustrated magnetism with a superconducting circuit
• Computational quantum-classical boundary of complex and noisy quantum systems
• Mapping constrained optimization problems to quantum annealing with application to fault diagnosis
• A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing---Abridged Version
• Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
• Entanglement-assisted variational algorithm for discrete optimization problems
• Improving the efficiency of quantum annealing with controlled diagonal catalysts
• Lagrange Oscillatory Neural Networks for Constraint Satisfaction and Optimization
• Solving the Gross-Pitaevskii equation on multiple different scales using the quantics tensor train representation
• Quadratic constrained mixed discrete optimization with an adiabatic quantum optimizer
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• Universal Computation with Quantum Fields
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• Three-step implementation of any nxn unitary with a complete graph of n qubits
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
• Recursive simulation of quantum annealing
• Reliability of digitized quantum annealing and the decay of entanglement
• Classical Simulated Annealing Using Quantum Analogues
• A Statistical Analysis for Per-Instance Evaluation of Stochastic Optimizers: Avoiding Unreliable Conclusions
• A practical efficient and effective method for the Hamiltonian cycle problem that runs on a standard computer
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• Subsampling Factorization Machine Annealing
• Relation of classical non-equilibrium dynamics and quantum annealing
• Optimization and benchmarking of the thermal cycling algorithm
• Quantum-Inspired Tempering for Ground State Approximation using Artificial Neural Networks
• Effect of Quantum Statistics on Computational Power of Atomic Quantum Annealers
• Hard combinatorial problems and minor embeddings on lattice graphs
• Minimizing minor embedding energy: an application in quantum annealing
• Noise Effects on Diabatic Quantum Annealing Protocols
• Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
• Statistical Analysis of Quantum Annealing
• 2D implementation of quantum annealing algorisms for fourth order binary optimization problems
• Finding Hadamard matrices by a quantum annealing machine
• A Quantum Annealing Approach to Reduce Covid-19 Spread on College Campuses
• Numerical Probe of Dynamical Properties of a Two-Dimensional Triangular Ising Lattice with Long-Range Interaction
• Assessing the quantumness of the annealing dynamics via Leggett Gargs inequalities: a weak measurement approach
• Exploring Quantum Annealing for Coarse-Grained Protein Folding
• Recent quantum runtime (dis)advantages
• Thermodynamic significance of QUBO encoding on quantum annealers
• Quantum annealing and condensed matter physics
• A Quantum Genetic Algorithm with application to Cosmological Parameters Estimation
• Degeneracy Engineering for Classical and Quantum Annealing: A Case Study of Sparse Linear Regression in Collider Physics
• Evaluating the solution performance of the augmented Lagrangian function on Ising machines
• Lack of a thermodynamic finite-temperature spin-glass phase in the two-dimensional randomly-coupled ferromagnet
• Quantum-inspired search method for low-energy states of classical Ising Hamiltonians