A scalable photonic computer solving the subset sum problem

Xu, Xiao-Yun1,2; Huang, Xuan-Lun1,2; Li, Zhan-Ming1,2; Gao, Jun1,2; Jiao, Zhi-Qiang1,2; Wang, Yao1,2; Ren, Ruo-Jing1,2; Zhang, H.P.3; Jin, Xian-Min1,2,4

2020

10.1126/sciadv.aay5853

Science Advances   影响因子和分区

23752548

The subset sum problem (SSP) is a typical nondeterministic-polynomial-time (NP)-complete problem that is hard to solve efficiently in time with conventional computers. Photons have the unique features of high propagation speed, strong robustness, and low detectable energy level and therefore can be promising candidates to meet the challenge. Here, we present a scalable chip built-in photonic computer to efficiently solve the SSP. We map the problem into a three-dimensional waveguide network through a femtosecond laser direct writing technique. We show that the photons sufficiently dissipate into the networks and search for solutions in parallel. In the case of successive primes, our approach exhibits a dominant superiority in time consumption even compared with supercomputers. Our results confirm the ability of light to realize computations intractable for conventional computers, and suggest the SSP as a good benchmarking platform for the race between photonic and conventional computers on the way toward "photonic supremacy".
Copyright © 2020 The Authors, some rights reserved.

SCI ; EI

英语

NI期刊

通讯

Shanghai Municipal Education Commission[2017-01-07-00-02-E00049] ; Program for Professor of Special Appointment (Eastern Scholar) at Shanghai Institutions of Higher Learning[GZ2016004] ; [2017YFA0303700] ; Science and Technology Commission of Shanghai Municipality[17JC1400403] ; National Natural Science Foundation of China[61734005]

Science & Technology - Other Topics

Multidisciplinary Sciences

WOS:000512904600027

American Association for the Advancement of Science

20200608139697

Polynomial approximation ; Supercomputers

Digital Computers and Systems:722.4 ; Numerical Methods:921.6 ; Atomic and Molecular Physics:931.3

Web of Science

1.Center for Integrated Quantum Information Technologies (IQIT), School of Physics and Astronomy, State Key Laboratory of Advanced Optical Communication Systems and Networks, Shanghai Jiao Tong University, Shanghai; 200240, China
2.CAS, Center for Excellence and Synergetic Innovation Center in Quantum Information and Quantum Physics, University of Science and Technology of China, Hefei; 230026, China
3.School of Physics and Astronomy, Institute of Natural Sciences, Shanghai Jiao Tong University, Shanghai; 200240, China
4.Institute for Quantum Science and Engineering, Department of Physics, Southern University of Science and Technology, Shenzhen; 518055, China

Xu, Xiao-Yun,Huang, Xuan-Lun,Li, Zhan-Ming,et al. A scalable photonic computer solving the subset sum problem[J]. Science Advances,2020,6(5).

Xu, Xiao-Yun.,Huang, Xuan-Lun.,Li, Zhan-Ming.,Gao, Jun.,Jiao, Zhi-Qiang.,...&Jin, Xian-Min.(2020).A scalable photonic computer solving the subset sum problem.Science Advances,6(5).

Xu, Xiao-Yun,et al."A scalable photonic computer solving the subset sum problem".Science Advances 6.5(2020).