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...
Autores principales: | , , , , , , , , |
---|---|
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 |