  Solving combinatorial optimization problems efficiently through emerging
hardware by converting the problem to its equivalent Ising model and obtaining
its ground state is known as Ising computing. Phase-binarized oscillators
(PBO), modeled through the Kuramoto model, have been proposed for Ising
computing, and various device technologies have been used to experimentally
implement such PBOs. In this paper, we show that an array of four
dipole-coupled uniform-mode spin Hall nano oscillators (SHNOs) can be used to
implement such PBOs and solve the NP-Hard combinatorial problem MaxCut on
4-node complete weighted graphs. We model the spintronic oscillators through
two techniques: an approximate model for coupled magnetization dynamics of spin
oscillators, and Landau Lifshitz Gilbert Slonckzweski (LLGS) equation-based
more accurate magnetization dynamics modeling of such oscillators. Next, we
compare the performance of these room-temperature-operating spin oscillators,
as well as generalized PBOs, with two other alternative methods that solve the
same MaxCut problem: a classical approximation algorithm, known as
Goemans-Williamson's (GW) algorithm, and a Noisy Intermediate Scale Quantum
(NISQ) algorithm, known as Quantum Approximation Optimization Algorithm (QAOA).
For four types of graphs, with graph size up to twenty nodes, we show that
approximation ratio (AR) and success probability (SP) obtained for generalized
PBOs (Kuramoto model), as well as spin oscillators, are comparable to that for
GW and much higher than that of QAOA for almost all graph instances. Moreover,
unlike GW, the time to solution (TTS) for generalized PBOs and spin oscillators
does not grow with graph size for the instances we have explored. This can be a
major advantage for PBOs in general and spin oscillators specifically for
solving these types of problems, along with the accuracy of solutions they
deliver.
