Improved time complexity for spintronic oscillator Ising machines compared to a popular classical optimization algorithm for the Max-Cut problem

Solving certain combinatorial optimization problems like Max-Cut becomes challenging once the graph size and edge connectivity increase beyond a threshold, with brute-force algorithms which solve such problems exactly on conventional digital computers having the bottleneck of exponential time complexity. Hence currently, such problems are instead solved approximately using algorithms like Goemans-Williamson (GW) algorithm, run on conventional computers with polynomial time complexity. Phase binarized oscillators (PBOs), also often known as oscillator Ising machines, have been proposed as an alternative to solve such problems. In this paper, restricting ourselves to the combinatorial optimization problem Max-Cut solved on three kinds of graphs (Mobius Ladder, random cubic, Erdös Rényi) up to 100 nodes, we empirically show that computation time/time to solution (TTS) for PBOs (captured through Kuramoto model) grows at a much lower rate (logarithmically:O(log(N)), with respect to graph size