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.
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.
Combinatorial optimization problems are ubiquitous in industrial applications. However, finding optimal or close-to-optimal solutions can often be extremely hard. Because some of these problems can be mapped to the ground-state search of the Ising model, tremendous effort has been devoted to developing solvers for Ising-type problems over the past decades. Recent advances in controlling and manipulating both quantum and classical systems have enabled novel computing paradigms such as quantum simulators and coherent Ising machines to tackle hard optimization problems. Here, we examine and benchmark several physics-inspired optimization algorithms, including coherent Ising machines, gain-dissipative algorithms, simulated bifurcation machines, and Hopfield neural networks, which we collectively refer to as stochastic driven nonlinear dynamical systems. Most importantly, we benchmark these algorithms against random Ising problems with planted solutions and compare them to simulated annealing as a baseline leveraging the same software stack for all solvers. We further study how different numerical integration techniques and graph connectivity affect performance. This work provides an overview of a diverse set of new optimization paradigms.
Abstract We incorporate a non-Markovian feedback mechanism into the simulated bifurcation method for dynamical solvers addressing combinatorial optimization problems. By reinjecting a portion of dissipated kinetic energy into each spin in a history-dependent and trajectory-informed manner, the method effectively suppresses early freezing induced by inelastic boundaries and enhances the system’s ability to explore complex energy landscapes. Numerical results on the maximum cut (MAX-CUT) instances of fully connected Sherrington–Kirkpatrick (SK) spin glass models, including the 2000-spin K 2000 benchmark, demonstrate that the non-Markovian algorithm significantly improves both solution quality and convergence speed. Tests on randomly generated SK instances with 100 to 1000 spins further indicate favorable scalability and substantial gains in computational efficiency. Moreover, the proposed scheme is well suited for massively parallel hardware implementations, such as field-programmable gate arrays, providing a practical and scalable approach for solving large-scale combinatorial optimization problems.
Finding the ground state of Ising spin glasses is notoriously difficult due to disorder and frustration. Often, this challenge is framed as a combinatorial optimization problem, for which a common strategy employs simulated annealing, a Monte Carlo (MC)-based algorithm that updates spins one at a time. Yet, these localized updates can cause the system to become trapped in local minima. Cluster algorithms (CAs) were developed to address this limitation and have demonstrated considerable success in studying ferromagnetic systems; however, they tend to encounter percolation issues when applied to generic spin glasses. In this work, we introduce a novel CA designed to tackle these challenges by leveraging precomputed two-point correlations, aiming solve combinatorial optimization problems in the form of Max-Cut more efficiently. In our approach, clusters are formed probabilistically based on these correlations. Various classical and quantum algorithms can be employed to generate correlations that embody information about the energy landscape of the problem. By utilizing this information, the algorithm aims to identify groups of spins whose simultaneous flipping induces large transitions in configuration space with high acceptance probability - even at low energy levels - thereby escaping local minima more effectively. Notably, clusters generated using correlations from the Quantum Approximate Optimization Algorithm exhibit high acceptance rates at low temperatures. These acceptance rates often increase with circuit depth, accelerating the algorithm and enabling more efficient exploration of the solution space.
Abstract Two classes of quantum-annealing-inspired-algorithms (QAIA), namely different variants of simulated coherent Ising machine and simulated bifurcation, have been proposed for efficiently solving combinatorial optimization problems recently. In order to certify the superiority of these algorithms, standardized comparisons among them and against other physics-based algorithms are necessary. In this work, for Max-Cut problems up to 20,000 nodes, we benchmark QAIA against quantum annealing and other physics-based algorithms. We found that ballistic simulated bifurcation excelled for chimera and small-scale graphs, achieving nearly a 50-fold reduction in time-to-solution compared to quantum annealing. For large-scale graphs, discrete simulated bifurcation achieves the lowest time-to-target and outperforms D-Wave Advantage system when tasked with finding the maximum cut value in pegasus graphs. Our results suggest that QAIA represents a promising means for solving combinatorial optimization problems in practice, and can act as a natural baseline for competing quantum algorithms.
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.
The Ising machine, as a quantum-inspired computing system, can be used to efficiently solve combinatorial optimization problems. Ongoing studies have positioned it to potentially surpass the performance limitations of traditional computers. However, such Ising machines also suffer from scalability as the solution quality becomes sub-optimal when the problem size increases. In this work, we propose an Ising-based framework that uses a distributed Ising algorithm to find the near-optimal solution for large-scale Max-Cut problems through parallel processing via graph segmentation and reassembly. We selected the coherent Ising machine as the hardware solver and successfully found the solution for a 2000-node instance utilizing 20 computational bits on the Gset standard dataset. Additionally, we investigated the key factors influencing the system's performance and discovered that setting the number of reorganizations to one results in higher accuracy. Building on this configuration, we utilized a 100-bit CIM hardware platform (CPQC-1) to solve instances with varying numbers of nodes. The experimental results agree well with the theoretical simulations, confirming the practical feasibility of our method. Moreover, compared to existing Ising-based solvers, our algorithm significantly reduces computational resource requirements while achieving superior performance on large-scale combinatorial optimization problems, highlighting its effectiveness on quantum-inspired hardware.