Towards higher order oscillatory Ising machines

Abstract

Abstract Ising machines as hardware solvers of combinatorial optimization problems (COPs) can efficiently explore large solution spaces due to their inherent parallelism and physics-based dynamics. Many important COPs such as satisfiability (SAT) assume arbitrary interactions between problem variables, while most Ising machines only support pairwise (second-order) interactions. This necessitates translation of higher-order interactions to pairwise, which typically results in extra variables not corresponding to problem variables, and a larger problem for the Ising machine to solve than the original problem. This in turn can significantly increase time-to-solution and/or degrade solution accuracy. In this paper, considering a representative CMOS-compatible class of Ising machines, we propose a practical design to enable direct hardware support for higher order interactions. By minimizing the overhead of problem translation and mapping, our design can result in up to 4 $$\times$$ lower time-to-solution without compromising solution accuracy.