A coherent Ising machine for 2000-node optimization problems.
The analysis and optimization of complex systems can be reduced to mathematical problems collectively known as combinatorial optimization. Many such problems can be mapped onto ground-state search problems of the Ising model, and various artificial spin systems are now emerging as promising approaches. However, physical Ising machines have suffered from limited numbers of spin-spin couplings because of implementations based on localized spins, resulting in severe scalability problems. We report a 2000-spin network with all-to-all spin-spin couplings. Using a measurement and feedback scheme, we coupled time-multiplexed degenerate optical parametric oscillators to implement maximum cut problems on arbitrary graph topologies with up to 2000 nodes. Our coherent Ising machine outperformed simulated annealing in terms of accuracy and computation time for a 2000-node complete graph.
NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan. inagaki.takahiro@lab.ntt.co.jp takesue.hiroki@lab.ntt.co.jp.
Takahiro
T
Inagaki
Department of Mathematical Informatics, University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-8656, Japan.|Institute of Industrial Science, University of Tokyo, 4-6-1, Komaba, Meguro-ku, Tokyo 153-8505, Japan.|National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan.
Yoshitaka
Y
Haribara
Division of Electrical, Electronic and Information Engineering, Osaka University, Osaka 565-0871, Japan.
Koji
K
Igarashi
National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan.|ERATO Kawarabayashi Large Graph Project, Japan Science and Technology Agency, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan.
Tomohiro
T
Sonobe
National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan.
Shuhei
S
Tamate
NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan.
Toshimori
T
Honjo
E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA.
Alireza
A
Marandi
E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA.
Peter L
PL
McMahon
NTT Device Technology Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan.
Takeshi
T
Umeki
NTT Device Technology Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan.
Koji
K
Enbutsu
NTT Device Technology Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan.
Osamu
O
Tadanaga
NTT Device Technology Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan.
Hirokazu
H
Takenouchi
Department of Mathematical Informatics, University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-8656, Japan.|Institute of Industrial Science, University of Tokyo, 4-6-1, Komaba, Meguro-ku, Tokyo 153-8505, Japan.
Kazuyuki
K
Aihara
National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan.|ERATO Kawarabayashi Large Graph Project, Japan Science and Technology Agency, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan.
Ken-Ichi
KI
Kawarabayashi
Division of Electrical, Electronic and Information Engineering, Osaka University, Osaka 565-0871, Japan.
Kyo
K
Inoue
National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan.
Shoko
S
Utsunomiya
NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan. inagaki.takahiro@lab.ntt.co.jp takesue.hiroki@lab.ntt.co.jp.
Hiroki
H
Takesue