'Optical oracle' could quickly solve complex computing problems

‘Optical oracle’ could quickly solve complex computing problems
(a) The optical oracle’s approach to solve the Hamiltonian path problem on a network with five nodes. An optical pulse is injected into the optical network and travels along all possible paths. A Hamiltonian path exists if a pulse returning to node 1 is observed after a delay equal to the total delay of the entire network. (b) Actual design of the optical oracle with optical fiber components. Credit: Wu, et al. ©2014 Nature

(Phys.org) —The optical fiber network that spans the globe consists of millions of miles of fibers that bring us our Internet, cable TV, and telephone services. Now researchers have shown that this global network offers an untapped computing potential due to its ability to act as an "optical oracle" that can solve the Hamiltonian path problem—determining whether a route exists between multiple towns so that each town is visited only once—hundreds of times faster than conventional computers. Although using the existing optical fiber network for computing would be unrealistic, the study shows that optical fibers could offer a powerful new computing platform in the future.

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

More information: Kan Wu, et al. "An optical fiber network oracle for NP-complete problems." Light: Science & Application. DOI: 10.1038/lsa.2014.28

© 2014 Phys.org. All rights reserved.

Citation: 'Optical oracle' could quickly solve complex computing problems (2014, March 31) retrieved 19 March 2024 from https://phys.org/news/2014-03-optical-oracle-quickly-complex-problems.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Explore further

On the path to 1 terabit-per-second networks

109 shares

Feedback to editors