Mean Field Approximation for solving QUBO problems

 

Optimization is one of the most useful mathematical tools in everyday life. The Quadratic Unconstrained Binary Optimization (QUBO) problem is a ubiquitous, NP hard problem, with no efficient solution, but many good approximations (simulated annealing, coherent Ising machine, etc). An adiabatic quantum computer would be perfect for this task, but its physical implementation is cumbersome, as the system can't be separated from its environment, and a large number of qubits would be needed.

I will present a mean-field-based algorithm we developed[1], imitating quantum annealing, to solve the QUBO problem, and compare it with mean field approximation as familiar from statistical physics.

 

[1]:  MT Veszeli, G Vattay: https://arxiv.org/abs/2106.03238