Abstract
Oscillator-based Ising machines (OIMs) encode binary spins with the phases of decoupled nonlinear oscillators and provide a physical method of combinatorial optimization. However, the dynamics of their continuous phase may not optimize the Ising energy after binary decoding: weak injection allows exploration but distorts the effective Ising field but strong injection refreezes the dynamics in metastable states. This thesis explores this trade-off based on statisticalphysics analysis and numerical benchmarks and suggests a digitized oscillator Ising machine (digOIM) to answer it.
In the case of the standard OIM of the SherringtonKirkpatrick (SK) model, a replicasymmetric theory is established which is expressed in longitudinal and transverse order parameters and susceptibilities, with a correction of spin flips at decoding boundaries. The analysis associates phase locking with decoded Ising energy and demonstrates why binarization and optimization performance do not necessarily go hand in hand. This finding is supported by numerical simulations: the standard OIM approaches the decoded energy of about −0.735 around its dynamical transition, whereas more intense locking is able to deteriorate the solution.
The digOIM is also inspired by the phase structure of analog Ising machines, but it digitalizes the information being exchanged in the coupling network but still uses continuous phase variables to be explored with noise assistance. The decoded spin is conveyed by each oscillator, in such a way that the interaction is dictated by the local Ising field. In the experiments reported, digOIM with phase decoding to branch matching and temperature annealing attains the finite-size SK reference energy of around −0.761. On 21 G-set Max-Cut problems, it has a total deviation of 17 out of the known best cuts, which is 92 on the standard OIM and 101 on a shaped-potential version. These findings reveal that digitized interaction, as opposed to increased local locking, is a promising design principle of phase-based Ising machines.