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

Scientific Reports

Oscillator-based Ising machine applied for Max-Cut in massively large and sparse graphs

Luciano Mazza, Eleonora Raimondo, Mario Carpentieri, Giovanni Finocchio, Vito Puliafito

Published Aug 26, 2026• 0 citations
Publisher

Abstract

Solving large-scale combinatorial optimization problems, such as Max-Cut, is crucial for a variety of applications such as network analysis and finance. Ising machines are emerging as unconventional computing paradigms for facing those problems while promising to reduce energy consumption and time-to-solution as compared to traditional methods such as the Goemans-Williamson algorithm. Here, we implement and benchmark a Graphics Processing Unit (GPU)-native software-based implementation of oscillator-based Ising machine (OIM) which can solve Max-Cut problems up to 20 million spins within a regular graph with degree 25. The benchmarked implementation is running on a single GPU, but it is scalable to multi-GPU platforms. Additionally, we identify an annealing strategy that searches the ground state with the help of dynamical checkpoints as bifurcation points in the dynamical phase space of the Max-Cut problems mapped into the Ising Hamiltonian, enabling the algorithm for a fast local search. The OIM consistently achieves accuracy averaging above 99.5% (up to 99.9%) for G-set problems.

DOI
10.1038/s41598-026-66268-9

Related papers

A comparison of Oscillatory Ising Machines and Simulated Bifurcation Machines for Solving Maximum Cut Problems

Md Shabaz Ansari, Hemkant Nehete, Andrea Grimaldi +5 more

Unconventional computing approaches have gained significant attention in the search for hardware-friendly solvers capable of finding the solution of combinatorial optimization problems COPs. Among others, oscillator-based, or oscillatory, Ising machines (OIMs), and simulated bifurcation-based Ising machines (SBMs) are two promising paradigms that are based on dynamical equations. This work presents a preliminary direct software comparison between an OIM and an SBM on instances from the G-set, a well-known benchmark library of maximum cut problems. The performance of the two paradigms is compared in terms of their average optimal approximation within a given number of timesteps using the same integration scheme. Our findings show that OIM performs better when optimizing its parameter for a specific problem or topology, while SBM has better performance in scenarios in which preprocessing is not possible, i.e., when considering large batches of instances with varied topologies and scales.

IEEE International Conference on Nanotechnology (IEEE-NANO)•Jul 8, 2024•2 citations

GPU-Accelerated Simulated Oscillator Ising/Potts Machine Solving Combinatorial Optimization Problems

Yilmaz Ege Gonul, Ceyhun Efe Kayan, Ilknur Mustafazade +2 more

Oscillator-based Ising machines (OIMs) and oscillator-based Potts machines (OPMs) have emerged as promising hardware accelerators for solving NP-hard combinatorial optimization problems by leveraging the phase dynamics of coupled oscillators. In this work, a GPU-accelerated simulated OIM/OPM digital computation framework capable of solving combinatorial optimization problems is presented. The proposed implementation harnesses the parallel processing capabilities of GPUs to simulate large-scale OIM/OPMs, leveraging the advantages of digital computing to offer high precision, programmability, and scalability. The performance of the proposed GPU framework is evaluated on the max-cut problems from the GSET benchmark dataset and graph coloring problems from the SATLIB benchmarks dataset, demonstrating competitive speed and accuracy in tackling large-scale problems. The results from simulations, reaching up to 11295x speed-up over CPUs with up to 99% accuracy, establish this framework as a scalable, massively parallelized, and high-fidelity digital realization of OIM/OPMs.

arXiv:2505.22631•ACM Great Lakes Symposium on VLSI (GLSVLSI)•Jun 27, 2025•2 citations

Accelerating the Max-Cut Problems via Distributed Ising Machine Solvers

Xing-Yu Wu, Yi-Xin Zhang, Chen-rui Fan +1 more

The Ising machine, as a quantum-inspired computing system, can be used to efficiently solve combinatorial optimization problems. Ongoing studies have positioned it to potentially surpass the performance limitations of traditional computers. However, such Ising machines also suffer from scalability as the solution quality becomes sub-optimal when the problem size increases. In this work, we propose an Ising-based framework that uses a distributed Ising algorithm to find the near-optimal solution for large-scale Max-Cut problems through parallel processing via graph segmentation and reassembly. We selected the coherent Ising machine as the hardware solver and successfully found the solution for a 2000-node instance utilizing 20 computational bits on the Gset standard dataset. Additionally, we investigated the key factors influencing the system's performance and discovered that setting the number of reorganizations to one results in higher accuracy. Building on this configuration, we utilized a 100-bit CIM hardware platform (CPQC-1) to solve instances with varying numbers of nodes. The experimental results agree well with the theoretical simulations, confirming the practical feasibility of our method. Moreover, compared to existing Ising-based solvers, our algorithm significantly reduces computational resource requirements while achieving superior performance on large-scale combinatorial optimization problems, highlighting its effectiveness on quantum-inspired hardware.

IEEE Transactions on Quantum Engineering•Jan 1, 2026•0 citations

FPGA-Based Simulated Bifurcation Machine

Kosuke Tatsumura, A. R. Dixon, Hayato Goto

Since many combinatorial optimization problems can be mapped onto ground-state search problems of Ising models, special-purpose machines for Ising problems have attracted intense attention. Simulated bifurcation (SB) is a recently proposed algorithm to solve these Ising problems. One of the remarkable features of SB is the high-degree parallelism underlying in the algorithm, providing an opportunity to solve the Ising problems very fast by massively parallel processing. In this work, we implement the SB algorithm on FPGAs by designing massively parallel custom circuits. We then compare the FPGA-based SB machines with a state-of-the-art machine called a coherent Ising machine (CIM), a highly optimized implementation of simulated annealing (SA), and GPU-based SB machines. SB machines with spin size of 2,048/4,096 (2K/4K) on an Arria10 GX1150 FPGA have 8,192 processing elements for the matrix-vector multiplication (MM) modules (the most computationally intensive part) and achieve computation throughput of 1,873/2,027 GMAC/s for the MM modules, outperforming 2K/4K SB machines on an Nvidia Tesla V100 GPU (113/183 GMAC/s). The 2K FPGA-SB solves all-to-all connected 2000-node MAX-CUT problem 14X (/124X) faster than the CIM (/the highly-optimized SA), with much better energy efficiency (288X better than the CIM).

International Conference on Field Programmable Logic and Applications (FPL)•Sep 1, 2019•80 citations

A coherent Ising machine for 2000-node optimization problems

Takahiro Inagaki, Yoshitaka Haribara, Koji Igarashi +14 more

The analysis and optimization of complex systems can be reduced to mathematical problems collectively known as combinatorial optimization. Many such problems can be mapped onto ground-state search problems of the Ising model, and various artificial spin systems are now emerging as promising approaches. However, physical Ising machines have suffered from limited numbers of spin-spin couplings because of implementations based on localized spins, resulting in severe scalability problems. We report a 2000-spin network with all-to-all spin-spin couplings. Using a measurement and feedback scheme, we coupled time-multiplexed degenerate optical parametric oscillators to implement maximum cut problems on arbitrary graph topologies with up to 2000 nodes. Our coherent Ising machine outperformed simulated annealing in terms of accuracy and computation time for a 2000-node complete graph.

Science•Oct 21, 2016•799 citations

A GPU-Based Ising Machine With a Multi-Spin-Flip Capability for Constrained Combinatorial Optimization

Satoru Jimbo, Tatsuhiko Shirai, Nozomu Togawa +2 more

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.

IEEE Access•Jan 1, 2024•8 citations
Solving large-scale combinatorial optimization problems, such as Max-Cut, is crucial for a variety of applications such as network analysis and finance. Ising machines are emerging as unconventional computing paradigms for facing those problems while promising to reduce energy consumption and time-to-solution as compared to traditional methods such as the Goemans-Williamson algorithm. Here, we implement and benchmark a Graphics Processing Unit (GPU)-native software-based implementation of oscillator-based Ising machine (OIM) which can solve Max-Cut problems up to 20 million spins within a regular graph with degree 25. The benchmarked implementation is running on a single GPU, but it is scalable to multi-GPU platforms. Additionally, we identify an annealing strategy that searches the ground state with the help of dynamical checkpoints as bifurcation points in the dynamical phase space of the Max-Cut problems mapped into the Ising Hamiltonian, enabling the algorithm for a fast local search. The OIM consistently achieves accuracy averaging above 99.5% (up to 99.9%) for G-set problems.
Unconventional computing approaches have gained significant attention in the search for hardware-friendly solvers capable of finding the solution of combinatorial optimization problems COPs. Among others, oscillator-based, or oscillatory, Ising machines (OIMs), and simulated bifurcation-based Ising machines (SBMs) are two promising paradigms that are based on dynamical equations. This work presents a preliminary direct software comparison between an OIM and an SBM on instances from the G-set, a well-known benchmark library of maximum cut problems. The performance of the two paradigms is compared in terms of their average optimal approximation within a given number of timesteps using the same integration scheme. Our findings show that OIM performs better when optimizing its parameter for a specific problem or topology, while SBM has better performance in scenarios in which preprocessing is not possible, i.e., when considering large batches of instances with varied topologies and scales.
Oscillator-based Ising machines (OIMs) and oscillator-based Potts machines (OPMs) have emerged as promising hardware accelerators for solving NP-hard combinatorial optimization problems by leveraging the phase dynamics of coupled oscillators. In this work, a GPU-accelerated simulated OIM/OPM digital computation framework capable of solving combinatorial optimization problems is presented. The proposed implementation harnesses the parallel processing capabilities of GPUs to simulate large-scale OIM/OPMs, leveraging the advantages of digital computing to offer high precision, programmability, and scalability. The performance of the proposed GPU framework is evaluated on the max-cut problems from the GSET benchmark dataset and graph coloring problems from the SATLIB benchmarks dataset, demonstrating competitive speed and accuracy in tackling large-scale problems. The results from simulations, reaching up to 11295x speed-up over CPUs with up to 99% accuracy, establish this framework as a scalable, massively parallelized, and high-fidelity digital realization of OIM/OPMs.
The Ising machine, as a quantum-inspired computing system, can be used to efficiently solve combinatorial optimization problems. Ongoing studies have positioned it to potentially surpass the performance limitations of traditional computers. However, such Ising machines also suffer from scalability as the solution quality becomes sub-optimal when the problem size increases. In this work, we propose an Ising-based framework that uses a distributed Ising algorithm to find the near-optimal solution for large-scale Max-Cut problems through parallel processing via graph segmentation and reassembly. We selected the coherent Ising machine as the hardware solver and successfully found the solution for a 2000-node instance utilizing 20 computational bits on the Gset standard dataset. Additionally, we investigated the key factors influencing the system's performance and discovered that setting the number of reorganizations to one results in higher accuracy. Building on this configuration, we utilized a 100-bit CIM hardware platform (CPQC-1) to solve instances with varying numbers of nodes. The experimental results agree well with the theoretical simulations, confirming the practical feasibility of our method. Moreover, compared to existing Ising-based solvers, our algorithm significantly reduces computational resource requirements while achieving superior performance on large-scale combinatorial optimization problems, highlighting its effectiveness on quantum-inspired hardware.
Since many combinatorial optimization problems can be mapped onto ground-state search problems of Ising models, special-purpose machines for Ising problems have attracted intense attention. Simulated bifurcation (SB) is a recently proposed algorithm to solve these Ising problems. One of the remarkable features of SB is the high-degree parallelism underlying in the algorithm, providing an opportunity to solve the Ising problems very fast by massively parallel processing. In this work, we implement the SB algorithm on FPGAs by designing massively parallel custom circuits. We then compare the FPGA-based SB machines with a state-of-the-art machine called a coherent Ising machine (CIM), a highly optimized implementation of simulated annealing (SA), and GPU-based SB machines. SB machines with spin size of 2,048/4,096 (2K/4K) on an Arria10 GX1150 FPGA have 8,192 processing elements for the matrix-vector multiplication (MM) modules (the most computationally intensive part) and achieve computation throughput of 1,873/2,027 GMAC/s for the MM modules, outperforming 2K/4K SB machines on an Nvidia Tesla V100 GPU (113/183 GMAC/s). The 2K FPGA-SB solves all-to-all connected 2000-node MAX-CUT problem 14X (/124X) faster than the CIM (/the highly-optimized SA), with much better energy efficiency (288X better than the CIM).
The analysis and optimization of complex systems can be reduced to mathematical problems collectively known as combinatorial optimization. Many such problems can be mapped onto ground-state search problems of the Ising model, and various artificial spin systems are now emerging as promising approaches. However, physical Ising machines have suffered from limited numbers of spin-spin couplings because of implementations based on localized spins, resulting in severe scalability problems. We report a 2000-spin network with all-to-all spin-spin couplings. Using a measurement and feedback scheme, we coupled time-multiplexed degenerate optical parametric oscillators to implement maximum cut problems on arbitrary graph topologies with up to 2000 nodes. Our coherent Ising machine outperformed simulated annealing in terms of accuracy and computation time for a 2000-node complete graph.
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.