Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Circuits and Systems proceedings

A Review of Simulation Algorithms of Classical Ising Machines for Combinatorial optimization

Tingting Zhang, Qichao Tao, Bailiang Liu, Jie Han

Published May 28, 2022• 17 citations
Publisher

Abstract

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.

DOI
10.1109/iscas48785.2022.9937767

Related papers

A Review of Ising Machines Implemented in Conventional and Emerging Technologies

Tingting Zhang, Qichao Tao, Bailiang Liu +9 more

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.

IEEE Transactions on Nanotechnology•Jan 1, 2024•35 citations

Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization

Junpeng Hou, Amin Barzegar, Helmut G. Katzgraber

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.

arXiv:2503.15427•Physical review. E•Jul 1, 2025•4 citations

High-performance combinatorial optimization based on classical mechanics

Hayato Goto, Kotaro Endo, Masaru Suzuki +6 more

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.

Science Advances•Feb 3, 2021•262 citations

Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems

Hayato Goto, Kosuke Tatsumura, A. R. Dixon

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.

Science Advances•Apr 5, 2019•456 citations

Performance analysis of classical adiabatic annealing on Ising machines

Jacob Lamers, Guy Verschaffelt, Guy Van der Sande

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.

quant-pharXiv:2606.07331•Communications Physics•Jun 8, 2026•0 citations

Enumeration algorithms for combinatorial problems using Ising machines: When should we stop exploring energy landscapes?

Yuta Mizuno, Ali, Mohammad, Tamiki Komatsuzaki

Combinatorial problems such as combinatorial optimization and constraint satisfaction problems arise in decision-making across various fields of science and technology. In real-world applications, when multiple optimal or constraint-satisfying solutions exist, enumerating all these solutions is often desirable, as it provides flexibility in decision-making. However, combinatorial problems and their enumeration versions pose significant computational challenges due to combinatorial explosion. To address these challenges, we propose enumeration algorithms for combinatorial optimization and constraint satisfaction problems using Ising machines. Ising machines are specialized devices designed to efficiently solve combinatorial problems by exploring the energy landscape of an Ising model. Ising machines typically sample lower-energy solutions with higher probability. Our enumeration algorithms repeatedly perform such sampling to collect all desirable solutions. The crux of the proposed algorithms lies in their stopping criteria for sampling-based energy landscape exploration, which are derived from probability theory. In particular, the proposed algorithms have theoretical guarantees that the failure probability of enumeration is bounded above by a user-specified value, provided that lower-cost solutions are sampled more frequently and equal-cost solutions are sampled with equal probability. Many physics-based Ising machines are expected to (approximately) satisfy these conditions. As a demonstration, we applied our algorithm using simulated annealing to maximum clique enumeration on random graphs. We found that our algorithm enumerates all maximum cliques in large, dense graphs faster than a conventional branch-and-bound algorithm specifically designed for maximum clique enumeration. These findings underscore the effectiveness and potential of our proposed approach.

arXiv:2412.00284•Nov 29, 2024•2 citations
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.
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.
Combinatorial problems such as combinatorial optimization and constraint satisfaction problems arise in decision-making across various fields of science and technology. In real-world applications, when multiple optimal or constraint-satisfying solutions exist, enumerating all these solutions is often desirable, as it provides flexibility in decision-making. However, combinatorial problems and their enumeration versions pose significant computational challenges due to combinatorial explosion. To address these challenges, we propose enumeration algorithms for combinatorial optimization and constraint satisfaction problems using Ising machines. Ising machines are specialized devices designed to efficiently solve combinatorial problems by exploring the energy landscape of an Ising model. Ising machines typically sample lower-energy solutions with higher probability. Our enumeration algorithms repeatedly perform such sampling to collect all desirable solutions. The crux of the proposed algorithms lies in their stopping criteria for sampling-based energy landscape exploration, which are derived from probability theory. In particular, the proposed algorithms have theoretical guarantees that the failure probability of enumeration is bounded above by a user-specified value, provided that lower-cost solutions are sampled more frequently and equal-cost solutions are sampled with equal probability. Many physics-based Ising machines are expected to (approximately) satisfy these conditions. As a demonstration, we applied our algorithm using simulated annealing to maximum clique enumeration on random graphs. We found that our algorithm enumerates all maximum cliques in large, dense graphs faster than a conventional branch-and-bound algorithm specifically designed for maximum clique enumeration. These findings underscore the effectiveness and potential of our proposed approach.