Towards higher order oscillatory Ising machines

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 × lower time-to-solution without compromising solution accuracy.