On the hardness of quadratic unconstrained binary optimization problems

Frontiers in Physics, vol. 10

Abstract

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.

Authors 4

1. Vrinda Mehta Aachen

   Forschungszentrum Jülich · Jülich Supercomputing Centre · RWTH Aachen University

   Affiliation as printed

   Institute for Advanced Simulation, Jülich Supercomputing Centre, Forschungszentrum Jülich, Jülich, Germany

   RWTH Aachen University, Aachen, Germany

2. Fengping Jin

   Forschungszentrum Jülich · Jülich Supercomputing Centre

   Affiliation as printed

   Institute for Advanced Simulation, Jülich Supercomputing Centre, Forschungszentrum Jülich, Jülich, Germany

3. Kristel F. L. Michielsen corresponding Aachen

   Forschungszentrum Jülich · Jülich Supercomputing Centre · RWTH Aachen University

   Affiliation as printed

   AIDAS, Jülich, Germany

   Institute for Advanced Simulation, Jülich Supercomputing Centre, Forschungszentrum Jülich, Jülich, Germany

   RWTH Aachen University, Aachen, Germany

4. Hans A. De Raedt

   University of Groningen · Forschungszentrum Jülich · Jülich Supercomputing Centre · Zernike Institute for Advanced Materials

   Affiliation as printed

   Institute for Advanced Simulation, Jülich Supercomputing Centre, Forschungszentrum Jülich, Jülich, Germany

   Zernike Institute for Advanced Materials, University of Groningen, Groningen, Netherlands