Why Tests for Quadratic Unconstrained Binary Optimization (QUBO) are poorly defined

We explore the impact of the weight distribution of the QUBO formulation usually found in the operations research literature and analyze their meaning in statistical physics language. To this end, we transform QUBO from its conventional Boolean presentation into an Ising spin glass with a random external field on each site. These fields tend to be rather large compared to the typical coupling, thus, tilting the energy landscape to a such a degree such that global minima become much easier to find than those of truly hard spin glass problems without (or in small) fields. This is also significant because QUBO is used as a NP-hard problem to test the efficiency of quantum computers such as D-Wave. To demonstrate the shortcomings of usual testbeds, we present a simple implementation of the Extremal Optimization (EO) heuristic (DOI:10.1103/PhysRevLett.86.5211) that finds solutions with high efficiency. In turn, transforming spin glasses with small fields into QUBO makes for strong testbeds.