Solving maximum independent set problems with a coherent Ising machine
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.
Authors
- Toshimori Honjo (ORCID: https://orcid.org/0000-0002-2176-9842)
- Takuya Ikuta (ORCID: https://orcid.org/0000-0003-3371-9583)
- Yuya Yonezu (ORCID: https://orcid.org/0000-0001-9024-5551)
- Yasuhiro Yamada (ORCID: https://orcid.org/0000-0002-5372-2141)
- Kensuke Inaba (ORCID: https://orcid.org/0000-0003-1182-4198)
- Takahiro Inagaki (ORCID: https://orcid.org/0000-0003-1322-8744)
- Hiroki Takesue (ORCID: https://orcid.org/0000-0003-1253-9049)
Institutions
- NTT Basic Research Laboratories (JP)
Publication Details
- Published
- 2024-10-02
- DOI
- https://doi.org/10.1117/12.3026866
- Primary Topic
- Machine Learning and Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.00