Demonstrating real advantage of machine learning–enhanced Monte Carlo for combinatorial optimization
Open Access
- 8 May 2026
- journal article
- Published by National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 123 (19)
Abstract
Combinatorial optimization problems are central to both practical applications and the development of optimization methods. While classical and quantum algorithms have been refined over decades, machine learning–assisted approaches are comparatively recent and have not yet consistently outperformed simple, state-of-the-art classical methods. Here, we focus on a class of Quadratic Unconstrained Binary Optimization problems, specifically the challenge of finding minimum energy configurations in three-dimensional Ising spin glasses. We use a Global Annealing Monte Carlo algorithm that integrates standard local moves with global moves proposed via machine learning. We show that local moves play a crucial role in achieving optimal performance. Benchmarking against Simulated Annealing and Population Annealing, we demonstrate that Global Annealing not only surpasses the performance of Simulated Annealing but also exhibits greater robustness than Population Annealing, maintaining effectiveness across problem hardness and system size without hyperparameter tuning. These results provide clear and robust evidence that a machine learning–assisted optimization method can exceed the capabilities of classical state-of-the-art techniques in a combinatorial optimization setting.Keywords
All Related Versions
Funding Information
- National Centre for HPC, Big Data and Quantum Computing (CN00000013)
- Sapienza University (B83C24005280001)
- Consiglio Nazionale delle Ricerche (PIR0100022)
This publication has 79 references indexed in Scilit:
- Hierarchical autoregressive neural networks in three-dimensional statistical systemComputer Physics Communications, 2025
- Unsupervised learning with GNNs for QUBO-based combinatorial optimizationEURO Journal on Computational Optimization, 2025
- Accelerating Markov Chain Monte Carlo sampling with diffusion modelsComputer Physics Communications, 2023
- Machine learning for combinatorial optimization: A methodological tour d’horizonEuropean Journal of Operational Research, 2021
- GPU accelerated population annealing algorithmComputer Physics Communications, 2017
- Scheduling2016
- Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxationsMathematical Programming, 2008
- Extremal Optimization2004
- A cluster Monte Carlo algorithm for 2-dimensional spin glassesThe European Physical Journal B, 2001
- Multi-spin coding: A very efficient technique for Monte Carlo simulations of spin systemsJournal of Computational Physics, 1981