Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
This work addresses the efficiency of QUBO and spin glass solvers by identifying redundancies in testbeds, which is incremental as it builds on existing methods with new insights.
The study transformed Quadratic Unconstrained Binary Optimization (QUBO) into a spin glass problem, revealing that testbed instances have large redundancies where many spins align with external fields, reducing problem hardness. It demonstrated consequences for solvers and heuristics, implementing Extremal Optimization for QUBO and proposing a scaling-based quality assessment method.
We analyze the transformation of QUBO from its conventional Boolean presentation into an equivalent spin glass problem with coupled $\pm1$ 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.