'Optical oracle' could quickly solve complex computing problems

March 31, 2014 by Lisa Zyga, Phys.org 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: On the path to 1 terabit-per-second networks

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

Related Stories

On the path to 1 terabit-per-second networks

March 1, 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

February 3, 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

CMS gets first result using largest-ever LHC data sample

February 15, 2019

Just under three months after the final proton–proton collisions from the Large Hadron Collider (LHC)'s second run (Run 2), the CMS collaboration has submitted its first paper based on the full LHC dataset collected in ...

Gravitational waves will settle cosmic conundrum

February 14, 2019

Measurements of gravitational waves from approximately 50 binary neutron stars over the next decade will definitively resolve an intense debate about how quickly our universe is expanding, according to findings from an international ...


Adjust slider to filter visible comments by rank

Display comments: newest first

Mar 31, 2014
This comment has been removed by a moderator.
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

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.