Mean field approximation for solving QUBO problems

Máté Tibor Veszeli and Gábor Vattay

PLOS ONE, 2022, vol. 17, issue 8, 1-12

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.

Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0273709 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 73709&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0273709

DOI: 10.1371/journal.pone.0273709

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().