Higher-order neuromorphic Ising machines—autoencoders and Fowler-Nordheim annealers are all you need for scalability
Faiek Ahsan, Saptarshi Maiti, Zihao Chen, Jakob Kaiser, Ankita Nandi, Madhuvanthi Srivatsav, Johannes Schemmel, Andreas G. Andreou, Jason K. Eshraghian, Chetan Singh Thakur, Shantanu Chakrabartty
We report that an autoencoder-based neuromorphic architecture, combined with Fowler-Nordheim annealing, is sufficient to implement scalable higher-order Ising machines. We show that these machines can consistently produce state-of-the-art solutions with high reliability and with competitive time-to-solution metrics. The autoencoder captures higher-order interactions by decomposing Ising clauses and Ising spins into encoder-decoder layers of spiking neurons, thereby keeping the resource complexity independent of the interaction order for sparse problems. An annealing process based on the dynamics of Fowler-Nordheim quantum mechanical tunneling extrapolates between an $${{\mathcal{O}}}(1/t)$$ annealing schedule and an $${{\mathcal{O}}}(1/\log (t))$$ annealing schedule. This not only ensures fast convergence towards high-quality solutions but also guarantees asymptotic convergence to the Ising ground state. To demonstrate the advantages of the proposed higher-order neuromorphic Ising machine, we systematically solved benchmark combinatorial optimization problems such as MAX-CUT and MAX-SAT, comparing the results to those obtained using a second-order Ising machine employing the same annealing process. The authors demonstrate that an autoencoder-based neuromorphic architecture combined with Fowler-Nordheim annealing, is sufficient to implement scalable higher-order Ising machines. They show that these machines can consistently produce state-of-the-art solutions with high reliability and competitive time-to-solution metrics.
We report that an autoencoder-based neuromorphic architecture, combined with Fowler-Nordheim annealing, is sufficient to implement scalable higher-order Ising machines. We show that these machines can consistently produce state-of-the-art solutions with high reliability and with competitive time-to-solution metrics. The autoencoder captures higher-order interactions by decomposing Ising clauses and Ising spins into encoder-decoder layers of spiking neurons, thereby keeping the resource complexity independent of the interaction order for sparse problems. An annealing process based on the dynamics of Fowler-Nordheim quantum mechanical tunneling extrapolates between an O(1/t) annealing schedule and an O(1/log(t)) annealing schedule. This not only ensures fast convergence towards high-quality solutions but also guarantees asymptotic convergence to the Ising ground state. To demonstrate the advantages of the proposed higher-order neuromorphic Ising machine, we systematically solved benchmark combinatorial optimization problems such as MAX-CUT and MAX-SAT, comparing the results to those obtained using a second-order Ising machine employing the same annealing process. The authors demonstrate that an autoencoder-based neuromorphic architecture combined with Fowler-Nordheim annealing, is sufficient to implement scalable higher-order Ising machines. They show that these machines can consistently produce state-of-the-art solutions with high reliability and competitive time-to-solution metrics.
Neuromorphic computing has so far been driven predominantly by machine-learning workloads, yet its underlying properties also make it particularly well suited to combinatorial optimization problems expressed in Ising or QUBO form. While neuromorphic Ising solvers have been demonstrated, how a given problem should be formulated to best suit neuromorphic dynamics has received far less attention. Maximum-likelihood (ML) channel decoding can be expressed as an Ising/QUBO problem, and two distinct formulations already exist in the quantum-annealing literature: a squared-penalty formulation that uses few spins but produces dense intra-check couplings, and a chain-product formulation that improves locality at the cost of additional auxiliary spins. Both place the ML codeword at the ground state under sufficient constraint enforcement, but they have not been compared under the constraints that neuromorphic hardware imposes. This work provides the first systematic side-by-side comparison of QUBO/Ising formulations of ML decoding for linear codes. We show that the two formulations impose fundamentally different tradeoffs in neuron count, synaptic density, locality, and convergence behavior. The preferred formulation is inseparable from the choice of solver, and the two must be considered jointly. Finally, we show that ground-state correctness alone is an insufficient design criterion, and that signal processing tasks should ideally be co-formulated with their neuromorphic hardware models if neuromorphic computing is to extend into the receiver pipeline.
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.
Ising machines are hardware solvers which aim to find the absolute or approximate ground states of the Ising model. The Ising model is of fundamental computational interest because it is possible to formulate any problem in the complexity class NP as an Ising problem with only polynomial overhead. A scalable Ising machine that outperforms existing standard digital computers could have a huge impact for practical applications for a wide variety of optimization problems. In this review, we survey the current status of various approaches to constructing Ising machines and explain their underlying operational principles. The types of Ising machines considered here include classical thermal annealers based on technologies such as spintronics, optics, memristors, and digital hardware accelerators; dynamical-systems solvers implemented with optics and electronics; and superconducting-circuit quantum annealers. We compare and contrast their performance using standard metrics such as the ground-state success probability and time-to-solution, give their scaling relations with problem size, and discuss their strengths and weaknesses.
Ising machines, quantum annealing (QA) machines, are promising for solving combinatorial optimization problems at high speed. Problems are formulated as Ising models where optimal solutions correspond to ground states, but stochastic noise often causes deviations, necessitating error reduction strategies. The quantum annealing correction (QAC) model introduces penalty spins to favor consistent solutions across replicas and has shown effectiveness in QA, but its behavior under simulated annealing (SA) remains insufficiently understood. This study systematically evaluates the stacked model, a recently proposed error reduction method, against QAC-based and simple parallelization approaches in SA. Our results demonstrate that, even for large-scale systems, the stacked model consistently outperforms alternatives as the number of replicas increases, maintaining relatively high success probability through spontaneous replica alignment via structured coupling. These findings highlight the stacked model as a scalable and error reduction framework for Ising-based optimization.
This research is concerned with an annealing processor for efficiently solving a combinatorial optimization problem.\nIn order to realize a smart society, optimization of people and thingssuch as transportation networks, power networks, human resource allocationand routes is indispensable. Many of these problems are called combinatorial optimization problems and are known as very important problems in modern society. However, it is known that the combinatorial optimization problem is NP-hard and it is difficult to efficiently solve it with a conventional Neumann computer.\nIn recent years, the miniaturization of the process of manufacturing computer chips is approaching the physical limit. Therefore, especially in the solution by the full search, the improvement in speed due to the calculation speed of the computer cannot be expected. From such a background, dedicated hardware capable of solving a combination optimization problem at high speed and with low power consumption has been attracting attention.\nThe annealing processor is a general-purpose combination optimization solver that utilizes the property that the ground state of the optimization problem expressed by using the Ising model and the optimal solution of the combination optimization problem match. The Ising model is a ferromagnetic model in statistical physics expressed by spins having an upward and downward state, spin-spin interactions occurring between the spins, and an external magnetic field acting on each spin. The Ising model can express a combinatorial optimization problem by expressing a control target and a cost using these parameters. The annealing processor updates the spin state while slowly lowering the temperature parameters based on simulated annealing,which is an optimization method learned from natural phenomena generally called annealing. Eventually, the spin will reach the ground state with a high probability and obtain the optimal solution.\nAnnealing processors are classified into two types, the nearest neighbor type and the fully connected type, depending on the shape of the Ising model simulated on the hardware. In the nearest neighbor type, the coupling between spins is limited to only between adjacent spins, and in the full coupling type, coupling exists between arbitrary spins. The nearest neighbor type realizes high parallel processing by reducing the data spin required by simulated annealing by reducing the proximity spin. In addition, since data transfer is limited to adjacent spins, the scalability is high. However, since the spin-to-spin interaction is sparse, there is a problem that the class of combinatorial optimization problems that can be dealt with is limited, or that the problem requires deformation processing to match the Ising model of hardware. The fully connected type can solve any class of problems as long as the number of spins permits, however it requires connections between arbitrary spins.Therefore, scalability is low. Because there there is a dependency on all spins,the number of spins that can be updated at one time is always limited to only one regardless of the total number of spins. Therefore, it takes time to converge to the ground state.\nIn this research, we propose a method of increasing the number of spins for this annealing processor by using (1) a spatially-expanded time-division processing mechanism architecture based on a loosely-coupled type, (2) An algorithm for applying a fully coupled Ising network to a more complex Ising network using the nearest neighbor Ising network and an annealing method that can be updated in parallel, (3)We conducted a study on the architecture of a fully coupled annealing processor for parallel updating annealing.\nAs described above, the research described in this paper contributes to the improvement of the efficiency of the annealing processor for solving the large-scale combinatorial optimization problem from both the fundamental algorithm and the hardware architecture. I hope that this research will solve the combinatorial optimization problem that is expected to increase in demand in the future and contribute to the development of human society.
With the slowdown of improvement in conventional von Neumann systems, increasing attention is paid to novel paradigms such as Ising machines. They have very different approach to solving combinatorial optimization problems. Ising machines have shown great potential in solving binary optimization problems like MaxCut. In this paper, we present an analysis of these systems in boolean satisfiability (SAT) problems. We demonstrate that, in the case of 3-SAT, a basic architecture fails to produce meaningful acceleration, largely due to the relentless progress made in conventional SAT solvers. Nevertheless, careful analysis attributes part of the failure to the lack of two important components: cubic interactions and efficient randomization heuristics. To overcome these limitations, we add proper architectural support for cubic interaction on a state-of-the-art Ising machine. More importantly, we propose a novel semantic-aware annealing schedule that makes the search-space navigation much more efficient than existing annealing heuristics. Using numerical simulations, we show that such an "Augmented" Ising Machine for SAT is projected to outperform state-of-the-art software-based, GPU-based and conventional hardware SAT solvers by orders of magnitude.