Fiber non-Turing all-optical computer for solving complex decision problems

This paper demonstrates an optical network approach to non-Turing optical computer to solve NP-complete problems. A proof-of-principle demonstration of solving directed Hamiltonian path problem was performed on a map with five towns built based on optical fiber network. The decision of the existence of Hamiltonian path can be made by monitoring the delayed output pulses from the fiber network where a positive answer means a pulse appearing at the delay equal to the total delay of the whole graph. The decision was successfully made in 82 ns. Considering the maximum obtainable pulse energy of ~10 μJ in fiber and minimum 10 photons for a reliable detection, we argue that current fiber technology shall allow interrogating graphs with up to a few hundred nodes. Moreover, it is known that all the NP-complete problems can be transferred to each other with a polynomial complete reduction, meaning that this optical computer can be applied to solve all kinds of NP-complete problems.