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

Combinatorial optimizers using physical systems, or "Ising machines," have been intensively studied as a way of computation that is more efficient than current digital computers. Here, we demonstrate that a coherent Ising machine (CIM) based on degenerate optical parametric oscillator (DOPO) pulses can find solutions to large-scale maximum independent set problems, which is an essential optimization problem that is closely related to real-world optimization tasks. We implemented a stable external field for each Ising spin as an interaction between a DOPO pulse and a group of ferromagnetically coupled auxiliary pulses. Consequently, the CIM delivered independent sets for dense graphs with up to 40,000 nodes. We compared the performance of the CIM with that of optimized simulated annealing algorithm implemented on a digital computer and found that the CIM outperformed the central processing unit (CPU) in terms of the time needed to obtain good approximate solutions when the graph size exceeded several thousand nodes.