Analysis of the relation between quadratic unconstrained binary optimization and the spin-glass ground-state problem
Stefan Boettcher · Physical Review Research · 2019
An inherent weakness in a widely used formulation of the Quadratic Unconstrained Binary Optimization problem is revealed when transformed into an Ising spin glass. In the ground state, spins in the glass experience external magnetic fields, many of which are of a sizable magnitude to entirely coerce their spins into alignment, irrespective of any coupling; only a small fraction of spins can resist. Thus, the effective size of this NP-hard combinatorial problem is much smaller than is apparent from the number of variables involved.