Finding independent sets in large-scale graphs with a coherent Ising machine.

Area of Science:

• Quantum computing and optimization
• Physical implementations of computational models

Background:

• Ising machines, physical systems for combinatorial optimization, offer potential computational advantages over digital computers.
• Maximum independent set problems are crucial in various real-world optimization scenarios.

Purpose of the Study:

• To demonstrate the capability of a coherent Ising machine (CIM) using degenerate optical parametric oscillator (DOPO) pulses for solving large-scale maximum independent set problems.
• To compare the performance of the CIM against optimized simulated annealing algorithms on digital computers.

Main Methods:

• Implementation of a stable external field for each Ising spin via interaction between DOPO pulses and ferromagnetically coupled auxiliary pulses.
• Utilizing the CIM to find independent sets for dense graphs.

Main Results:

• The CIM successfully identified independent sets for dense graphs containing up to 40,000 nodes.
• The CIM demonstrated superior performance compared to CPU-based simulated annealing for graph sizes exceeding several thousand nodes, particularly in the time required to find approximate solutions.

Conclusions:

• Coherent Ising machines based on DOPO pulses are effective for tackling large-scale maximum independent set problems.
• CIMs present a promising alternative to digital computation for specific complex optimization tasks, offering significant speedups for large problem instances.