Annealed Mean Field Descent Is Highly Effective for Quadratic Unconstrained Binary Optimization
Kyo Kuroki, Thiem Van Chu, Masato Motomura, Kazushi Kawamura · IEEE Transactions on Evolutionary Computation · 2026
In recent years, formulating various combinatorial optimization problems as Quadratic Unconstrained Binary Optimization (QUBO) has gained significant attention as a promising approach for efficiently obtaining optimal or near-optimal solutions. While QUBO offers a general-purpose framework, existing solvers often struggle with performance variability across different problems. This paper (i) theoretically analyzes Mean Field Annealing (MFA) and its variants, which are representative QUBO solvers, and shows that their underlying self-consistent equations do not necessarily correspond to the minimization condition of the Kullback–Leibler divergence between the mean-field approximation and the exact distribution. Moreover, the paper (ii) proposes a novel method, Annealed Mean Field Descent (AMFD), which directly minimizes this divergence to address this limitation. Through extensive experiments on five benchmark combinatorial optimization problems (Maximum Cut Problem, Maximum Independent Set Problem, Traveling Salesman Problem, Quadratic Assignment Problem, and Graph Coloring Problem), we demonstrate that AMFD exhibits superior performance in many cases and reduced problem dependence compared to state-of-the-art QUBO solvers and Gurobi—a state-of-the-art versatile mathematical optimization solver not limited to QUBO.