Journal Article

FZJ-2022-03917

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
Frontiers Media Lausanne

This record in other databases:    

Please use a persistent id in citations: http://hdl.handle.net/2128/32203  doi:10.3389/fphy.2022.956882

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.

---

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:
; ; ; ; Article Processing Charges ; Clarivate Analytics Master Journal List ; Current Contents - Physical, Chemical and Earth Sciences ; DOAJ Seal ; Essential Science Indicators ; Fees ; IF < 5 ; JCR ; SCOPUS ; Science Citation Index Expanded ; Web of Science Core Collection

---