Efficient optimization with higher-order ising machines.

Bybee, Connor; Kleyko, Denis; Nikonov, Dmitri E.; Khosrowshahi, Amir; Olshausen, Bruno A.; Sommer, Friedrich T.

A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Boolean k-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines. Combinatorial optimization problems can be solved on parallel hardware called Ising machines. Most studies have focused on the use of second-order Ising machines. Compared to second-order Ising machines, the authors show that higher-order Ising machines realized with coupled-oscillator networks can be more resource-efficient and provide superior solutions for constraint satisfaction problems.

CONSTRAINT satisfaction; COMBINATORIAL optimization; MACHINERY; PROBLEM solving

Nature Communications, 2023, Vol 14, Issue 1, p1

2041-1723

Academic Journal

10.1038/s41467-023-41214-9