Mean field approximation for solving QUBO problems

Veszeli, Máté and Vattay, Gábor (2022) Mean field approximation for solving QUBO problems. PLOS ONE, 17 (8). ISSN 1932-6203

Preview

Text 2106.03238.pdf Download (577kB) | Preview

Abstract

The Quadratic Unconstrained Binary Optimization (QUBO) problem is NP-hard. Some exact methods like the Branch-and-Bound algorithm are suitable for small problems. Some approximations like stochastic simulated annealing for discrete variables or mean-field annealing for continuous variables exist for larger ones, and quantum computers based on the quantum adiabatic annealing principle have also been developed. Here we show that the mean-field approximation of the quantum adiabatic annealing leads to equations similar to those of thermal mean-field annealing. However, a new type of sigmoid function replaces the thermal one. The new mean-field quantum adiabatic annealing can replicate the best-known cut values on some of the popular benchmark Maximum Cut problems.

Actions (login required)

Edit Item