A deceptive step towards quantum speedup detection

Abstract

There have been multiple attempts to design synthetic benchmark problems with the goal of detecting quantum speedup in current quantum annealing machines. To date, classical heuristics have consistently outperformed quantum-annealing based approaches. Here we introduce a class of problems based on frustrated cluster loops - deceptive cluster loops - for which all currently known state-of-the-art classical heuristics are outperformed by the D-Wave 2000Q quantum annealing machine. While there is a sizable constant speedup over all known classical heuristics, a noticeable improvement in the scaling remains elusive. These results represent the first steps towards a detection of potential quantum speedup, albeit without a scaling improvement and for synthetic benchmark problems.

11 pages, 9 figures

References in corpus (3)

• Mathematical Foundation of Quantum Annealing
• Decoherence in adiabatic quantum computation
• Reexamining classical and quantum models for the D-Wave One processor

Cited by in corpus (41)

• Perspectives of quantum annealing: Methods and implementations
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Boundaries of quantum supremacy via random circuit sampling
• Uncertain fate of fair sampling in quantum annealing
• Scaling overhead of embedding optimization problems in quantum annealing
• Why and when is pausing beneficial in quantum annealing?
• Quantum annealing for systems of polynomial equations
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Physics-Inspired Heuristics for Soft MIMO Detection in 5G New Radio and Beyond
• Quantum adiabatic machine learning with zooming
• Equation Planting: A Tool for Benchmarking Ising Machines
• Nested Quantum Annealing Correction at Finite Temperature: $p$-spin models
• Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
• Computational hardness of spin-glass problems with tile-planted solutions
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Networked Quantum Services
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Fair sampling of ground-state configurations of binary optimization problems
• Counterdiabatic Reverse Annealing
• Deep learning optimal quantum annealing schedules for random Ising models
• Unfolding as Quantum Annealing
• Forbidden subspaces for level-1 QAOA and IQP circuits
• Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
• Verifying the output of quantum optimizers with ground-state energy lower bounds
• QUBO.jl: A Julia Ecosystem for Quadratic Unconstrained Binary Optimization
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Discriminating Non-Isomorphic Graphs with an Experimental Quantum Annealer
• Entanglement-assisted variational algorithm for discrete optimization problems
• Absence of small-world effects at the quantum level and stability of the quantum critical point
• Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo
• Optimization and benchmarking of the thermal cycling algorithm
• The Perturbed Ferromagnetic Chain: A Tuneable Test of Quantum Hardness in the Transverse-Field Ising Model
• Noise Effects on Diabatic Quantum Annealing Protocols
• Surrogate Modeling via Factorization Machine and Ising Model with Enhanced Higher-Order Interaction Learning
• Families of $d=2$ 2D subsystem stabilizer codes for universal Hamiltonian quantum computation with two-body interactions