Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem

Abstract

We analyze the transformation of QUBO from its conventional Boolean presentation into an equivalent spin glass problem with coupled $\pm 1$ spin variables exposed to a site-dependent external field. We find that in a widely used testbed for QUBO these fields tend to be rather large compared to the typical coupling and many spins in each optimal configurations simply align with the fields irrespective of their constraints. Thereby, the testbed instances tend to exhibit large redundancies - seemingly independent variables which contribute little to the hardness of the problem, however. We demonstrate various consequences of this insight, for QUBO solvers as well as for heuristics developed for finding spin glass ground states. To this end, we implement the Extremal Optimization (EO) heuristic, in a new adaptation for the QUBO problem. We also propose a novel way to assess the quality of heuristics for increasing problem sizes based on asymptotic scaling.

RevTex, 9 pages, 7 figs, 2 tabs. Numerous clarifications. For related information, see http://www.physics.emory.edu/faculty/boettcher/

References in corpus (8)

• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Behavior of Ising Spin Glasses in a Magnetic Field
• Spin glasses in a field: Three and four dimensions as seen from one space dimension
• Finite size corrections in the Sherrington-Kirkpatrick model
• Improved extremal optimization for the Ising spin glass
• Double Criticality of the Sherrington-Kirkpatrick Model at T=0
• From local to global ground states in Ising spin glasses
• Hysteretic Optimization For Spin Glasses

Cited by in corpus (7)

• Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut
• Ground State Properties of the Diluted Sherrington-Kirkpatrick Spin Glass
• Deep reinforced learning heuristic tested on spin-glass ground states: The larger picture
• Exploring the topological sector optimization on quantum computers
• Physics of the Edwards-Anderson Spin Glass in Dimensions $d=3,\dots ,8$ from Heuristic Ground State Optimization
• Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
• Recent quantum runtime (dis)advantages