Abstract
There is a class of diverse mathematical complexity problems such as the travelling salesman problem of looking for a shortest possible route on a map, often referred as Nondeterministic Polynomial (NP) complete problems. There is still yet no efficient algorithm to solve these problems within polynomial time by a deterministic Turing machine. Besides the conventional approach with electronic computers, Non-Turing approaches such as DNA, quantum and optical computing may work. Here we show that these NP-complete problems may be solved by using a new type of all-optical computer. A proof-of-principle demonstration was performed on a fiber network representing a map of five towns on the NP-complete directed Hamiltonian path problem of deciding if a map can be travelled in a unidirectional way that each town is visited exactly once. The decision was successfully obtained only in a few tens of nanoseconds. We argue that current fiber technology shall allow interrogating graphs of hundreds of nodes and providing a simple-to-implement alternative to a quantum computer approach.
© 2013 IEEE
PDF ArticleMore Like This
Eli Yablonovitch, T. Patrick Xiao, and Sri Krishna Vadlamani
JTu4A.114 Frontiers in Optics (FiO) 2019
Yalin Hou, Xin Zhao, Qian Li, Jie Chen, Yihong Li, and Zheng Zheng
SF1M.2 CLEO: Science and Innovations (CLEO:S&I) 2019
Zhe Wang, Alireza Marandi, Kai Wen, Robert L. Byer, and Yoshihisa Yamamoto
FM2A.2 CLEO: QELS_Fundamental Science (CLEO:FS) 2014