Abstract

Cognitive photonic networks are researched to efficiently solve computationally hard problems. Flexible fabrication techniques for the implementation of such networks into compact and scalable chips are desirable for the study of new optical computing schemes and algorithm optimization. Here we demonstrate a femtosecond laser-written optical oracle based on cascaded directional couplers in glass, for the solution of the Hamiltonian path problem. By interrogating the integrated photonic chip with ultrashort laser pulses, we were able to distinguish the different paths traveled by light pulses, and thus infer the existence or the absence of the Hamiltonian path in the network by using an optical correlator. This work proves that graph theory problems may be easily implemented in integrated photonic networks, down scaling the net size and speeding up execution times.

© 2018 Optical Society of America under the terms of the OSA Open Access Publishing Agreement

Full Article  |  PDF Article
OSA Recommended Articles
Optical solution for bounded NP-complete problems

Natan T. Shaked, Stephane Messika, Shlomi Dolev, and Joseph Rosen
Appl. Opt. 46(5) 711-724 (2007)

Optical solver of combinatorial problems: nanotechnological approach

Eyal Cohen, Shlomi Dolev, Sergey Frenkel, Boris Kryzhanovsky, Alexandr Palagushkin, Michael Rosenblit, and Victor Zakharov
J. Opt. Soc. Am. A 30(9) 1845-1853 (2013)

An Optical Solution For The Traveling Salesman Problem

Tobias Haist and Wolfgang Osten
Opt. Express 15(16) 10473-10482 (2007)

References

  • View by:
  • |
  • |
  • |

  1. P. E. Dunne, “An annotated list of selected NP-complete problems,” http://cgi.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html .
  2. F. Harary and I. C. Ross, “A procedure for clique detection using the group matrix,” Sociometry 20, 205–215 (1957).
  3. S. Dolev and H. Fitoussi, “Masking traveling beams: Optical solutions for NP-complete problems, trading space for time,” Theor. Comput. Sci. 411, 837–853 (2010).
  4. L. Fortnow, The golden ticket: P, NP, and the search for the impossible (Princeton University Press, 2013).
  5. S. Aaronson, “NP-Complete Problems and Physical Reality,” ACM Sigact News 36, 30–52 (2005).
  6. D. T. Chiu, E. Pezzoli, H. Wu, A. D. Stroock, and G. M. Whitesides, “Using three-dimensional microfluidic networks for solving computationally hard problems,” Proc. Natl. Acad. Sci. U.S.A. 98(6), 2961–2966 (2001).
    [PubMed]
  7. R. H. Lathrop, “The protein threading problem with sequence amino acid interaction preferences is NP-complete,” Protein Eng. 7(9), 1059–1068 (1994).
    [PubMed]
  8. C. Guyeux, N. M. Côté, J. M. Bahi, and W. Bienia, “Is protein folding problem really a NP-complete one? First investigations,” J. Bioinform. Comput. Biol. 12(1), 1350017 (2014).
    [PubMed]
  9. K. A. Dill, S. B. Ozkan, M. S. Shell, and T. R. Weikl, “The protein folding problem,” Annu. Rev. Biophys. 37, 289–316 (2008).
    [PubMed]
  10. A. S. Fraenkel, “Complexity of protein folding,” Bull. Math. Biol. 55(6), 1199–1210 (1993).
    [PubMed]
  11. A. M. Childs, D. Gosset, and Z. Webb, “Universal computation by multiparticle quantum walk,” Science 339(6121), 791–794 (2013).
    [PubMed]
  12. J. L. O’Brien, “Optical quantum computing,” Science 318(5856), 1567–1570 (2007).
    [PubMed]
  13. J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
    [PubMed]
  14. N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).
  15. G. D. Marshall, A. Politi, J. C. Matthews, P. Dekker, M. Ams, M. J. Withford, and J. L. O’Brien, “Laser written waveguide photonic quantum circuits,” Opt. Express 17(15), 12546–12554 (2009).
    [PubMed]
  16. Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith, “DNA computing on surfaces,” Nature 403(6766), 175–179 (2000).
    [PubMed]
  17. Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber, “DNA solution of the maximal clique problem,” Science 278(5337), 446–449 (1997).
    [PubMed]
  18. K. W. Huang, J. L. Chen, C. S. Yang, and C. W. Tsai, “A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem,” Neural Comput. Appl. 26, 495–506 (2015).
  19. H. Wu, “An improved surface-based method for DNA computation,” Biosystems 59(1), 1–5 (2001).
    [PubMed]
  20. T. Haist and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15(16), 10473–10482 (2007).
    [PubMed]
  21. M. Oltean and O. Muntean, “Evolutionary design of graph-based structures for optical computing,” in International Workshop on Optical Supercomputing, (Springer Berlin Heidelberg, 2009), pp. 56–69.
  22. K. Wu, J. García de Abajo, C. Soci, P. P. Shum, and N. I. Zheludev, “An optical fiber network oracle for NP-complete problems,” Light Sci. Appl. 3, e147 (2014).
  23. M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Nat. Comput. 7, 57–70 (2008).
  24. W. Hu, K. Wu, P. P. Shum, N. I. Zheludev, and C. Soci, “All-Optical Implementation of the Ant Colony Optimization Algorithm,” Sci. Rep. 6, 26283 (2016).
    [PubMed]
  25. K. Wu, C. Soci, P. P. Shum, and N. I. Zheludev, “Computing matrix inversion with optical networks,” Opt. Express 22(1), 295–304 (2014).
    [PubMed]
  26. B. Gholipour, P. Bastock, C. Craig, K. Khan, D. Hewak, and C. Soci, “Amorphous Metal‐Sulphide Microfibers Enable Photonic Synapses for Brain‐Like Computing,” Adv. Opt. Mater. 3, 635–641 (2015).
  27. N. M. Estakhri, B. E. Edwards, and N. Engheta, “Solving Integral Equations with optical Metamaterial-Waveguide Networks” in Conference on Lasers and Electro-Optics, OSA Technical Digest (Optical Society of America, 2017), paper FTh1G.2.
  28. Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).
  29. R. W. Boyd, J. E. Heebner, N. N. Lepeshkin, Q. H. Park, A. Schweinsberg, G. W. Wicks, and R. M. Boysel, “Nanofabrication of optical structures and devices for photonics and biophotonics,” J. Mod. Opt. 50, 2543–2550 (2003).
  30. K. Yamada, T. Tsuchizawa, R. Kou, H. Nishi, H. Shinojima, Y. Ishikawa, K. Wada, and S. Mutoh, “Silicon photonic platform for telecommunications applications,” in Photonics Conference (IEEE, 2011), pp. 591–592.
  31. Y. Yang, Y. Ma, H. Guan, Y. Liu, S. Danziger, S. Ocheltree, K. Bergman, T. Baehr-Jones, and M. Hochberg, “Phase coherence length in silicon photonic platform,” Opt. Express 23(13), 16890–16902 (2015).
    [PubMed]
  32. P. Frisco, C. Henkel, and S. Tengely, “An algorithm for SAT without an extraction phase,” in International Workshop on DNA-Based Computers (Springer, 2005), pp. 67–80.
  33. N. Spagnolo, L. Aparo, C. Vitelli, A. Crespi, R. Ramponi, R. Osellame, P. Mataloni, and F. Sciarrino, “Quantum interferometry with three-dimensional geometry,” Sci. Rep. 2, 862 (2012).
    [PubMed]
  34. Corning, “Corning EAGLE2000 AMLCD glass substrates material information,” http://www.corning.com/displaytechnologies .
  35. T. Meany, S. Gross, N. Jovanic, A. Arriola, M. J. Steel, and M. J. Withford, “Towards low-loss lightwave circuits for non-classical optics at 800 and 1,550 nm,” Appl. Phys., A Mater. Sci. Process. 114(1), 113–118 (2014).
  36. L. Sansoni, F. Sciarrino, G. Vallone, P. Mataloni, A. Crespi, R. Ramponi, and R. Osellame, “Polarization entangled state measurement on a chip,” Phys. Rev. Lett. 105(20), 200503 (2010).
    [PubMed]
  37. R. Trebino, Frequency-Resolved Optical Gating: The measurement of Ultrashort Laser Pulses, (Springer Science & Business Media, 2012).
  38. S. M. Eaton, H. Zhang, M. L. Ng, J. Li, W. J. Chen, S. Ho, and P. R. Herman, “Transition from thermal diffusion to heat accumulation in high repetition rate femtosecond laser writing of buried optical waveguides,” Opt. Express 16(13), 9443–9458 (2008).
    [PubMed]
  39. S. Eaton, H. Zhang, P. Herman, F. Yoshino, L. Shah, J. Bovatsek, and A. Arai, “Heat accumulation effects in femtosecond laser-written waveguides with variable repetition rate,” Opt. Express 13(12), 4708–4716 (2005).
    [PubMed]
  40. W. P. Huang and C. L. Xu, “Simulation of three-dimensional optical waveguides by a full-vector beam propagation method,” IEEE J. Quantum Electron. 29, 2639–2649 (1993).
  41. T. T. Fernandez, M. Hernandez, B. Sotillo, S. M. Eaton, G. Jose, R. Osellame, A. Jha, P. Fernandez, and J. Solis, “Role of ion migrations in ultrafast laser written tellurite glass waveguides,” Opt. Express 22(12), 15298–15304 (2014).
    [PubMed]
  42. A. Yariv, “Coupled-mode theory for guided-wave optics,” IEEE J. Quantum Electron. 9, 919–933 (1973).
  43. W. J. Chen, S. M. Eaton, H. Zhang, and P. R. Herman, “Broadband directional couplers fabricated in bulk glass with high repetition rate femtosecond laser pulses,” Opt. Express 16(15), 11470–11480 (2008).
    [PubMed]
  44. S. M. Eaton, W. Chen, L. Zhang, H. Zhang, R. Iyer, J. S. Aitchison, and P. R. Herman, “Telecom-band directional coupler written with femtosecond fiber laser,” IEEE Photonics Technol. Lett. 18, 2174–2176 (2006).

2017 (1)

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

2016 (1)

W. Hu, K. Wu, P. P. Shum, N. I. Zheludev, and C. Soci, “All-Optical Implementation of the Ant Colony Optimization Algorithm,” Sci. Rep. 6, 26283 (2016).
[PubMed]

2015 (3)

B. Gholipour, P. Bastock, C. Craig, K. Khan, D. Hewak, and C. Soci, “Amorphous Metal‐Sulphide Microfibers Enable Photonic Synapses for Brain‐Like Computing,” Adv. Opt. Mater. 3, 635–641 (2015).

K. W. Huang, J. L. Chen, C. S. Yang, and C. W. Tsai, “A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem,” Neural Comput. Appl. 26, 495–506 (2015).

Y. Yang, Y. Ma, H. Guan, Y. Liu, S. Danziger, S. Ocheltree, K. Bergman, T. Baehr-Jones, and M. Hochberg, “Phase coherence length in silicon photonic platform,” Opt. Express 23(13), 16890–16902 (2015).
[PubMed]

2014 (6)

K. Wu, J. García de Abajo, C. Soci, P. P. Shum, and N. I. Zheludev, “An optical fiber network oracle for NP-complete problems,” Light Sci. Appl. 3, e147 (2014).

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

C. Guyeux, N. M. Côté, J. M. Bahi, and W. Bienia, “Is protein folding problem really a NP-complete one? First investigations,” J. Bioinform. Comput. Biol. 12(1), 1350017 (2014).
[PubMed]

T. Meany, S. Gross, N. Jovanic, A. Arriola, M. J. Steel, and M. J. Withford, “Towards low-loss lightwave circuits for non-classical optics at 800 and 1,550 nm,” Appl. Phys., A Mater. Sci. Process. 114(1), 113–118 (2014).

K. Wu, C. Soci, P. P. Shum, and N. I. Zheludev, “Computing matrix inversion with optical networks,” Opt. Express 22(1), 295–304 (2014).
[PubMed]

T. T. Fernandez, M. Hernandez, B. Sotillo, S. M. Eaton, G. Jose, R. Osellame, A. Jha, P. Fernandez, and J. Solis, “Role of ion migrations in ultrafast laser written tellurite glass waveguides,” Opt. Express 22(12), 15298–15304 (2014).
[PubMed]

2013 (2)

A. M. Childs, D. Gosset, and Z. Webb, “Universal computation by multiparticle quantum walk,” Science 339(6121), 791–794 (2013).
[PubMed]

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

2012 (1)

N. Spagnolo, L. Aparo, C. Vitelli, A. Crespi, R. Ramponi, R. Osellame, P. Mataloni, and F. Sciarrino, “Quantum interferometry with three-dimensional geometry,” Sci. Rep. 2, 862 (2012).
[PubMed]

2010 (2)

L. Sansoni, F. Sciarrino, G. Vallone, P. Mataloni, A. Crespi, R. Ramponi, and R. Osellame, “Polarization entangled state measurement on a chip,” Phys. Rev. Lett. 105(20), 200503 (2010).
[PubMed]

S. Dolev and H. Fitoussi, “Masking traveling beams: Optical solutions for NP-complete problems, trading space for time,” Theor. Comput. Sci. 411, 837–853 (2010).

2009 (1)

2008 (4)

2007 (2)

2006 (1)

S. M. Eaton, W. Chen, L. Zhang, H. Zhang, R. Iyer, J. S. Aitchison, and P. R. Herman, “Telecom-band directional coupler written with femtosecond fiber laser,” IEEE Photonics Technol. Lett. 18, 2174–2176 (2006).

2005 (2)

2003 (1)

R. W. Boyd, J. E. Heebner, N. N. Lepeshkin, Q. H. Park, A. Schweinsberg, G. W. Wicks, and R. M. Boysel, “Nanofabrication of optical structures and devices for photonics and biophotonics,” J. Mod. Opt. 50, 2543–2550 (2003).

2001 (2)

D. T. Chiu, E. Pezzoli, H. Wu, A. D. Stroock, and G. M. Whitesides, “Using three-dimensional microfluidic networks for solving computationally hard problems,” Proc. Natl. Acad. Sci. U.S.A. 98(6), 2961–2966 (2001).
[PubMed]

H. Wu, “An improved surface-based method for DNA computation,” Biosystems 59(1), 1–5 (2001).
[PubMed]

2000 (1)

Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith, “DNA computing on surfaces,” Nature 403(6766), 175–179 (2000).
[PubMed]

1997 (1)

Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber, “DNA solution of the maximal clique problem,” Science 278(5337), 446–449 (1997).
[PubMed]

1994 (1)

R. H. Lathrop, “The protein threading problem with sequence amino acid interaction preferences is NP-complete,” Protein Eng. 7(9), 1059–1068 (1994).
[PubMed]

1993 (2)

A. S. Fraenkel, “Complexity of protein folding,” Bull. Math. Biol. 55(6), 1199–1210 (1993).
[PubMed]

W. P. Huang and C. L. Xu, “Simulation of three-dimensional optical waveguides by a full-vector beam propagation method,” IEEE J. Quantum Electron. 29, 2639–2649 (1993).

1973 (1)

A. Yariv, “Coupled-mode theory for guided-wave optics,” IEEE J. Quantum Electron. 9, 919–933 (1973).

1957 (1)

F. Harary and I. C. Ross, “A procedure for clique detection using the group matrix,” Sociometry 20, 205–215 (1957).

Aaronson, S.

S. Aaronson, “NP-Complete Problems and Physical Reality,” ACM Sigact News 36, 30–52 (2005).

Aitchison, J. S.

S. M. Eaton, W. Chen, L. Zhang, H. Zhang, R. Iyer, J. S. Aitchison, and P. R. Herman, “Telecom-band directional coupler written with femtosecond fiber laser,” IEEE Photonics Technol. Lett. 18, 2174–2176 (2006).

Ams, M.

Aparo, L.

N. Spagnolo, L. Aparo, C. Vitelli, A. Crespi, R. Ramponi, R. Osellame, P. Mataloni, and F. Sciarrino, “Quantum interferometry with three-dimensional geometry,” Sci. Rep. 2, 862 (2012).
[PubMed]

Arai, A.

Arriola, A.

T. Meany, S. Gross, N. Jovanic, A. Arriola, M. J. Steel, and M. J. Withford, “Towards low-loss lightwave circuits for non-classical optics at 800 and 1,550 nm,” Appl. Phys., A Mater. Sci. Process. 114(1), 113–118 (2014).

Baehr-Jones, T.

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

Y. Yang, Y. Ma, H. Guan, Y. Liu, S. Danziger, S. Ocheltree, K. Bergman, T. Baehr-Jones, and M. Hochberg, “Phase coherence length in silicon photonic platform,” Opt. Express 23(13), 16890–16902 (2015).
[PubMed]

Bahi, J. M.

C. Guyeux, N. M. Côté, J. M. Bahi, and W. Bienia, “Is protein folding problem really a NP-complete one? First investigations,” J. Bioinform. Comput. Biol. 12(1), 1350017 (2014).
[PubMed]

Barbieri, M.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Bastock, P.

B. Gholipour, P. Bastock, C. Craig, K. Khan, D. Hewak, and C. Soci, “Amorphous Metal‐Sulphide Microfibers Enable Photonic Synapses for Brain‐Like Computing,” Adv. Opt. Mater. 3, 635–641 (2015).

Bentivegna, M.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

Bergman, K.

Bienia, W.

C. Guyeux, N. M. Côté, J. M. Bahi, and W. Bienia, “Is protein folding problem really a NP-complete one? First investigations,” J. Bioinform. Comput. Biol. 12(1), 1350017 (2014).
[PubMed]

Bovatsek, J.

Boyd, R. W.

R. W. Boyd, J. E. Heebner, N. N. Lepeshkin, Q. H. Park, A. Schweinsberg, G. W. Wicks, and R. M. Boysel, “Nanofabrication of optical structures and devices for photonics and biophotonics,” J. Mod. Opt. 50, 2543–2550 (2003).

Boysel, R. M.

R. W. Boyd, J. E. Heebner, N. N. Lepeshkin, Q. H. Park, A. Schweinsberg, G. W. Wicks, and R. M. Boysel, “Nanofabrication of optical structures and devices for photonics and biophotonics,” J. Mod. Opt. 50, 2543–2550 (2003).

Brod, D. J.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

Chen, J. L.

K. W. Huang, J. L. Chen, C. S. Yang, and C. W. Tsai, “A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem,” Neural Comput. Appl. 26, 495–506 (2015).

Chen, W.

S. M. Eaton, W. Chen, L. Zhang, H. Zhang, R. Iyer, J. S. Aitchison, and P. R. Herman, “Telecom-band directional coupler written with femtosecond fiber laser,” IEEE Photonics Technol. Lett. 18, 2174–2176 (2006).

Chen, W. J.

Childs, A. M.

A. M. Childs, D. Gosset, and Z. Webb, “Universal computation by multiparticle quantum walk,” Science 339(6121), 791–794 (2013).
[PubMed]

Chiu, D. T.

D. T. Chiu, E. Pezzoli, H. Wu, A. D. Stroock, and G. M. Whitesides, “Using three-dimensional microfluidic networks for solving computationally hard problems,” Proc. Natl. Acad. Sci. U.S.A. 98(6), 2961–2966 (2001).
[PubMed]

Condon, A. E.

Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith, “DNA computing on surfaces,” Nature 403(6766), 175–179 (2000).
[PubMed]

Corn, R. M.

Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith, “DNA computing on surfaces,” Nature 403(6766), 175–179 (2000).
[PubMed]

Côté, N. M.

C. Guyeux, N. M. Côté, J. M. Bahi, and W. Bienia, “Is protein folding problem really a NP-complete one? First investigations,” J. Bioinform. Comput. Biol. 12(1), 1350017 (2014).
[PubMed]

Craig, C.

B. Gholipour, P. Bastock, C. Craig, K. Khan, D. Hewak, and C. Soci, “Amorphous Metal‐Sulphide Microfibers Enable Photonic Synapses for Brain‐Like Computing,” Adv. Opt. Mater. 3, 635–641 (2015).

Crespi, A.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

N. Spagnolo, L. Aparo, C. Vitelli, A. Crespi, R. Ramponi, R. Osellame, P. Mataloni, and F. Sciarrino, “Quantum interferometry with three-dimensional geometry,” Sci. Rep. 2, 862 (2012).
[PubMed]

L. Sansoni, F. Sciarrino, G. Vallone, P. Mataloni, A. Crespi, R. Ramponi, and R. Osellame, “Polarization entangled state measurement on a chip,” Phys. Rev. Lett. 105(20), 200503 (2010).
[PubMed]

Danziger, S.

Datta, A.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Dekker, P.

Dill, K. A.

K. A. Dill, S. B. Ozkan, M. S. Shell, and T. R. Weikl, “The protein folding problem,” Annu. Rev. Biophys. 37, 289–316 (2008).
[PubMed]

Dolev, S.

S. Dolev and H. Fitoussi, “Masking traveling beams: Optical solutions for NP-complete problems, trading space for time,” Theor. Comput. Sci. 411, 837–853 (2010).

Eaton, S.

Eaton, S. M.

Englund, D.

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

Fernandez, P.

Fernandez, T. T.

Fitoussi, H.

S. Dolev and H. Fitoussi, “Masking traveling beams: Optical solutions for NP-complete problems, trading space for time,” Theor. Comput. Sci. 411, 837–853 (2010).

Flamini, F.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

Fraenkel, A. S.

A. S. Fraenkel, “Complexity of protein folding,” Bull. Math. Biol. 55(6), 1199–1210 (1993).
[PubMed]

Frisco, P.

P. Frisco, C. Henkel, and S. Tengely, “An algorithm for SAT without an extraction phase,” in International Workshop on DNA-Based Computers (Springer, 2005), pp. 67–80.

Frutos, A. G.

Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith, “DNA computing on surfaces,” Nature 403(6766), 175–179 (2000).
[PubMed]

Galvao, E. F.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

García de Abajo, J.

K. Wu, J. García de Abajo, C. Soci, P. P. Shum, and N. I. Zheludev, “An optical fiber network oracle for NP-complete problems,” Light Sci. Appl. 3, e147 (2014).

Gates, J. C.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Gholipour, B.

B. Gholipour, P. Bastock, C. Craig, K. Khan, D. Hewak, and C. Soci, “Amorphous Metal‐Sulphide Microfibers Enable Photonic Synapses for Brain‐Like Computing,” Adv. Opt. Mater. 3, 635–641 (2015).

Giacomini, S.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

Gosset, D.

A. M. Childs, D. Gosset, and Z. Webb, “Universal computation by multiparticle quantum walk,” Science 339(6121), 791–794 (2013).
[PubMed]

Gross, S.

T. Meany, S. Gross, N. Jovanic, A. Arriola, M. J. Steel, and M. J. Withford, “Towards low-loss lightwave circuits for non-classical optics at 800 and 1,550 nm,” Appl. Phys., A Mater. Sci. Process. 114(1), 113–118 (2014).

Guan, H.

Guyeux, C.

C. Guyeux, N. M. Côté, J. M. Bahi, and W. Bienia, “Is protein folding problem really a NP-complete one? First investigations,” J. Bioinform. Comput. Biol. 12(1), 1350017 (2014).
[PubMed]

Haist, T.

Harary, F.

F. Harary and I. C. Ross, “A procedure for clique detection using the group matrix,” Sociometry 20, 205–215 (1957).

Harris, N. C.

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

Heebner, J. E.

R. W. Boyd, J. E. Heebner, N. N. Lepeshkin, Q. H. Park, A. Schweinsberg, G. W. Wicks, and R. M. Boysel, “Nanofabrication of optical structures and devices for photonics and biophotonics,” J. Mod. Opt. 50, 2543–2550 (2003).

Henkel, C.

P. Frisco, C. Henkel, and S. Tengely, “An algorithm for SAT without an extraction phase,” in International Workshop on DNA-Based Computers (Springer, 2005), pp. 67–80.

Herman, P.

Herman, P. R.

Hernandez, M.

Hewak, D.

B. Gholipour, P. Bastock, C. Craig, K. Khan, D. Hewak, and C. Soci, “Amorphous Metal‐Sulphide Microfibers Enable Photonic Synapses for Brain‐Like Computing,” Adv. Opt. Mater. 3, 635–641 (2015).

Ho, S.

Hochberg, M.

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

Y. Yang, Y. Ma, H. Guan, Y. Liu, S. Danziger, S. Ocheltree, K. Bergman, T. Baehr-Jones, and M. Hochberg, “Phase coherence length in silicon photonic platform,” Opt. Express 23(13), 16890–16902 (2015).
[PubMed]

Hu, W.

W. Hu, K. Wu, P. P. Shum, N. I. Zheludev, and C. Soci, “All-Optical Implementation of the Ant Colony Optimization Algorithm,” Sci. Rep. 6, 26283 (2016).
[PubMed]

Huang, K. W.

K. W. Huang, J. L. Chen, C. S. Yang, and C. W. Tsai, “A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem,” Neural Comput. Appl. 26, 495–506 (2015).

Huang, W. P.

W. P. Huang and C. L. Xu, “Simulation of three-dimensional optical waveguides by a full-vector beam propagation method,” IEEE J. Quantum Electron. 29, 2639–2649 (1993).

Humphreys, P. C.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Ishikawa, Y.

K. Yamada, T. Tsuchizawa, R. Kou, H. Nishi, H. Shinojima, Y. Ishikawa, K. Wada, and S. Mutoh, “Silicon photonic platform for telecommunications applications,” in Photonics Conference (IEEE, 2011), pp. 591–592.

Iyer, R.

S. M. Eaton, W. Chen, L. Zhang, H. Zhang, R. Iyer, J. S. Aitchison, and P. R. Herman, “Telecom-band directional coupler written with femtosecond fiber laser,” IEEE Photonics Technol. Lett. 18, 2174–2176 (2006).

Jha, A.

Jin, X. M.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Jose, G.

Jovanic, N.

T. Meany, S. Gross, N. Jovanic, A. Arriola, M. J. Steel, and M. J. Withford, “Towards low-loss lightwave circuits for non-classical optics at 800 and 1,550 nm,” Appl. Phys., A Mater. Sci. Process. 114(1), 113–118 (2014).

Kaplan, P. D.

Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber, “DNA solution of the maximal clique problem,” Science 278(5337), 446–449 (1997).
[PubMed]

Khan, K.

B. Gholipour, P. Bastock, C. Craig, K. Khan, D. Hewak, and C. Soci, “Amorphous Metal‐Sulphide Microfibers Enable Photonic Synapses for Brain‐Like Computing,” Adv. Opt. Mater. 3, 635–641 (2015).

Kolthammer, W. S.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Kou, R.

K. Yamada, T. Tsuchizawa, R. Kou, H. Nishi, H. Shinojima, Y. Ishikawa, K. Wada, and S. Mutoh, “Silicon photonic platform for telecommunications applications,” in Photonics Conference (IEEE, 2011), pp. 591–592.

Kundys, D.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Langford, N. K.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Larochelle, H.

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

Lathrop, R. H.

R. H. Lathrop, “The protein threading problem with sequence amino acid interaction preferences is NP-complete,” Protein Eng. 7(9), 1059–1068 (1994).
[PubMed]

Lepeshkin, N. N.

R. W. Boyd, J. E. Heebner, N. N. Lepeshkin, Q. H. Park, A. Schweinsberg, G. W. Wicks, and R. M. Boysel, “Nanofabrication of optical structures and devices for photonics and biophotonics,” J. Mod. Opt. 50, 2543–2550 (2003).

Li, J.

Libchaber, A.

Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber, “DNA solution of the maximal clique problem,” Science 278(5337), 446–449 (1997).
[PubMed]

Liu, Q.

Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith, “DNA computing on surfaces,” Nature 403(6766), 175–179 (2000).
[PubMed]

Liu, S.

Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber, “DNA solution of the maximal clique problem,” Science 278(5337), 446–449 (1997).
[PubMed]

Liu, Y.

Ma, Y.

Marshall, G. D.

Mataloni, P.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

N. Spagnolo, L. Aparo, C. Vitelli, A. Crespi, R. Ramponi, R. Osellame, P. Mataloni, and F. Sciarrino, “Quantum interferometry with three-dimensional geometry,” Sci. Rep. 2, 862 (2012).
[PubMed]

L. Sansoni, F. Sciarrino, G. Vallone, P. Mataloni, A. Crespi, R. Ramponi, and R. Osellame, “Polarization entangled state measurement on a chip,” Phys. Rev. Lett. 105(20), 200503 (2010).
[PubMed]

Matthews, J. C.

Meany, T.

T. Meany, S. Gross, N. Jovanic, A. Arriola, M. J. Steel, and M. J. Withford, “Towards low-loss lightwave circuits for non-classical optics at 800 and 1,550 nm,” Appl. Phys., A Mater. Sci. Process. 114(1), 113–118 (2014).

Metcalf, B. J.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Milani, G.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

Mutoh, S.

K. Yamada, T. Tsuchizawa, R. Kou, H. Nishi, H. Shinojima, Y. Ishikawa, K. Wada, and S. Mutoh, “Silicon photonic platform for telecommunications applications,” in Photonics Conference (IEEE, 2011), pp. 591–592.

Ng, M. L.

Nishi, H.

K. Yamada, T. Tsuchizawa, R. Kou, H. Nishi, H. Shinojima, Y. Ishikawa, K. Wada, and S. Mutoh, “Silicon photonic platform for telecommunications applications,” in Photonics Conference (IEEE, 2011), pp. 591–592.

O’Brien, J. L.

Ocheltree, S.

Oltean, M.

M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Nat. Comput. 7, 57–70 (2008).

Osellame, R.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

T. T. Fernandez, M. Hernandez, B. Sotillo, S. M. Eaton, G. Jose, R. Osellame, A. Jha, P. Fernandez, and J. Solis, “Role of ion migrations in ultrafast laser written tellurite glass waveguides,” Opt. Express 22(12), 15298–15304 (2014).
[PubMed]

N. Spagnolo, L. Aparo, C. Vitelli, A. Crespi, R. Ramponi, R. Osellame, P. Mataloni, and F. Sciarrino, “Quantum interferometry with three-dimensional geometry,” Sci. Rep. 2, 862 (2012).
[PubMed]

L. Sansoni, F. Sciarrino, G. Vallone, P. Mataloni, A. Crespi, R. Ramponi, and R. Osellame, “Polarization entangled state measurement on a chip,” Phys. Rev. Lett. 105(20), 200503 (2010).
[PubMed]

Osten, W.

Ouyang, Q.

Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber, “DNA solution of the maximal clique problem,” Science 278(5337), 446–449 (1997).
[PubMed]

Ozkan, S. B.

K. A. Dill, S. B. Ozkan, M. S. Shell, and T. R. Weikl, “The protein folding problem,” Annu. Rev. Biophys. 37, 289–316 (2008).
[PubMed]

Park, Q. H.

R. W. Boyd, J. E. Heebner, N. N. Lepeshkin, Q. H. Park, A. Schweinsberg, G. W. Wicks, and R. M. Boysel, “Nanofabrication of optical structures and devices for photonics and biophotonics,” J. Mod. Opt. 50, 2543–2550 (2003).

Pezzoli, E.

D. T. Chiu, E. Pezzoli, H. Wu, A. D. Stroock, and G. M. Whitesides, “Using three-dimensional microfluidic networks for solving computationally hard problems,” Proc. Natl. Acad. Sci. U.S.A. 98(6), 2961–2966 (2001).
[PubMed]

Politi, A.

Prabhu, M.

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

Ramponi, R.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

N. Spagnolo, L. Aparo, C. Vitelli, A. Crespi, R. Ramponi, R. Osellame, P. Mataloni, and F. Sciarrino, “Quantum interferometry with three-dimensional geometry,” Sci. Rep. 2, 862 (2012).
[PubMed]

L. Sansoni, F. Sciarrino, G. Vallone, P. Mataloni, A. Crespi, R. Ramponi, and R. Osellame, “Polarization entangled state measurement on a chip,” Phys. Rev. Lett. 105(20), 200503 (2010).
[PubMed]

Ross, I. C.

F. Harary and I. C. Ross, “A procedure for clique detection using the group matrix,” Sociometry 20, 205–215 (1957).

Sansoni, L.

L. Sansoni, F. Sciarrino, G. Vallone, P. Mataloni, A. Crespi, R. Ramponi, and R. Osellame, “Polarization entangled state measurement on a chip,” Phys. Rev. Lett. 105(20), 200503 (2010).
[PubMed]

Schweinsberg, A.

R. W. Boyd, J. E. Heebner, N. N. Lepeshkin, Q. H. Park, A. Schweinsberg, G. W. Wicks, and R. M. Boysel, “Nanofabrication of optical structures and devices for photonics and biophotonics,” J. Mod. Opt. 50, 2543–2550 (2003).

Sciarrino, F.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

N. Spagnolo, L. Aparo, C. Vitelli, A. Crespi, R. Ramponi, R. Osellame, P. Mataloni, and F. Sciarrino, “Quantum interferometry with three-dimensional geometry,” Sci. Rep. 2, 862 (2012).
[PubMed]

L. Sansoni, F. Sciarrino, G. Vallone, P. Mataloni, A. Crespi, R. Ramponi, and R. Osellame, “Polarization entangled state measurement on a chip,” Phys. Rev. Lett. 105(20), 200503 (2010).
[PubMed]

Shah, L.

Shell, M. S.

K. A. Dill, S. B. Ozkan, M. S. Shell, and T. R. Weikl, “The protein folding problem,” Annu. Rev. Biophys. 37, 289–316 (2008).
[PubMed]

Shen, Y.

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

Shinojima, H.

K. Yamada, T. Tsuchizawa, R. Kou, H. Nishi, H. Shinojima, Y. Ishikawa, K. Wada, and S. Mutoh, “Silicon photonic platform for telecommunications applications,” in Photonics Conference (IEEE, 2011), pp. 591–592.

Shum, P. P.

W. Hu, K. Wu, P. P. Shum, N. I. Zheludev, and C. Soci, “All-Optical Implementation of the Ant Colony Optimization Algorithm,” Sci. Rep. 6, 26283 (2016).
[PubMed]

K. Wu, J. García de Abajo, C. Soci, P. P. Shum, and N. I. Zheludev, “An optical fiber network oracle for NP-complete problems,” Light Sci. Appl. 3, e147 (2014).

K. Wu, C. Soci, P. P. Shum, and N. I. Zheludev, “Computing matrix inversion with optical networks,” Opt. Express 22(1), 295–304 (2014).
[PubMed]

Skirlo, S.

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

Smith, B. J.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Smith, L. M.

Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith, “DNA computing on surfaces,” Nature 403(6766), 175–179 (2000).
[PubMed]

Smith, P. G. R.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Soci, C.

W. Hu, K. Wu, P. P. Shum, N. I. Zheludev, and C. Soci, “All-Optical Implementation of the Ant Colony Optimization Algorithm,” Sci. Rep. 6, 26283 (2016).
[PubMed]

B. Gholipour, P. Bastock, C. Craig, K. Khan, D. Hewak, and C. Soci, “Amorphous Metal‐Sulphide Microfibers Enable Photonic Synapses for Brain‐Like Computing,” Adv. Opt. Mater. 3, 635–641 (2015).

K. Wu, J. García de Abajo, C. Soci, P. P. Shum, and N. I. Zheludev, “An optical fiber network oracle for NP-complete problems,” Light Sci. Appl. 3, e147 (2014).

K. Wu, C. Soci, P. P. Shum, and N. I. Zheludev, “Computing matrix inversion with optical networks,” Opt. Express 22(1), 295–304 (2014).
[PubMed]

Solis, J.

Soljacic, M.

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

Sotillo, B.

Spagnolo, N.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

N. Spagnolo, L. Aparo, C. Vitelli, A. Crespi, R. Ramponi, R. Osellame, P. Mataloni, and F. Sciarrino, “Quantum interferometry with three-dimensional geometry,” Sci. Rep. 2, 862 (2012).
[PubMed]

Spring, J. B.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Steel, M. J.

T. Meany, S. Gross, N. Jovanic, A. Arriola, M. J. Steel, and M. J. Withford, “Towards low-loss lightwave circuits for non-classical optics at 800 and 1,550 nm,” Appl. Phys., A Mater. Sci. Process. 114(1), 113–118 (2014).

Stroock, A. D.

D. T. Chiu, E. Pezzoli, H. Wu, A. D. Stroock, and G. M. Whitesides, “Using three-dimensional microfluidic networks for solving computationally hard problems,” Proc. Natl. Acad. Sci. U.S.A. 98(6), 2961–2966 (2001).
[PubMed]

Sun, X.

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

Tengely, S.

P. Frisco, C. Henkel, and S. Tengely, “An algorithm for SAT without an extraction phase,” in International Workshop on DNA-Based Computers (Springer, 2005), pp. 67–80.

Thomas-Peter, N.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Tsai, C. W.

K. W. Huang, J. L. Chen, C. S. Yang, and C. W. Tsai, “A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem,” Neural Comput. Appl. 26, 495–506 (2015).

Tsuchizawa, T.

K. Yamada, T. Tsuchizawa, R. Kou, H. Nishi, H. Shinojima, Y. Ishikawa, K. Wada, and S. Mutoh, “Silicon photonic platform for telecommunications applications,” in Photonics Conference (IEEE, 2011), pp. 591–592.

Vallone, G.

L. Sansoni, F. Sciarrino, G. Vallone, P. Mataloni, A. Crespi, R. Ramponi, and R. Osellame, “Polarization entangled state measurement on a chip,” Phys. Rev. Lett. 105(20), 200503 (2010).
[PubMed]

Vitelli, C.

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

N. Spagnolo, L. Aparo, C. Vitelli, A. Crespi, R. Ramponi, R. Osellame, P. Mataloni, and F. Sciarrino, “Quantum interferometry with three-dimensional geometry,” Sci. Rep. 2, 862 (2012).
[PubMed]

Wada, K.

K. Yamada, T. Tsuchizawa, R. Kou, H. Nishi, H. Shinojima, Y. Ishikawa, K. Wada, and S. Mutoh, “Silicon photonic platform for telecommunications applications,” in Photonics Conference (IEEE, 2011), pp. 591–592.

Walmsley, I. A.

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Wang, L.

Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith, “DNA computing on surfaces,” Nature 403(6766), 175–179 (2000).
[PubMed]

Webb, Z.

A. M. Childs, D. Gosset, and Z. Webb, “Universal computation by multiparticle quantum walk,” Science 339(6121), 791–794 (2013).
[PubMed]

Weikl, T. R.

K. A. Dill, S. B. Ozkan, M. S. Shell, and T. R. Weikl, “The protein folding problem,” Annu. Rev. Biophys. 37, 289–316 (2008).
[PubMed]

Whitesides, G. M.

D. T. Chiu, E. Pezzoli, H. Wu, A. D. Stroock, and G. M. Whitesides, “Using three-dimensional microfluidic networks for solving computationally hard problems,” Proc. Natl. Acad. Sci. U.S.A. 98(6), 2961–2966 (2001).
[PubMed]

Wicks, G. W.

R. W. Boyd, J. E. Heebner, N. N. Lepeshkin, Q. H. Park, A. Schweinsberg, G. W. Wicks, and R. M. Boysel, “Nanofabrication of optical structures and devices for photonics and biophotonics,” J. Mod. Opt. 50, 2543–2550 (2003).

Withford, M. J.

T. Meany, S. Gross, N. Jovanic, A. Arriola, M. J. Steel, and M. J. Withford, “Towards low-loss lightwave circuits for non-classical optics at 800 and 1,550 nm,” Appl. Phys., A Mater. Sci. Process. 114(1), 113–118 (2014).

G. D. Marshall, A. Politi, J. C. Matthews, P. Dekker, M. Ams, M. J. Withford, and J. L. O’Brien, “Laser written waveguide photonic quantum circuits,” Opt. Express 17(15), 12546–12554 (2009).
[PubMed]

Wu, H.

H. Wu, “An improved surface-based method for DNA computation,” Biosystems 59(1), 1–5 (2001).
[PubMed]

D. T. Chiu, E. Pezzoli, H. Wu, A. D. Stroock, and G. M. Whitesides, “Using three-dimensional microfluidic networks for solving computationally hard problems,” Proc. Natl. Acad. Sci. U.S.A. 98(6), 2961–2966 (2001).
[PubMed]

Wu, K.

W. Hu, K. Wu, P. P. Shum, N. I. Zheludev, and C. Soci, “All-Optical Implementation of the Ant Colony Optimization Algorithm,” Sci. Rep. 6, 26283 (2016).
[PubMed]

K. Wu, J. García de Abajo, C. Soci, P. P. Shum, and N. I. Zheludev, “An optical fiber network oracle for NP-complete problems,” Light Sci. Appl. 3, e147 (2014).

K. Wu, C. Soci, P. P. Shum, and N. I. Zheludev, “Computing matrix inversion with optical networks,” Opt. Express 22(1), 295–304 (2014).
[PubMed]

Xu, C. L.

W. P. Huang and C. L. Xu, “Simulation of three-dimensional optical waveguides by a full-vector beam propagation method,” IEEE J. Quantum Electron. 29, 2639–2649 (1993).

Yamada, K.

K. Yamada, T. Tsuchizawa, R. Kou, H. Nishi, H. Shinojima, Y. Ishikawa, K. Wada, and S. Mutoh, “Silicon photonic platform for telecommunications applications,” in Photonics Conference (IEEE, 2011), pp. 591–592.

Yang, C. S.

K. W. Huang, J. L. Chen, C. S. Yang, and C. W. Tsai, “A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem,” Neural Comput. Appl. 26, 495–506 (2015).

Yang, Y.

Yariv, A.

A. Yariv, “Coupled-mode theory for guided-wave optics,” IEEE J. Quantum Electron. 9, 919–933 (1973).

Yoshino, F.

Zhang, H.

Zhang, L.

S. M. Eaton, W. Chen, L. Zhang, H. Zhang, R. Iyer, J. S. Aitchison, and P. R. Herman, “Telecom-band directional coupler written with femtosecond fiber laser,” IEEE Photonics Technol. Lett. 18, 2174–2176 (2006).

Zhao, S.

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

Zheludev, N. I.

W. Hu, K. Wu, P. P. Shum, N. I. Zheludev, and C. Soci, “All-Optical Implementation of the Ant Colony Optimization Algorithm,” Sci. Rep. 6, 26283 (2016).
[PubMed]

K. Wu, J. García de Abajo, C. Soci, P. P. Shum, and N. I. Zheludev, “An optical fiber network oracle for NP-complete problems,” Light Sci. Appl. 3, e147 (2014).

K. Wu, C. Soci, P. P. Shum, and N. I. Zheludev, “Computing matrix inversion with optical networks,” Opt. Express 22(1), 295–304 (2014).
[PubMed]

ACM Sigact News (1)

S. Aaronson, “NP-Complete Problems and Physical Reality,” ACM Sigact News 36, 30–52 (2005).

Adv. Opt. Mater. (1)

B. Gholipour, P. Bastock, C. Craig, K. Khan, D. Hewak, and C. Soci, “Amorphous Metal‐Sulphide Microfibers Enable Photonic Synapses for Brain‐Like Computing,” Adv. Opt. Mater. 3, 635–641 (2015).

Annu. Rev. Biophys. (1)

K. A. Dill, S. B. Ozkan, M. S. Shell, and T. R. Weikl, “The protein folding problem,” Annu. Rev. Biophys. 37, 289–316 (2008).
[PubMed]

Appl. Phys., A Mater. Sci. Process. (1)

T. Meany, S. Gross, N. Jovanic, A. Arriola, M. J. Steel, and M. J. Withford, “Towards low-loss lightwave circuits for non-classical optics at 800 and 1,550 nm,” Appl. Phys., A Mater. Sci. Process. 114(1), 113–118 (2014).

Biosystems (1)

H. Wu, “An improved surface-based method for DNA computation,” Biosystems 59(1), 1–5 (2001).
[PubMed]

Bull. Math. Biol. (1)

A. S. Fraenkel, “Complexity of protein folding,” Bull. Math. Biol. 55(6), 1199–1210 (1993).
[PubMed]

IEEE J. Quantum Electron. (2)

W. P. Huang and C. L. Xu, “Simulation of three-dimensional optical waveguides by a full-vector beam propagation method,” IEEE J. Quantum Electron. 29, 2639–2649 (1993).

A. Yariv, “Coupled-mode theory for guided-wave optics,” IEEE J. Quantum Electron. 9, 919–933 (1973).

IEEE Photonics Technol. Lett. (1)

S. M. Eaton, W. Chen, L. Zhang, H. Zhang, R. Iyer, J. S. Aitchison, and P. R. Herman, “Telecom-band directional coupler written with femtosecond fiber laser,” IEEE Photonics Technol. Lett. 18, 2174–2176 (2006).

J. Bioinform. Comput. Biol. (1)

C. Guyeux, N. M. Côté, J. M. Bahi, and W. Bienia, “Is protein folding problem really a NP-complete one? First investigations,” J. Bioinform. Comput. Biol. 12(1), 1350017 (2014).
[PubMed]

J. Mod. Opt. (1)

R. W. Boyd, J. E. Heebner, N. N. Lepeshkin, Q. H. Park, A. Schweinsberg, G. W. Wicks, and R. M. Boysel, “Nanofabrication of optical structures and devices for photonics and biophotonics,” J. Mod. Opt. 50, 2543–2550 (2003).

Light Sci. Appl. (1)

K. Wu, J. García de Abajo, C. Soci, P. P. Shum, and N. I. Zheludev, “An optical fiber network oracle for NP-complete problems,” Light Sci. Appl. 3, e147 (2014).

Nat. Comput. (1)

M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Nat. Comput. 7, 57–70 (2008).

Nat. Photonics (2)

N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvao, and F. Sciarrino, “Experimental validation of photonic boson sampling,” Nat. Photonics 8, 615–620 (2014).

Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund, and M. Soljačić, “Deep learning with coherent nanophotonic circuits,” Nat. Photonics 11, 441–446 (2017).

Nature (1)

Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith, “DNA computing on surfaces,” Nature 403(6766), 175–179 (2000).
[PubMed]

Neural Comput. Appl. (1)

K. W. Huang, J. L. Chen, C. S. Yang, and C. W. Tsai, “A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem,” Neural Comput. Appl. 26, 495–506 (2015).

Opt. Express (8)

S. Eaton, H. Zhang, P. Herman, F. Yoshino, L. Shah, J. Bovatsek, and A. Arai, “Heat accumulation effects in femtosecond laser-written waveguides with variable repetition rate,” Opt. Express 13(12), 4708–4716 (2005).
[PubMed]

T. Haist and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15(16), 10473–10482 (2007).
[PubMed]

S. M. Eaton, H. Zhang, M. L. Ng, J. Li, W. J. Chen, S. Ho, and P. R. Herman, “Transition from thermal diffusion to heat accumulation in high repetition rate femtosecond laser writing of buried optical waveguides,” Opt. Express 16(13), 9443–9458 (2008).
[PubMed]

W. J. Chen, S. M. Eaton, H. Zhang, and P. R. Herman, “Broadband directional couplers fabricated in bulk glass with high repetition rate femtosecond laser pulses,” Opt. Express 16(15), 11470–11480 (2008).
[PubMed]

G. D. Marshall, A. Politi, J. C. Matthews, P. Dekker, M. Ams, M. J. Withford, and J. L. O’Brien, “Laser written waveguide photonic quantum circuits,” Opt. Express 17(15), 12546–12554 (2009).
[PubMed]

K. Wu, C. Soci, P. P. Shum, and N. I. Zheludev, “Computing matrix inversion with optical networks,” Opt. Express 22(1), 295–304 (2014).
[PubMed]

T. T. Fernandez, M. Hernandez, B. Sotillo, S. M. Eaton, G. Jose, R. Osellame, A. Jha, P. Fernandez, and J. Solis, “Role of ion migrations in ultrafast laser written tellurite glass waveguides,” Opt. Express 22(12), 15298–15304 (2014).
[PubMed]

Y. Yang, Y. Ma, H. Guan, Y. Liu, S. Danziger, S. Ocheltree, K. Bergman, T. Baehr-Jones, and M. Hochberg, “Phase coherence length in silicon photonic platform,” Opt. Express 23(13), 16890–16902 (2015).
[PubMed]

Phys. Rev. Lett. (1)

L. Sansoni, F. Sciarrino, G. Vallone, P. Mataloni, A. Crespi, R. Ramponi, and R. Osellame, “Polarization entangled state measurement on a chip,” Phys. Rev. Lett. 105(20), 200503 (2010).
[PubMed]

Proc. Natl. Acad. Sci. U.S.A. (1)

D. T. Chiu, E. Pezzoli, H. Wu, A. D. Stroock, and G. M. Whitesides, “Using three-dimensional microfluidic networks for solving computationally hard problems,” Proc. Natl. Acad. Sci. U.S.A. 98(6), 2961–2966 (2001).
[PubMed]

Protein Eng. (1)

R. H. Lathrop, “The protein threading problem with sequence amino acid interaction preferences is NP-complete,” Protein Eng. 7(9), 1059–1068 (1994).
[PubMed]

Sci. Rep. (2)

W. Hu, K. Wu, P. P. Shum, N. I. Zheludev, and C. Soci, “All-Optical Implementation of the Ant Colony Optimization Algorithm,” Sci. Rep. 6, 26283 (2016).
[PubMed]

N. Spagnolo, L. Aparo, C. Vitelli, A. Crespi, R. Ramponi, R. Osellame, P. Mataloni, and F. Sciarrino, “Quantum interferometry with three-dimensional geometry,” Sci. Rep. 2, 862 (2012).
[PubMed]

Science (4)

Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber, “DNA solution of the maximal clique problem,” Science 278(5337), 446–449 (1997).
[PubMed]

A. M. Childs, D. Gosset, and Z. Webb, “Universal computation by multiparticle quantum walk,” Science 339(6121), 791–794 (2013).
[PubMed]

J. L. O’Brien, “Optical quantum computing,” Science 318(5856), 1567–1570 (2007).
[PubMed]

J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X. M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, “Boson sampling on a photonic chip,” Science 339(6121), 798–801 (2013).
[PubMed]

Sociometry (1)

F. Harary and I. C. Ross, “A procedure for clique detection using the group matrix,” Sociometry 20, 205–215 (1957).

Theor. Comput. Sci. (1)

S. Dolev and H. Fitoussi, “Masking traveling beams: Optical solutions for NP-complete problems, trading space for time,” Theor. Comput. Sci. 411, 837–853 (2010).

Other (8)

L. Fortnow, The golden ticket: P, NP, and the search for the impossible (Princeton University Press, 2013).

P. E. Dunne, “An annotated list of selected NP-complete problems,” http://cgi.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html .

M. Oltean and O. Muntean, “Evolutionary design of graph-based structures for optical computing,” in International Workshop on Optical Supercomputing, (Springer Berlin Heidelberg, 2009), pp. 56–69.

Corning, “Corning EAGLE2000 AMLCD glass substrates material information,” http://www.corning.com/displaytechnologies .

K. Yamada, T. Tsuchizawa, R. Kou, H. Nishi, H. Shinojima, Y. Ishikawa, K. Wada, and S. Mutoh, “Silicon photonic platform for telecommunications applications,” in Photonics Conference (IEEE, 2011), pp. 591–592.

P. Frisco, C. Henkel, and S. Tengely, “An algorithm for SAT without an extraction phase,” in International Workshop on DNA-Based Computers (Springer, 2005), pp. 67–80.

N. M. Estakhri, B. E. Edwards, and N. Engheta, “Solving Integral Equations with optical Metamaterial-Waveguide Networks” in Conference on Lasers and Electro-Optics, OSA Technical Digest (Optical Society of America, 2017), paper FTh1G.2.

R. Trebino, Frequency-Resolved Optical Gating: The measurement of Ultrashort Laser Pulses, (Springer Science & Business Media, 2012).

Cited By

OSA participates in Crossref's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (4)

Fig. 1
Fig. 1

Femtosecond laser-written optical oracle design. The photonic waveguide network mimics the topology of a network with four nodes or towns in which each town is a 3-dB directional coupler for a 50:50 power splitting ratio.

Fig. 2
Fig. 2

(a) Optical cross-correlator setup for time resolved measurements. (b) Optical autocorrelation measured in free space, and after propagation in the oracle chip and in the control sample, respectively. (c) Femtosecond output pulses in time domain detected from oracle chip and control sample. The node number visited by each pulse is indicated next to every peak.

Fig. 3
Fig. 3

Waveguide characterization. (a) Overhead white-light microscopy of a waveguide. Two different zones can be clearly differentiated: the core along the central part, where maximum change in refractive index is reached, and the cladding at its surrounding. (b) Cross-sectional white-light-microscopic image of the waveguide at its end facet. (c) Guided mode at 808 nm wavelength with MFD of 6.5 µm × 7.1 µm.

Fig. 4
Fig. 4

(a) Directional coupler with S-bend geometry. The different parameters are: pitch between access ports, p, radius of curvature, R, separation distance, s, and interaction length, L. P0 represents the optical input power injected into a single arm while P1 and P2 are the through and cross output port powers, respectively. (b) Experimental and simulated bend loss as a function of bend radius for a S-bend waveguide. (c) Beat length as a function of the separation distance. (d) Experimental power coupling ratio versus interaction length for a separation distance of s = 7 µm. The dot lines in blue indicate a 50% power coupling ratio at an interaction length of 700 µm.

Tables (1)

Tables Icon

Table 1 Waveguide path lengths designed for the oracle chip.