Solving maximum independent set problems with a coherent Ising machine
Hiroki Takesue, Kensuke Inaba, Toshimori Honjo, Takuya Ikuta, Yuya Yonezu, Yasuhiro Yamada, Takahiro Inagaki · 2024
The maximum independent set (MIS) problem is an optimization problem in graph theory and is related to various applications such as network design and resource allocation. Here we report that a coherent Ising machine based on a network of optical parametric oscillators can find large independent sets in graphs that consist of thousands of nodes faster than simulated annealing implemented many-core CPU.