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.
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.
Recent demonstrations on specialized benchmarks have reignited excitement for quantum computers, yet their advantage for real-world problems remains an open question. Here, we show that probabilistic computers, co-designed with hardware to implement Monte Carlo algorithms, provide a scalable classical pathway for solving hard optimization problems. We focus on two algorithms applied to three-dimensional spin glasses: discrete-time simulated quantum annealing and adaptive parallel tempering. We benchmark these methods against a leading quantum annealer. For simulated quantum annealing, increasing replicas improves residual energy scaling, consistent with extreme value theory. Adaptive parallel tempering, supported by non-local isoenergetic cluster moves, scales more favorably and outperforms simulated quantum annealing. Field Programmable Gate Arrays or specialized chips can implement these algorithms in modern hardware, leveraging massive parallelism to accelerate them while improving energy efficiency. Our results establish a rigorous classical baseline for assessing practical quantum advantage and present probabilistic computers as a scalable platform for real-world optimization challenges.
A numerical technique called Simulated Ising Annealing (SIA) uses digital computers to obtain approximations of the ground states of Ising models. The quadratic unconstrained binary optimization (QUBO) problem in combinatorial optimization, which is challenging to solve through exhaustive search, has significant linkages to the Ising model. Therefore, SIA's main objective is to identify a better solution in finite iterations. In order to enhance the performance of the simulated annealing procedure, we adopt a Gaussian augmented Hamiltonian Monte Carlo (GAHMC) method in this study. We contrasted our algorithm with Gibbs sampling and local quantum annealing method. Finally, we discuss its application on QUBO problem.
This paper explores the applications of quantum annealing (QA) and classical simulated annealing (SA) to a suite of combinatorial optimization problems in machine learning, namely feature selection, instance selection, and clustering. We formulate each task as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implement both quantum and classical solvers to compare their effectiveness. For feature selection, we propose several QUBO configurations that balance feature importance and redundancy, showing that quantum annealing (QA) produces solutions that are computationally more efficient. In instance selection, we propose a few novel heuristics for instance-level importance measures that extend existing methods. For clustering, we embed a classical-to-quantum pipeline, using classical clustering followed by QUBO-based medoid refinement, and demonstrate consistent improvements in cluster compactness and retrieval metrics. Our results suggest that QA can be a competitive and efficient tool for discrete machine learning optimization, even within the constraints of current quantum hardware.
Abstract Combinatorial optimization problems and ground state problems of spin glasses are crucial in various fields of science and technology. However, they often belong to the computational class of NP-hard, presenting significant computational challenges. Traditional algorithms inspired by statistical physics like simulated annealing have been widely adopted. Recently, advancements in Ising machines, such as quantum annealers and coherent Ising machines, offer new paradigms for solving these problems efficiently by embedding them into the analog evolution of nonlinear dynamical systems. However, existing dynamics-based algorithms often suffer from low convergence rates and local minima traps. In this work, we introduce the dual mean-field dynamics into Ising machines. The approach integrates the gradient force and the transverse force into the dynamics of Ising machines in solving combinatorial optimization problems, making it easier for the system to jump out of the local minimums and allowing the dynamics to explore wider in configuration space. We conduct extensive numerical experiments using the Sherrington–Kirkpatrick spin glass up to 10 000 spins and the maximum cut problems with the standard G-set benchmarks. The numerical results demonstrate that our dual mean-field dynamics approach enhances the performance of base Ising machines, providing a more effective solution for large-scale combinatorial optimization problems.
Quadratic Unconstrained Binary Optimization (QUBO) has emerged as a unifying framework for diverse NP-hard combinatorial optimization problems. However, a major challenge in existing QUBO solvers is the need for extensive manual tuning of algorithmic hyperparameters, such as temperature schedules in simulated annealing, which can vary greatly in effectiveness depending on the problem instance. In this paper, we propose RL-assisted annealing(RLA), a novel approach that integrates reinforcement learning (RL) with annealing-based local searches. Rather than relying on hand-crafted heuristics, RLA trains an agent to adaptively determine a bit-flip policy by observing the statistical properties of the energy differences in the objective function. Crucially, RLA encodes QUBO states as fixed-dimensional statistics, making the method scalable to various problem sizes. To further support large-scale problems, we employ distributed training on multi-GPU platforms using JAX’s pmap, parallelizing both environment simulation and policy updates. Experimental evaluations on benchmark datasets, including TSP, QAP, Max-Cut, and randomly generated QUBO instances, demonstrate that RLA achieves solution qualities on par with or better than conventional annealing-based methods, while maintaining robust performance across diverse problem instances without extensive hyperparameter tuning. These results highlight RLA as a promising step toward a flexible and practical solver for QUBO-based applications.
Optimization algorithms for combinatorial problems play a critical role in a wide range of applications, from logistics and scheduling to cryptography and artificial intelligence. Traditional classical methods, such as simulated annealing, genetic algorithms, and branch-and-bound techniques, have been widely employed to solve these problems, but they often face limitations in terms of computational efficiency and scalability as problem complexity grows. In recent years, quantum computing has emerged as a promising alternative, with quantum annealing offering a novel approach to solving combinatorial optimization problems. This study provides a comparative analysis of quantum annealing and classical optimization methods, highlighting their respective strengths and limitations. We explore how quantum annealing, through leveraging quantum tunnelling and superposition, has the potential to outperform classical algorithms in specific problem domains and Noisy Mean Field Annealing (NMFA) is used to comparisons of all algorithms. Benchmarking various combinatorial problems, such as the Traveling Salesman Problem (TSP), Max-Cut, Knapsack, and Quadratic Assignment Problem (QAP), this paper discusses performance metrics, computational time, and scalability. The findings suggest that while classical methods remain robust and practical for many real-world problems, quantum annealing holds significant promise, especially as quantum hardware continues to mature. However, there remain challenges in terms of noise, coherence, and problem mapping, which currently limit the full realization of quantum annealing's potential. This study offers insights into the future directions of optimization techniques and the evolving role of quantum computing in solving complex combinatorial problems.