Practical engineering of hard spin-glass instances

Abstract

Recent technological developments in the field of experimental quantum annealing have made prototypical annealing optimizers with hundreds of qubits commercially available. The experimental demonstration of a quantum speedup for optimization problems has since then become a coveted, albeit elusive goal. Recent studies have shown that the so far inconclusive results, regarding a quantum enhancement, may have been partly due to the benchmark problems used being unsuitable. In particular, these problems had inherently too simple a structure, allowing for both traditional resources and quantum annealers to solve them with no special efforts. The need therefore has arisen for the generation of harder benchmarks which would hopefully possess the discriminative power to separate classical scaling of performance with size, from quantum. We introduce here a practical technique for the engineering of extremely hard spin glass Ising-type problem instances that does not require `cherry picking' from large ensembles of randomly generated instances. We accomplish this by treating the generation of hard optimization problems itself as an optimization problem, for which we offer a heuristic algorithm that solves it. We demonstrate the genuine thermal hardness of our generated instances by examining them thermodynamically and analyzing their energy landscapes, as well as by testing the performance of various state-of-the art algorithms on them. We argue that a proper characterization of the generated instances offers a practical, efficient way to properly benchmark experimental quantum annealers, as well as any other optimization algorithm.

8 pages plus appendix. 6+2 figures. Comments for v2: Fixed mistake in online title. Changed one sentence in abstract slightly, for better readability. Extended Sec. IIA, IV (final paragraph only), VI, based on referee comments. Updated References (removed duplicates, added footnote). Modified figure font sizing for readability

References in corpus (11)

• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Probing for quantum speedup in spin glass problems with planted solutions
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Phase transition in the three dimensional Heisenberg spin glass: Finite-size scaling analysis
• Temperature and Disorder Chaos in Three-Dimensional Ising Spin Glasses
• Simulating spin systems on IANUS, an FPGA-based computer
• Unraveling Quantum Annealers using Classical Hardness
• Computational Role of Collective Tunneling in a Quantum Annealer

Cited by in corpus (24)

• Perspectives of quantum annealing: Methods and implementations
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Scaling and diabatic effects in quantum annealing with a D-Wave device
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• A deceptive step towards quantum speedup detection
• Thermalization, freeze-out and noise: deciphering experimental quantum annealers
• From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
• The Quantum Transition of the Two-Dimensional Ising Spin Glass: A Tale of Two Gaps
• Dynamic Variational Study of Chaos: Spin Glasses in Three Dimensions
• 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
• Equation Planting: A Tool for Benchmarking Ising Machines
• Computational hardness of spin-glass problems with tile-planted solutions
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Phase Transitions between Different Spin-Glass Phases and between Different Chaoses in Quenched Random Chiral Systems
• Devil's Staircase Continuum in the Chiral Clock Spin Glass with Competing Ferromagnetic-Antiferromagnetic and Left-Right Chiral Interactions
• Viewing Vanilla Quantum Annealing Through Spin Glasses
• Patch-planting spin-glass solution for benchmarking
• Chook -- A comprehensive suite for generating binary optimization problems with planted solutions
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Adding color: Visualization of energy landscapes in spin glasses
• Solving Spin Glasses with Optimized Trees of Clustered Spins
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Ultrastrong capacitive coupling of flux qubits