Simulated Oscillator-Based Ising Machine for two Million Nodes Max-Cut Problems

The search for new, unconventional approaches for the solution of combinatorial optimization problems (COPs) is a research topic of great interest in the current post-Moore era. Oscillator-based Ising machines (OIMs) are a promising paradigm, highly compatible with many COPs, that uses coupled oscillators to search for the ground state of an Ising model. In this work, we simulate an OIM by integrating the Kuramoto model. Our implementation performs remarkably well when scaling to very large instances (>1e6 nodes) of maximum cut problems. The performance is analyzed as a function of the graph size and the connection density and compared with well-known conventional algorithms. The software can handle a cubic problem with two million nodes, which is the largest attempted so far in literature.