An optical fiber network oracle for NP-complete problems

Kan Wu; Javier García de Abajo; Cesare Soci; Perry Ping Shum; Nikolay I Zheludev

doi:10.1038/lsa.2014.28

Go to Nature Website

Your Location：

Home >

Browse articles >

An optical fiber network oracle for NP-complete problems

Original Articles

- An optical fiber network oracle for NP-complete problems
- Light: Science & Applications Vol. 3, Issue 1, (2014)
- Affiliations：
  
  1.Centre for Disruptive Photonic Technologies, Nanyang Technological University, Singapore 637371, Singapore
  2.Optoelectronics Research Centre, University of Southampton, Southampton SO17 1BJ, UK
  3.IQFR-CSIC, 28006 Madrid, Spain
- Author bio：
  
  Dr C Soci, Centre for Disruptive Photonic Technologies, Nanyang Technological University, 21 Nanyang Link, Singapore 637371, Singapore E-mail: csoci@ntu.edu.sg
- Funds：
- DOI：10.1038/lsa.2014.28
  CLC：
- Published：2014-03，
  
  Published Online：28 February 2014，
  
  Received：18 June 2013，
  
  Revised：01 October 2013，
  
  Accepted：18 October 2013
- Accepted：
Scan QR Code
Wu, K. et al. An optical fiber network oracle for NP-complete problems. Light: Science & Applications, 3, e147 (2014).
DOI：

Wu, K. et al. An optical fiber network oracle for NP-complete problems. Light: Science & Applications, 3, e147 (2014). DOI： 10.1038/lsa.2014.28.

摘要

Abstract

The modern information society is enabled by photonic fiber networks characterized by huge coverage and great complexity and ranging in size from transcontinental submarine telecommunication cables to fiber to the home and local segments. This world-wide network has yet to match the complexity of the human brain

which contains a hundred billion neurons

each with thousands of synaptic connections on average. However

it already exceeds the complexity of brains from primitive organisms

i.e.

the honey bee

which has a brain containing approximately one million neurons. In this study

we present a discussion of the computing potential of optical networks as information carriers. Using a simple fiber network

we provide a proof-of-principle demonstration that this network can be treated as an optical oracle for the Hamiltonian path problem

the famous mathematical complexity problem of finding whether a set of towns can be travelled

via

a path in which each town is visited only once. Pronouncement of a Hamiltonian path is achieved by monitoring the delay of an optical pulse that interrogates the network

and this delay will be equal to the sum of the travel times needed to visit all of the nodes (towns). We argue that the optical oracle could solve this NP-complete problem hundreds of times faster than brute-force computing. Additionally

we discuss secure communication applications for the optical oracle and propose possible implementation in silicon photonics and plasmonic networks.

关键词

Keywords

Hamiltonian path problemNP completeoptical oracle

references

Karp RM. Reducibility among combinatorial problems. In:50 Years of Integer Programming 1958–2008. Chapter 8. Berlin/Heidelberg: Springer; 2010; 219–241.

Cook SA. The complexity of theorem-proving procedures. In:Proceedings of the Third Annual ACM Symposium on Theory of Computing. Shaker Heights, OH: ACM; 1971; 151–158.

Dorigo M, Gambardella LM. Ant colony system: a cooperative learning approach to the traveling salesman problem.IEEE Trans Evol Comput1997;1: 53–66..

Ouyang Q, Kaplan PD, Liu S, Libchaber A. DNA solution of the maximal clique problem.Science1997;278: 446–449..

Aaronson S. NP-complete problems and physical reality.SIGACT News2005;36: 30–52..

Kieu T. Quantum algorithm for Hilbert's tenth problem.Int J Theor Phys2003;42: 1461–1478..

O'Brien JL. Optical quantum computing.Science2007;318: 1567–1570..

Adleman LM. Molecular computation of solutions to combinatorial problems.Science1994;266: 1021–1024..

Ezziane Z. DNA computing: applications and challenges.Nanotechnology2006;17: R27..

Liu Q, Wang L, Frutos AG, Condon AE, Corn RMet al. DNA computing on surfaces.Nature2000;403: 175–179..

Caulfield HJ, Dolev S. Why future supercomputing requires optics.Nat Photon2010;4: 261–263..

Oltean M. Solving the Hamiltonian path problem with a light-based computer.Nat Comput2008;7: 57–70..

Shaked NT, Messika S, Dolev S, Rosen J. Optical solution for bounded NP-complete problems.Appl Opt2007;46: 711–724..

Woods D, Naughton TJ. Optical computing: photonic neural networks.Nat Phys2012;8: 257–259..

Haist T, Osten W. An optical solution for the traveling salesman problem.Opt Express2007;15: 10473–10482..

Sartakhti JS, Jalili S, Rudi AG. A new light-based solution to the Hamiltonian path problem.Future Gen Comput Syst2013;29: 520–527..

Dolev S, Fitoussi H. Masking traveling beams: optical solutions for NP-complete problems, trading space for time.Theor Comput Sci2010;411: 837–853..

Goliaei S, Jalili S, Salimi J. Light-based solution for the dominating set problem.Appl Opt2012;51: 6979–6983..

Oltean M. A light-based device for solving the Hamiltonian path problem. In:Unconventional Computation. Chapter 18. Berlin/Heidelberg: Springer; 2006; 217–227.

Held M, Karp R. A dynamic programming approach to sequencing problems.J Soc Ind Appl Math1962;10: 196–210..

Bjorklund A. Determinant sums for undirected Hamiltonicity. Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science; 23–25 October 2010; Las Vegas, NV, USA. IEEE Computer Society: Washington, DC, USA, pp 173–182.

Sámson ZL, Horak P, MacDonald KF, Zheludev NI. Femtosecond surface plasmon pulse propagation.Opt Lett2011;36: 250–252..

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰