Probing for quantum speedup in spin glass problems with planted solutions

Abstract

The availability of quantum annealing devices with hundreds of qubits has made the experimental demonstration of a quantum speedup for optimization problems a coveted, albeit elusive goal. Going beyond earlier studies of random Ising problems, here we introduce a method to construct a set of frustrated Ising-model optimization problems with tunable hardness. We study the performance of a D-Wave Two device (DW2) with up to 503 qubits on these problems and compare it to a suite of classical algorithms, including a highly optimized algorithm designed to compete directly with the DW2. The problems are generated around predetermined ground-state configurations, called planted solutions, which makes them particularly suitable for benchmarking purposes. The problem set exhibits properties familiar from constraint satisfaction (SAT) problems, such as a peak in the typical hardness of the problems, determined by a tunable clause density parameter. We bound the hardness regime where the DW2 device either does not or might exhibit a quantum speedup for our problem set. While we do not find evidence for a speedup for the hardest and most frustrated problems in our problem set, we cannot rule out that a speedup might exist for some of the easier, less frustrated problems. Our empirical findings pertain to the specific D-Wave processor and problem set we studied and leave open the possibility that future processors might exhibit a quantum speedup on the same problem set.

24 pages, 25 figures. v2: new version replaces erroneously posted incomplete version. v3: updated to published version

References in corpus (8)

• Quantum Computing
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Decoherence in adiabatic quantum computation
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• Quantum annealing correction for random Ising problems
• Reexamining classical and quantum models for the D-Wave One processor
• Quantum and Classical in Adiabatic Computation

Cited by in corpus (104)

• Quantum information processing with superconducting circuits: a review
• Perspectives of quantum annealing: Methods and implementations
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• What is the Computational Value of Finite Range Tunneling?
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
• Quantum annealing versus classical machine learning applied to a simplified computational biology problem
• Searching for quantum speedup in quasistatic quantum annealers
• Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
• 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
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Benchmarking a quantum annealing processor with the time-to-target metric
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
• A deceptive step towards quantum speedup detection
• Temperature scaling law for quantum annealing optimizers
• Genome assembly using quantum and quantum-inspired annealing
• Unraveling Quantum Annealers using Classical Hardness
• Driver Hamiltonians for constrained optimization in quantum annealing
• On the Computational Complexity of Curing the Sign Problem
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Building an iterative heuristic solver for a quantum annealer
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Uncertain fate of fair sampling in quantum annealing
• Maximum-Entropy Inference with a Programmable Annealer
• Readiness of Quantum Optimization Machines for Industrial Applications
• Enhancing Quantum Annealing Performance for the Molecular Similarity Problem
• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
• Machine learning \& artificial intelligence in the quantum domain
• Scaling overhead of embedding optimization problems in quantum annealing
• Thermalization, freeze-out and noise: deciphering experimental quantum annealers
• From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
• Chaos in spin glasses revealed through thermal boundary conditions
• Analog Errors in Ising Machines
• Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs
• Practical engineering of hard spin-glass instances
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• An Application of Quantum Annealing Computing to Seismic Inversion
• Analog Nature of Quantum Adiabatic Unstructured Search
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Boosting quantum annealer performance via sample persistence
• The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
• Degeneracy, degree, and heavy tails in quantum annealing
• Advantages of Unfair Quantum Ground-State Sampling
• Programmable Superpositions of Ising Configurations
• Evaluating Ising Processing Units with Integer Programming
• Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks
• A Performance Estimator for Quantum Annealers: Gauge selection and Parameter Setting
• Equation Planting: A Tool for Benchmarking Ising Machines
• Nested Quantum Annealing Correction at Finite Temperature: $p$-spin models
• Optimally Stopped Optimization
• Computational hardness of spin-glass problems with tile-planted solutions
• Generating Weighted MAX-2-SAT Instances of Tunable Difficulty with Frustrated Loops
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Energy landscapes of combinatorial optimization in Ising machines
• Fair sampling of ground-state configurations of binary optimization problems
• Estimating the Density of States of Frustrated Spin Systems
• Viewing Vanilla Quantum Annealing Through Spin Glasses
• Patch-planting spin-glass solution for benchmarking
• Physics-inspired Ising Computing with Ring Oscillator Activated p-bits
• A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing
• Fluctuation guided search in quantum annealing
• Chook -- A comprehensive suite for generating binary optimization problems with planted solutions
• Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
• A comparison between D-wave and a classical approximation algorithm and a heuristic for computing the ground state of an Ising spin glass
• Many-Qudit representation for the Travelling Salesman Problem Optimisation
• Towards an Automatic Framework for Solving Optimization Problems with Quantum Computers
• Realization of Heisenberg models of spin systems with polar molecules in pendular states
• Site and bond percolation thresholds in $K_{n,n}$-based lattices: Vulnerability of quantum annealers to random qubit and coupler failures on chimera topologies
• Localization transition induced by programmable disorder
• A small-world search for quantum speedup: How small-world interactions can lead to improved quantum annealer designs
• Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
• How Quantum is the Speedup in Adiabatic Unstructured Search?
• Approximate ground states of the random-field Potts model from graph cuts
• Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer
• Verifying the output of quantum optimizers with ground-state energy lower bounds
• Quantum Annealing and the Satisfiability Problem
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Adding color: Visualization of energy landscapes in spin glasses
• Demonstration of error-suppressed quantum annealing via boundary cancellation
• Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
• Discriminating Non-Isomorphic Graphs with an Experimental Quantum Annealer
• Posiform Planting: Generating QUBO Instances for Benchmarking
• 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
• Mapping State Transition Susceptibility in Quantum Annealing
• Development of research network on Quantum Annealing Computation and Information using Google Scholar data
• Absence of small-world effects at the quantum level and stability of the quantum critical point
• Analytical shortcuts to adiabaticity of weakly driven processes
• Hard combinatorial problems and minor embeddings on lattice graphs
• Optimization and benchmarking of the thermal cycling algorithm
• Classical Simulated Annealing Using Quantum Analogues
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Applying Multi-qubit Correction to Frustrated Cluster Loops on an Adiabatic Quantum Computer
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
• Analog Errors in Quantum Annealing: Doom and Hope
• Lack of a thermodynamic finite-temperature spin-glass phase in the two-dimensional randomly-coupled ferromagnet
• Essentiality of the Non-stoquastic Hamiltonians and Driver Graph Design in Quantum Optimization Annealing
• Degeneracy Engineering for Classical and Quantum Annealing: A Case Study of Sparse Linear Regression in Collider Physics