Ising machines are specialized devices designed to efficiently solve combinatorial optimization problems. They consist of artificial spins that evolve towards a low-energy configuration representing a problem’s solution. Most realistic problems require both spin-spin couplings and external fields. In Ising machines with analog spins, these interactions scale differently with the continuous spin amplitudes, leading to imbalances that affect performance. Various techniques have been proposed to mitigate this issue, but their performance has not been benchmarked. We address this gap through a numerical analysis. We evaluate the time-to-solution of these methods across three distinct problem classes with up to 2400 spins. Our results show that the most effective way to incorporate external fields is through an approach where the spin interactions are proportional to the spin signs, rather than their continuous amplitudes. Solving real-world optimization problems on analog Ising machines requires the use of external fields that bias individual spins. This work shows that the best performance is achieved using spin interactions proportional to the spin signs rather than their analog amplitudes.
Ising machines are specialized devices designed to efficiently solve combinatorial optimization problems. They consist of artificial spins that evolve towards a low-energy configuration representing a problem’s solution. Most realistic problems require both spin-spin couplings and external fields. In Ising machines with analog spins, these interactions scale differently with the continuous spin amplitudes, leading to imbalances that affect performance. Various techniques have been proposed to mitigate this issue, but their performance has not been benchmarked. We address this gap through a numerical analysis. We evaluate the time-to-solution of these methods across three distinct problem classes with up to 2400 spins. Our results show that the most effective way to incorporate external fields is through an approach where the spin interactions are proportional to the spin signs, rather than their continuous amplitudes. Solving real-world optimization problems on analog Ising machines requires the use of external fields that bias individual spins. This work shows that the best performance is achieved using spin interactions proportional to the spin signs rather than their analog amplitudes.
Ising machines are specialized devices designed to efficiently solve combinatorial optimization problems. Among such problems, Boolean Satisfiability (SAT) is particularly relevant in industrial applications. To solve SAT problems using Ising machines, it is crucial to incorporate higher-order interactions. However, in analog Ising machines, interactions of different orders scale unevenly with the continuous spin amplitudes, introducing imbalances that can significantly degrade performance. Here we present a numerical comparison of methods to mitigate these imbalances, evaluating time-to-solution and success rate on uniform random 3-SAT and 4-SAT instances. Our results show that the most effective approach employs spin interactions that are proportional to the signs of spins, rather than their continuous amplitudes. We further demonstrate that smooth approximations of this method make it compatible with analog hardware. These findings underscore the central role of spin-sign-based interactions in enabling robust and scalable analog Ising machine dynamics. Ising machines (IMs) offer promising solutions for combinatorial optimization problems yet face challenges with imbalances in higher-order interactions when applied to Boolean Satisfiability (SAT) tasks. Here, the authors demonstrate that employing spin-sign-based interactions effectively mitigates these imbalances, enhancing performance and compatibility with analog hardware, thus advancing robust and scalable IM dynamics.
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.
Ising machines are a promising approach to solve combinatorial optimization problems. They map these problems onto the Ising model and search for low-energy configurations. However, navigating the rugged energy landscapes of these systems remains difficult. To improve this navigation, classical adiabatic annealing has been proposed in the literature as a heuristic optimization method for classical Ising machines. Using this technique, the Hamiltonian of the Ising machine is gradually transformed from an easily solvable Hamiltonian to the target Hamiltonian. However, its purported effectiveness is primarily motivated by an analogy to quantum adiabatic annealing, and systematic benchmarking has remained limited.
In this work, we analyze the classical adiabatic annealing technique using continuation methods. Motivated by insights from this analysis, we propose an optimized annealing strategy we refer to as hybrid classical adiabatic annealing. We benchmark our proposed strategy using MaxCut instances with up to 800 spins and problems with external fields, for which it achieves a marginal improvement for a limited set of problems. We conclude that, although theoretically motivated and occasionally beneficial, the hybrid strategy does not offer a sufficient practical advantage over simpler, existing techniques.
With the growing demand for efficient computing to tackle complex real-world challenges like combinatorial optimization, both academia and industry are exploring alternative computing paradigms. The Ising machine (IM) is one such approach, solving optimization problems by mapping their cost functions onto the Ising model. In this framework, finding the optimal solution equates to determining the Ising spin configuration corresponding to the ground state of the Ising Hamiltonian. Analog IMs, relying on artificial spins that can take analogue rather than binary values, have shown great potential in reaching this ground at high speeds. Optical implementations, such as the opto-electronic IM developed within our research group, are particularly promising due to their higher bandwidth, energy efficiency, and lower latency compared to electronic IMs. However, scaling remains a challenge for large problems. To overcome this, we propose a novel analog optical IM utilizing a spatial light modulator (SLM). Our design differs from other IMs relying on SLMs by employing analog spin variables instead of binary ones and leveraging gradient descent-based feedback rather than a computer-driven Metropolis–Hastings sampling process. By exploiting the inherent parallelism of light, this SLM-based IM is expected to efficiently handle optimization problems with millions of spins while still maintaining high energy efficiency. At the conference, we will also offer more insight into the performance of these analogue IMs and will delve deeper in the bit resolution required for the different optical components such as the employed SLM. Based on the dynamical evolution of the IM, we will discuss strategies to further improve the problem-solving capacity and speed of these optical IMs.
Many combinatorial optimization problems can be reformulated as finding the ground state of the Ising model. Existing Ising solvers are mostly inspired by simulated annealing. Although annealing techniques offer scalability, they lack convergence guarantees and are sensitive to the cooling schedule. We propose solving the Ising problem by relaxing the binary spins to continuous variables and introducing an attraction potential that steers the solution toward binary spin configurations. A key property of this potential is that its combination with the Ising energy produces a Hamiltonian that can be written as a difference of convex polynomials. This enables us to design efficient iterative algorithms that require a single matrix-vector multiplication per iteration and provide convergence guarantees. We implement our Ising solver on a wide range of GPU platforms, from edge devices to high-performance computing clusters, and demonstrate that it consistently outperforms existing solvers across problem sizes ranging from small (103 spins) to ultra-large (108 spins).
Unconventional computers based on superconducting qubits [1] and analog/digital hardware accelerators [2]–[5] have been developed and solved hard combinatorial optimization problems (COPs) with higher efficiency than classical computers by integrating the Ising models in hardware and observing their natural convergence behavior towards the lower Ising Hamiltonian (or energy). Ouantum annealer based on superconducting qubits [1] has demonstrated its capability of finding solutions to COPs using the quantum tunneling effect. However, the quantum computer requires operating at ultra-low temperatures (15-20mK), consumes excessive power (>10kW), and is not scalable yet to solve real-world problems. Recently, ASIC hardware accelerators [2]–[5] using low-cost CMOS technologies have implemented the Ising model by integrating many physical spins (i.e., computing units of the Ising model) to accelerate the finding of solutions to hard COPs. The hardware accelerators, so-called Ising machines, solved hard COPs much faster than classical computers and consumed several orders of magnitude lower energy. Nevertheless, they still have to overcome the fundamental scalability issues for solving large-scale COPs in the real world. The performance of existing discrete-time Ising machines has been limited by the exponentially increasing number of operation cycles when the problem size increases for the large-scale COPs. in addition, prior works have not been able to integrate massive random number generators (RNG), the essential building blocks of the Ising machines for finding better solutions, that could occupy a significant hardware footprint. Prior works have implemented them off-chip, or a few have been integrated on-chip and shared by many spins. This paper proposes a novel continuous-time analog Ising machine based on coupled inveiter chain circuits to address the scalability issues of the existing discrete-time Ising machines. Besides the benefits of the continuous-time operation, which significantly lowers the computing energy and latency, we introduce an equalization method for finding better solutions without RNGs.