The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)

Abstract

In an effort to overcome the limitations of random spin-glass benchmarks for quantum annealers, focus has shifted to carefully-crafted gadget-based problems whose logical structure has typically a planar topology. Recent experiments on these gadget problems using a commercially-available quantum annealer have demonstrated an impressive performance over a selection of commonly-used classical optimization heuristics. Here we show that efficient classical optimization techniques, such as minimum-weight perfect matching, can solve these gadget problems exactly and in polynomial time. We present approaches on how to mitigate this shortcoming of commonly-used benchmark problems based on planar logical topologies.

5 pages, 2 figures

Cited by in corpus (23)

• Quantum Computing in the NISQ era and beyond
• 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
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Nonnegative/binary matrix factorization with a D-Wave quantum annealer
• A deceptive step towards quantum speedup detection
• Network Community Detection On Small Quantum Computers
• Uncertain fate of fair sampling in quantum annealing
• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
• Scaling overhead of embedding optimization problems in quantum annealing
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Evaluating Ising Processing Units with Integer Programming
• Fair sampling of ground-state configurations of binary optimization problems
• Viewing Vanilla Quantum Annealing Through Spin Glasses
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features
• A small-world search for quantum speedup: How small-world interactions can lead to improved quantum annealer designs
• Verifying the output of quantum optimizers with ground-state energy lower bounds
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Discriminating Non-Isomorphic Graphs with an Experimental Quantum Annealer
• Absence of small-world effects at the quantum level and stability of the quantum critical point
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking