Efficient optimization with higher-order ising machines

Connor Bybee

doi:10.1038/s41467-023-41214-9

Return

Efficient optimization with higher-order ising machines

2023-09-27

Sommer, Friedrich T. *

DOI：10.1038/s41467-023-41214-9

Original

Save

View PDF

Abstract

En 中文

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.

Keywords:

NEURAL-NETWORKS

FACTORIZATION

CIRCUITS

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.