Combinatorial optimization problems are difficult to solve due to the space explosion in an exhaustive search. Using Ising model-based solvers can efficiently find near-optimal solutions by minimizing the energy of a nonlinear Hamiltonian system. In contrast to Ising machines based on quantum mechanics, classical Ising machines using conventional technologies, such as the complementary metal-oxide-semiconductor, offer efficient implementations with competitive performance. In this paper, we briefly review recently developed simulation algorithms of classical Ising machines. These algorithms are classified by considering various inherent mechanisms in the simulation of physical phenomena. Then, strategies to improve the simulation efficiency are discussed by generalizing their characteristics and behaviours. These simulation algorithms are key for improving the efficiency of classical Ising machines in solving combinatorial optimization problems.
Combinatorial optimization problems are difficult to solve due to the space explosion in an exhaustive search. Using Ising model-based solvers can efficiently find near-optimal solutions by minimizing the energy of a nonlinear Hamiltonian system. In contrast to Ising machines based on quantum mechanics, classical Ising machines using conventional technologies, such as the complementary metal-oxide-semiconductor, offer efficient implementations with competitive performance. In this paper, we briefly review recently developed simulation algorithms of classical Ising machines. These algorithms are classified by considering various inherent mechanisms in the simulation of physical phenomena. Then, strategies to improve the simulation efficiency are discussed by generalizing their characteristics and behaviours. These simulation algorithms are key for improving the efficiency of classical Ising machines in solving combinatorial optimization problems.
Ising machines have received growing interest as efficient and hardware-friendly solvers for combinatorial optimization problems (COPs). They search for the absolute or approximate ground states of the Ising model with a proper annealing process. In contrast to Ising machines built with superconductive or optical circuits, complementary metal-oxide-semiconductor (CMOS) Ising machines offer inexpensive fabrication, high scalability, and easy integration with mainstream semiconductor chips. As low-energy and CMOS-compatible emerging technologies, spintronics and phase-transition devices offer functionalities that can enhance the scalability and sampling performance of Ising machines. In this article, we survey various approaches in the process flow for solving COPs using CMOS, hybrid CMOS-spintronic, and phase-transition devices. First, the methods for formulating COPs as Ising problems and embedding Ising formulations to the topology of the Ising machine are reviewed. Then, Ising machines are classified by their underlying operational principles and reviewed from a perspective of hardware implementation. CMOS solutions are advantageous with denser connectivity, whereas hybrid CMOS-spintronic and phase-transition device-based solutions show great potential in energy efficiency and high performance. Finally, the challenges and prospects are discussed for the Ising formulation, embedding process, and implementation of Ising machines.
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.
Quickly obtaining optimal solutions of combinatorial optimization problems has tremendous value but is extremely difficult. Thus, various kinds of machines specially designed for combinatorial optimization have recently been proposed and developed. Toward the realization of higher-performance machines, here, we propose an algorithm based on classical mechanics, which is obtained by modifying a previously proposed algorithm called simulated bifurcation. Our proposed algorithm allows us to achieve not only high speed by parallel computing but also high solution accuracy for problems with up to one million binary variables. Benchmarking shows that our machine based on the algorithm achieves high performance compared to recently developed machines, including a quantum annealer using a superconducting circuit, a coherent Ising machine using a laser, and digital processors based on various algorithms. Thus, high-performance combinatorial optimization is realized by massively parallel implementations of the proposed algorithm based on classical mechanics.
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.
Combinatorial optimization problems are ubiquitous but difficult to solve. Hardware devices for these problems have recently been developed by various approaches, including quantum computers. Inspired by recently proposed quantum adiabatic optimization using a nonlinear oscillator network, we propose a new optimization algorithm simulating adiabatic evolutions of classical nonlinear Hamiltonian systems exhibiting bifurcation phenomena, which we call simulated bifurcation (SB). SB is based on adiabatic and chaotic (ergodic) evolutions of nonlinear Hamiltonian systems. SB is also suitable for parallel computing because of its simultaneous updating. Implementing SB with a field-programmable gate array, we demonstrate that the SB machine can obtain good approximate solutions of an all-to-all connected 2000-node MAX-CUT problem in 0.5 ms, which is about 10 times faster than a state-of-the-art laser-based machine called a coherent Ising machine. SB will accelerate large-scale combinatorial optimization harnessing digital computer technologies and also offer a new application of computational and mathematical physics.
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.