Analog Ising machines are dedicated hardware solvers designed to solve NP hard optimization problems. However, the global optimum is often not found as the system gets stuck in local minima. While several strategies exist to increase the chance of escaping local minima, these methods often require extensive parameter tuning. In this work, we investigate the injection of large noise as a standalone scheme and in combination with annealing to improve the success rate and the time-to-target (TTT) of analog Ising machines for MaxCut problems. We demonstrate that optimizing the noise improves the TTT by several orders of magnitude and renders both approaches competitive with state-of-the-art schemes, such as chaotic amplitude control. Moreover, we are able to predict an optimal noise value based on the problem connectivity, statistics of the coupling matrix and the coupling strength, thereby eliminating the need for costly parameter optimization.
Analog Ising machines are dedicated hardware solvers designed to solve NP hard optimization problems. However, the global optimum is often not found as the system gets stuck in local minima. While several strategies exist to increase the chance of escaping local minima, these methods often require extensive parameter tuning. In this work, we investigate the injection of large noise as a standalone scheme and in combination with annealing to improve the success rate and the time-to-target (TTT) of analog Ising machines for MaxCut problems. We demonstrate that optimizing the noise improves the TTT by several orders of magnitude and renders both approaches competitive with state-of-the-art schemes, such as chaotic amplitude control. Moreover, we are able to predict an optimal noise value based on the problem connectivity, statistics of the coupling matrix and the coupling strength, thereby eliminating the need for costly parameter optimization.
Photonic Ising machines are a recent and promising non-von Neuman architecture to efficiently solve large NP-hard optimization problems. This is done by letting spins evolve to the ground state of the Ising system. However, the Ising machine does not always relax to this ground state and can get trapped in local minima, resulting in suboptimal solutions. Here, we show that Ising-encoded optimization problems implemented on analog Ising machines can be divided in three difficulty classes and we propose an annealing scheme to efficiently solve two of them. Furthermore, we show that changing the physical implementation of the Ising machine can cause a problem to change difficulty class, rendering it potentially a lot more easy to solve.
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.
Solving large-scale quadratic unconstrained binary optimization (QUBO) problems is critical in various fields, including physics, finance, and engineering. However, these problems remain intractable on conventional computing architectures. Alternative solvers, such as Ising machines (IMs) based on networks of coupled electronic, mechanical, or photonic parametric oscillators (POs), have recently been developed. PO-based IMs aim to find the ground state of an Ising Hamiltonian, which encodes the solution to a QUBO problem. However, their analog nature and their energy-minimization process based on gradient descent make PO-based IMs inherently susceptible to identifying inaccurate solutions. In this work, we introduce and validate a QUBO solver—the analog Floquet solver (AFS)—which enhances the dynamics of PO-based IMs by leveraging Floquet states that emerge spontaneously in POs coupled to high-quality-factor resonances. These states enable the AFS to embed periodic time modulation into its energy-minimization process, allowing it to escape local minima during the search for QUBO problem solutions. As a result, the AFS significantly increases the likelihood of identifying accurate solutions compared to conventional PO-based IMs. More generally, this work defines a new paradigm in analog computing—spanning both classical and quantum realms—that can be physically realized with existing technologies across diverse physical domains.
Abstract Ising machines are novel computing devices for the energy minimization of Ising models. These combinatorial optimization problems are of paramount importance for science and technology, but remain difficult to tackle on large scale by conventional electronics. Recently, various photonics‐based Ising machines demonstrated fast computing of a Ising ground state by data processing through multiple temporal or spatial optical channels. Experimental noise acts as a detrimental effect in many of these devices. On the contrary, here we demonstrate that an optimal noise level enhances the performance of spatial‐photonic Ising machines on frustrated spin problems. By controlling the error rate at the detection, we introduce a noisy‐feedback mechanism in an Ising machine based on spatial light modulation. We investigate the device performance on systems with hundreds of individually‐addressable spins with all‐to‐all couplings and we found an increased success probability at a specific noise level. The optimal noise amplitude depends on graph properties and size, thus indicating an additional tunable parameter helpful in exploring complex energy landscapes and in avoiding getting stuck in local minima. Our experimental results identify noise as a potentially valuable resource for optical computing. This concept, which also holds in different nanophotonic neural networks, may be crucial in developing novel hardware with optics‐enabled parallel architecture for large‐scale optimizations.
Abstract Ising machines based on nonlinear analog systems are a promising method to accelerate computation of NP-hard optimization problems. Yet, their analog nature is also causing amplitude inhomogeneity which can deteriorate the ability to find optimal solutions. Here, we investigate how the system’s nonlinear transfer function can mitigate amplitude inhomogeneity and improve computational performance. By simulating Ising machines with polynomial, periodic, sigmoid and clipped transfer functions and benchmarking them with MaxCut optimization problems, we find the choice of transfer function to have a significant influence on the calculation time and solution quality. For periodic, sigmoid and clipped transfer functions, we report order-of-magnitude improvements in the time-to-solution compared to conventional polynomial models, which we link to the suppression of amplitude inhomogeneity induced by saturation of the transfer function. This provides insights into the suitability of nonlinear systems for building Ising machines and presents an efficient way for overcoming performance limitations.
Several continuous dynamical systems have recently been proposed as special-purpose analog computers designed to solve combinatorial optimization problems such as k-SAT or the Ising problem. While combinatorial optimization problems are known to be NP-hard, and thus scale, in the worst case, exponentially with the problem size, these analog solvers promise substantial speed-up and scaling advantages in finding the solution. The underlying algorithms, which can be cast in the form of differential equations, generically involve highly chaotic dynamics and thus assume that the system variables can be processed with, in principle, arbitrary precision. However, both actual physical systems as well as finite digital machines, which are used to virtually emulate the dynamics, can process the evolution only with finite precision, be it because of intrinsic noise or because of limited precision in number representation. We investigate the impact of such noise on the solution-finding capability. To this end, we focus on two representative analog solvers, designed to address the Ising problem and the k-SAT problem, respectively. Our numerical analysis reveals that the ability of these algorithms to find solutions exhibits a threshold behavior under the addition of noise, where the solution-finding capability remains mostly uncompromised below a noise threshold, while it rapidly deteriorates above the threshold. As we show, these noise tolerance thresholds decrease with the problem size, following an approximate algebraic scaling. This allows us to infer principal limits on the problem sizes that can be efficiently tackled with these solvers under given noise levels.