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 ($10^3$ spins) to ultra-large ($10^8$ spins).
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).
Ising machines are domain-specific computers that solve combinatorial optimization problems (COPs). They utilize an Ising model to represent a COP and search for the optimal spin configuration of the Ising model to solve the COP. Most Ising machines are based on simulated annealing (SA) and update the spin configuration according to single-spin-flip Markov Chain Monte Carlo methods. However, supporting a multi-spin flip is important to enhance the search performance of SA-based Ising machines when constrained COPs are solved. In this paper, we extend the merge method, which was introduced to provide a multi-spin-flip capability for SA-based Ising machines, and formulate it as a series of matrix multiplications that can be executed on a graphics processing unit (GPU) efficiently. We then construct a GPU-based Ising machine that implements the GPU-oriented merge method together with an extended SA algorithm. We finally demonstrate its superiority over the state-of-the-art GPU-based Ising machine for quadratic knapsack problems.
Combinatorial optimization problems are central to many challenges in logistics, finance, engineering, and the life sciences, yet they remain among the most computationally demanding. Many of these problems can be mapped onto the Ising model, in which binary spins interact through a network of couplings, and solutions correspond to low-energy, ideally ground-state, spin configurations. Photonic Ising machines have the potential to be fast and energy-efficient heuristic solvers of optimization problems by leveraging the low latency, high bandwidth, and inherent parallelism of optics. However, current photonic implementations remain limited in scalability, connectivity, reconfigurability, and time-to-solution, preventing their use in many practical applications. In this perspective, we examine the current landscape of photonic Ising machines, discuss the challenges and limitations of existing platforms, and identify the scientific and technological advances needed to realize large-scale systems. These developments could establish photonic Ising machines as useful hardware platforms for practical optimization.
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.
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.
An Ising machine (IM), as a type of analog computer tailored for tackling intractable combinatorial optimization problems, has attracted remarkable attention in recent years. In contrast to the blossoming field of bespoke IM hardware, developing metaheuristics from IMs remains largely uninvestigated. Here, we propose a physics-inspired evolutionary computation paradigm, termed the Ising optimization framework (IOF); it comprises a unique Ising algorithm and a hybrid annealing scheme, which together are well-suited for solving quadratic unconstrained binary optimization (QUBO) problems embedded in Ising system energy. The Ising algorithm leverages a set of iterated self-mapping functions to evolve an Ising-spin swarm, enabling efficient energy minimization in artificial Ising systems while mitigating detrimental chaos. Complementing the algorithm, a hybrid annealing scheme integrating singular value dropout, bifurcation control, and a nudging strategy, is devised to augment the overall optimization capacity. The effectiveness of the IOF is validated on various Ising and Max-cut problems with decision variables ranging from 625 to 5000 in number. In comparison to four major types of methods for solving QUBOs, including IM simulations, nature-inspired algorithms, a state-of-the-art heuristic, and the commercial solver Gurobi, the IOF consistently demonstrates notable optimization quality and computational efficiency. This paper provides a theoretical foundation and practical guidelines for bridging Ising-inspired approaches with evolutionary computation, offering an evolutionary perspective on Ising optimizations and suggesting a fertile avenue for future research and application.
One of the vital roles of computing is to solve large-scale combinatorial optimization problems in a short time. In recent years, methods have been proposed that map optimization problems to ones of searching for the ground state of an Ising model by using a stochastic process. Simulated annealing (SA) is a representative algorithm. However, it is inherently difficult to perform a parallel search. Here we propose an algorithm called momentum annealing (MA), which, unlike SA, updates all spins of fully connected Ising models simultaneously and can be implemented on GPUs that are widely used for scientific computing. MA running in parallel on GPUs is 250 times faster than SA running on a modern CPU at solving problems involving 100 000 spin Ising models.