Format

Send to

Choose Destination
Science. 2016 Nov 4;354(6312):603-606. Epub 2016 Oct 20.

A coherent Ising machine for 2000-node optimization problems.

Author information

1
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.
2
Department of Mathematical Informatics, University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-8656, Japan.
3
Institute of Industrial Science, University of Tokyo, 4-6-1, Komaba, Meguro-ku, Tokyo 153-8505, Japan.
4
National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan.
5
Division of Electrical, Electronic and Information Engineering, Osaka University, Osaka 565-0871, Japan.
6
ERATO Kawarabayashi Large Graph Project, Japan Science and Technology Agency, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo 101-8403, Japan.
7
NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan.
8
E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA.
9
NTT Device Technology Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan.

Abstract

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.

PMID:
27811271
DOI:
10.1126/science.aah4243

Supplemental Content

Full text links

Icon for HighWire
Loading ...
Support Center