RESUMEN
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 sizeN) compared to GW algorithm, for which TTS increases as square of graph size (O(N2)). However, Kuramoto model being a physics-agnostic mathematical model, this time complexity/ TTS trend for PBOs is a general trend and is device-physics agnostic. So for more specific results, we choose spintronic oscillators, known for their high operating frequency (in GHz), and model them through Slavin's model which captures the physics of their coupled magnetization oscillation dynamics. We thereby empirically show that TTS of spintronic oscillators also grows logarithmically with graph size (O(log(N)), while their accuracy is comparable to that of GW. So spintronic oscillators have improved time complexity over GW algorithm. For large graphs, they are expected to compute Max-Cut values much faster than GW algorithm, as well as other oscillators operating at lower frequencies, while maintaining the same level of accuracy.
RESUMEN
Mutual synchronization of N serially connected spintronic nano-oscillators boosts their coherence by N and peak power by N2. Increasing the number of synchronized nano-oscillators in chains holds significance for improved signal quality and emerging applications such as oscillator based unconventional computing. We successfully fabricate spin Hall nano-oscillator chains with up to 50 serially connected nanoconstrictions using W/NiFe, W/CoFeB/MgO, and NiFe/Pt stacks. Our experiments demonstrate robust and complete mutual synchronization of 21 nanoconstrictions at an operating frequency of 10 GHz, achieving line widths <134 kHz and quality factors >79,000. As the number of mutually synchronized oscillators increases, we observe a quadratic increase in peak power, resulting in 400-fold higher peak power in long chains compared to individual nanoconstrictions. While chains longer than 21 nanoconstrictions also achieve complete mutual synchronization, it is less robust, and their signal quality does not improve significantly, as they tend to break into partially synchronized states.