Cargando…

A scalable photonic computer solving the subset sum problem

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...

Descripción completa

Detalles Bibliográficos
Autores principales: Xu, Xiao-Yun, Huang, Xuan-Lun, Li, Zhan-Ming, Gao, Jun, Jiao, Zhi-Qiang, Wang, Yao, Ren, Ruo-Jing, Zhang, H. P., Jin, Xian-Min
Formato: Online Artículo Texto
Lenguaje:English
Publicado: American Association for the Advancement of Science 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6994215/
https://www.ncbi.nlm.nih.gov/pubmed/32064352
http://dx.doi.org/10.1126/sciadv.aay5853
_version_ 1783493164836847616
author Xu, Xiao-Yun
Huang, Xuan-Lun
Li, Zhan-Ming
Gao, Jun
Jiao, Zhi-Qiang
Wang, Yao
Ren, Ruo-Jing
Zhang, H. P.
Jin, Xian-Min
author_facet Xu, Xiao-Yun
Huang, Xuan-Lun
Li, Zhan-Ming
Gao, Jun
Jiao, Zhi-Qiang
Wang, Yao
Ren, Ruo-Jing
Zhang, H. P.
Jin, Xian-Min
author_sort Xu, Xiao-Yun
collection PubMed
description 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.”
format Online
Article
Text
id pubmed-6994215
institution National Center for Biotechnology Information
language English
publishDate 2020
publisher American Association for the Advancement of Science
record_format MEDLINE/PubMed
spelling pubmed-69942152020-02-14 A scalable photonic computer solving the subset sum problem Xu, Xiao-Yun Huang, Xuan-Lun Li, Zhan-Ming Gao, Jun Jiao, Zhi-Qiang Wang, Yao Ren, Ruo-Jing Zhang, H. P. Jin, Xian-Min Sci Adv Research Articles 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.” American Association for the Advancement of Science 2020-01-31 /pmc/articles/PMC6994215/ /pubmed/32064352 http://dx.doi.org/10.1126/sciadv.aay5853 Text en Copyright © 2020 The Authors, some rights reserved; exclusive licensee American Association for the Advancement of Science. No claim to original U.S. Government Works. Distributed under a Creative Commons Attribution NonCommercial License 4.0 (CC BY-NC). http://creativecommons.org/licenses/by-nc/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution-NonCommercial license (http://creativecommons.org/licenses/by-nc/4.0/) , which permits use, distribution, and reproduction in any medium, so long as the resultant use is not for commercial advantage and provided the original work is properly cited.
spellingShingle Research Articles
Xu, Xiao-Yun
Huang, Xuan-Lun
Li, Zhan-Ming
Gao, Jun
Jiao, Zhi-Qiang
Wang, Yao
Ren, Ruo-Jing
Zhang, H. P.
Jin, Xian-Min
A scalable photonic computer solving the subset sum problem
title A scalable photonic computer solving the subset sum problem
title_full A scalable photonic computer solving the subset sum problem
title_fullStr A scalable photonic computer solving the subset sum problem
title_full_unstemmed A scalable photonic computer solving the subset sum problem
title_short A scalable photonic computer solving the subset sum problem
title_sort scalable photonic computer solving the subset sum problem
topic Research Articles
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6994215/
https://www.ncbi.nlm.nih.gov/pubmed/32064352
http://dx.doi.org/10.1126/sciadv.aay5853
work_keys_str_mv AT xuxiaoyun ascalablephotoniccomputersolvingthesubsetsumproblem
AT huangxuanlun ascalablephotoniccomputersolvingthesubsetsumproblem
AT lizhanming ascalablephotoniccomputersolvingthesubsetsumproblem
AT gaojun ascalablephotoniccomputersolvingthesubsetsumproblem
AT jiaozhiqiang ascalablephotoniccomputersolvingthesubsetsumproblem
AT wangyao ascalablephotoniccomputersolvingthesubsetsumproblem
AT renruojing ascalablephotoniccomputersolvingthesubsetsumproblem
AT zhanghp ascalablephotoniccomputersolvingthesubsetsumproblem
AT jinxianmin ascalablephotoniccomputersolvingthesubsetsumproblem
AT xuxiaoyun scalablephotoniccomputersolvingthesubsetsumproblem
AT huangxuanlun scalablephotoniccomputersolvingthesubsetsumproblem
AT lizhanming scalablephotoniccomputersolvingthesubsetsumproblem
AT gaojun scalablephotoniccomputersolvingthesubsetsumproblem
AT jiaozhiqiang scalablephotoniccomputersolvingthesubsetsumproblem
AT wangyao scalablephotoniccomputersolvingthesubsetsumproblem
AT renruojing scalablephotoniccomputersolvingthesubsetsumproblem
AT zhanghp scalablephotoniccomputersolvingthesubsetsumproblem
AT jinxianmin scalablephotoniccomputersolvingthesubsetsumproblem