On the hardness of quadratic unconstrained binary optimization problems

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.

6 pages, 6 figures

References in corpus (2)

• Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
• Monte Carlo Search for Very Hard KSAT Realizations for Use in Quantum Annealing

Cited by in corpus (5)

• Guided quantum walk
• Towards Arbitrary QUBO Optimization: Analysis of Classical and Quantum-Activated Feedforward Neural Networks
• A QUBO Framework for Team Formation
• Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
• A method for quantifying the generalization capabilities of generative models for solving Ising models