A coherent Ising machine for 2000-node optimization problems
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.
Additional Information
© 2016, American Association for the Advancement of Science. 8 July 2016; accepted 26 September 2016. Published online 20 October 2016. Supported by the Impulsing Paradigm Change Through Disruptive Technologies (ImPACT) Program of the Council of Science, Technology and Innovation (Cabinet Office, Government of Japan). We thank H. Nishimori for fruitful discussions, K. Inaba for fruitful discussions, and H. Tamura for various types of support during this research. S.U. and H. Takesue are inventors on patent application PCT/JP2015/059057 submitted by the National Institute of Informatics (NII) and Nippon Telegraph and Telephone (NTT) Corporation that covers the coherent Ising machine based on the measurement and feedback scheme. A.M. and S.U. are inventors on patent application PCT/US2014/046025 submitted by Stanford University and NII that covers the implementation of a coherent Ising machine using degenerate optical parametric oscillators. T.U., K.E., and H. Takenouchi are inventors on patent application PCT/JP1012/000360 submitted by NTT that covers the configurations of phase-sensitive amplifiers based on periodically poled lithium niobate waveguides.Attached Files
Supplemental Material - Inagaki.SM.pdf
Files
| Name | Size | Download all |
|---|---|---|
|
md5:51f09558e5aeaa0bcf8c1ac5988ff10d
|
1.2 MB | Preview Download |
Additional details
- Eprint ID
- 86952
- DOI
- 10.1126/science.aah4243
- Resolver ID
- CaltechAUTHORS:20180608-164534310
- Council of Science, Technology and Innovation (Japan)
- Created
-
2018-06-11Created from EPrint's datestamp field
- Updated
-
2021-11-15Created from EPrint's last_modified field