Efficient optimization with higher-order ising machines

Area of Science:

• Computational physics
• Quantum computing
• Combinatorial optimization

Background:

• Ising machines are prominent for solving combinatorial optimization problems on parallel hardware.
• Most Ising machines use second-order interactions, but higher-order interactions are better suited for problems like satisfiability.
• Existing second-order Ising machines face limitations with certain optimization problem classes.

Purpose of the Study:

• To demonstrate the resource efficiency of higher-order Ising machines for satisfiability problems.
• To compare the performance of higher-order Ising machines against traditional second-order Ising machines.
• To advance the capabilities of Ising machines for complex computational tasks.

Main Methods:

• Implementing higher-order Ising machines using coupled oscillators.
• Testing performance on a benchmark dataset of Boolean k-satisfiability problems.
• Comparing resource utilization (spin variables, connections) and solution quality.

Main Results:

• Higher-order Ising machines solve satisfiability problems more resource-efficiently than second-order machines.
• The coupled oscillator implementation of higher-order Ising machines rapidly finds better solutions.
• This approach improves the current state-of-the-art for Ising machine performance.

Conclusions:

• Higher-order Ising machines represent a significant advancement for solving specific optimization problems.
• Coupled oscillator implementations offer a promising pathway for efficient and high-performance Ising machines.
• This work enhances the applicability of Ising machines to a broader range of computational challenges.