'Optical oracle' could quickly solve complex computing problems

Mar 31, 2014 by Lisa Zyga feature
(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.

Explore further: Low-cost multi-fiber optical connector developed

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

4.5 /5 (27 votes)
add to favorites email to friend print save as pdf

Related Stories

On the path to 1 terabit-per-second networks

Mar 01, 2012

As IP traffic continues to increase and the router interface rate extends beyond 100 gigabits-per-second (Gb/s), future optical networks—ones that would achieve unprecedented speeds of 1 terabit-per-second (Tb/s)—will ...

Low-cost multi-fiber optical connector developed

Feb 03, 2014

Fujitsu Laboratories and Furukawa Electric today announced that they have collaborated to develop a new multi-fiber optical connector that enjoins and aligns multiple optical fibers for optical interconnects.

Recommended for you

Spin-based electronics: New material successfully tested

3 hours ago

Spintronics is an emerging field of electronics, where devices work by manipulating the spin of electrons rather than the current generated by their motion. This field can offer significant advantages to computer technology. ...

Verifying the future of quantum computing

4 hours ago

Physicists are one step closer to proving the reliability of a quantum computer – a machine which promises to revolutionise the way we trade over the internet and provide new tools to perform powerful simulations.

A transistor-like amplifier for single photons

Jul 29, 2014

Data transmission over long distances usually utilizes optical techniques via glass fibres – this ensures high speed transmission combined with low power dissipation of the signal. For quite some years ...

User comments : 2

Adjust slider to filter visible comments by rank

Display comments: newest first

Dr_toad
1 / 5 (1) Mar 31, 2014
This is pretty cool. Analog computers are much faster in solving this sort of problem than are digital approximations.

This is similar to Martin Gardner's spaghetti sort, if anyone remembers that...
freeiam
not rated yet Apr 01, 2014
Very clever. I didn't understand it at first because essential information is missing from the article, but this will help: http://www.nature...28a.html