March 31, 2014 feature
'Optical oracle' could quickly solve complex computing problems
The researchers, Kan Wu, et al., at Nanyang Technological University in Singapore, the University of Southampton in the UK, and IQFR-CSIC in Madrid, Spain, have published a paper on their proof-of-principle demonstration of an optical fiber network solving the Hamiltonian path problem. The paper is published in a recent issue of Light: Science & Application.
"The optical oracle shows that using photonic networks as information carrier opens up unconventional ways to optical computing, in which traditional advantages of photonics like processing speed, bandwidth and parallelism, may be exploited in combination with highly reconfigurable materials and nanoscale systems to realize efficient and highly integrated solutions to difficult computational tasks," coauthor Cesare Soci, Assistant Professor at Nanyang Technological University, told Phys.org.
As the researchers explain, the Hamiltonian path problem is part of a class of famous complexity problems known as NP-complete problems. Although conventional computer algorithms can solve NP-complete problems like this one when they involve small numbers, the time it takes to solve them increases exponentially with the size of the problem.
Despite many years of research, there is still no efficient way to solve NP-complete problems, and many researchers suspect that an efficient algorithm does not even exist. Researchers have also been investigating alternative approaches to conventional algorithms, such as the use of soap bubbles, protein folding, quantum computing, and DNA computing. So far, none of these approaches has made solving these problems any easier.
In the new study, the researchers experimentally show that an optical fiber network can be used to solve the Hamiltonian path problem for five cities (or nodes). Although the problem is fairly easily solved with only five nodes, the researchers predict that the problem with 30 nodes could be solved approximately 375 times faster using the optical oracle than with a conventional computer.
The optical oracle relies on timing how long it takes a light pulse to travel through the network. As the researchers explain, a light path experiences a unique delay upon visiting each node. The delays are assigned to the nodes so that their sum can only be obtained by summing each node's delay exactly once. When the experiment is run, if a light pulse traveling through the network is detected after this sum of delay times, it means a Hamiltonian path does indeed exist in the network; otherwise, a Hamiltonian path does not exist.
Similar to other physics approaches, such as soap bubbles and DNA computing, the optical oracle's ability to solve large NP-complete problems is limited by the requirement for scaling of the physical resources. For the optical oracle, solving the Hamiltonian path problem for a 30-node network would require a minimum fiber length of 100 km and a maximum of 200 km. These lengths are within the reach of current fiber technology, although they may require optical signal amplification.
The researchers also noted that the optical oracle cannot solve the Hamiltonian path problem as quickly as probabilistic Monte Carlo algorithms. However, the solutions obtained by these algorithms involve a degree of uncertainty, while the optical oracle completely excludes false predictions.
With the ability to solve NP-compete problems much faster than conventional computers, optical telecommunications networks may have a significant impact in applications such as secure communications, routing optimization, and optical data processing. More realistically, the strategy could be implemented on a silicon photonics platform with femtosecond lasers to allow for a more compact architecture. The researchers are also investigating how optical networks can be used to mimic the complexities of the human brain.
"At the Centre for Disruptive Photonic Technologies, we are exploring several possibilities to use optical networks to perform non-Boolean data processing and mimic brain functionalities and signal protocols—we call this area 'cognitive photonics,'" Soci said. "We are currently looking at nonlinear fiber networks and we are planning to extend this work to integrated photonic networks, which will eventually allow tackling problems of much greater size and complexity.
© 2014 Phys.org. All rights reserved.