A Characterization of Binary Quadratic Optimization Problems

Gary A. Kochenberger, Fred Glover, Haibo Wang

Martin Anthony, Endre Boros, Yves Crama +1 more

Otto Nissfolk, Tapio Westerlund

Vrinda Mehta, Fengping Jin, Kristel F. L. Michielsen +1 more

We use exact enumeration to characterize the solutions of quadratic unconstrained binary optimization problems of less than 21 variables in terms of their distributions of Hamming distances to close-by solutions. We also perform experiments with the D-Wave Advantage 5.1 quantum annealer, solving many instances of up to 170-variable, quadratic unconstrained binary optimization problems. Our results demonstrate that the exponents characterizing the success probability of a D-Wave annealer to solve a quadratic unconstrained binary optimization correlate very well with the predictions based on the Hamming distance distributions computed for small problem instances.

Vrinda Mehta, Fengping Jin, Kristel F. L. Michielsen +1 more

We use exact enumeration to characterize the solutions of quadratic unconstrained binary optimization problems of less than 21 variables in terms of their distributions of Hamming distances to close-by solutions. We also perform experiments with the D-Wave Advantage 5.1 quantum annealer, solving many instances of up to 170-variable, quadratic unconstrained binary optimization problems. Our results demonstrate that the exponents characterizing the success probability of a D-Wave annealer to solve a QUBO correlate very well with the predictions based on the Hamming distance distributions computed for small problem instances.