Impacts of graph structure on the computational properties of oscillator Ising machines

Many combinatorial optimization problems (COPs) can be mapped to Ising Hamiltonians. Oscillator Ising machines (OIMs) are built to minimize the Ising Hamiltonians, thereby indirectly solving the COPs. Specifically, the dynamics of an OIM evolve in the direction of decreasing value of the Ising Hamiltonian, and its state converges to a steady state, known as an asymptotically stable equilibrium point. Such an equilibrium point represents a candidate solution of the underlying COP. Although OIMs show great potential in solving COPs, they, like many heuristic algorithms, are prone to getting stuck in local minima. Even for trivial problems, e.g., unfrustrated Ising Hamiltonians, an OIM may get trapped in local minima if its parameters and its initial condition are not properly selected. In this work, we examine the impacts of the graph structure underlying an OIM on the computational properties of the OIM. In particular, we identify graph structures of OIMs for which the parameters of the OIMs can be properly designed such that only the equilibrium points representing global minima are asymptotically stable and all other equilibrium points are unstable. Thus, an OIM with such a graph structure, possibly with a small perturbation, can converge to the globally optimal solutions from any initial condition.