Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
arXiv:1906.10036 · doi:10.1103/PhysRevResearch.1.033142
Abstract
We analyze the transformation of QUBO from its conventional Boolean presentation into an equivalent spin glass problem with coupled 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.
arXiv commentRevTex, 9 pages, 7 figs, 2 tabs. Numerous clarifications. For related information, see http://www.physics.emory.edu/faculty/boettcher/
References in corpus (22)
- The Bethe lattice spin glass revisited
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Optimization with Extremal Dynamics
- Nature's Way of Optimizing
- Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses
- Triviality of the Ground State Structure in Ising Spin Glasses
- Extremal Optimization at the Phase Transition of the 3-Coloring Problem
- 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
- Ground-state clusters of two-, three- and four-dimensional +-J Ising spin glasses
- Low temperature solution of the Sherrington-Kirkpatrick model
- Improved extremal optimization for the Ising spin glass
- Hysteretic optimization for the Sherrington-Kirkpatrick spin glass
- Double Criticality of the Sherrington-Kirkpatrick Model at T=0
- Numerical Results for Ground States of Spin Glasses on Bethe Lattices
- From local to global ground states in Ising spin glasses
- Jamming Model for the Extremal Optimization Heuristic
- Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses
- Numerical estimate of finite size corrections to the free energy of the SK model using Guerra--Toninelli interpolation
- Hysteretic Optimization For Spin Glasses
- Numerical Results for Spin Glass Ground States on Bethe Lattices: Gaussian Bonds
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 from Heuristic Ground State Optimization
- Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
- Recent quantum runtime (dis)advantages