Poster (Other)

FZJ-2023-00543

http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png On the hardness of quadratic unconstrained binary optimization problems

Mehta, V.FZJ* ; Jin, F.FZJ* ; Michielsen, K. (Corresponding author)FZJ* ; De Raedt, H.FZJ*

2022

Please use a persistent id in citations: http://hdl.handle.net/2128/33536

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 QUBO correlate very well with the predictions based on the Hamming distance distributions computed for small problem instances.

---

Contributing Institute(s):

1. Jülich Supercomputing Center (JSC)

Research Program(s):

1. 5111 - Domain-Specific Simulation & Data Life Cycle Labs (SDLs) and Research Groups (POF4-511) (POF4-511)

Appears in the scientific report 2022

---

Database coverage:

---