OSA's Digital Library

Journal of the Optical Society of America A

Journal of the Optical Society of America A

| OPTICS, IMAGE SCIENCE, AND VISION

  • Editor: Franco Gori
  • Vol. 30, Iss. 9 — Sep. 1, 2013
  • pp: 1845–1853

Optical solver of combinatorial problems: nanotechnological approach

Eyal Cohen, Shlomi Dolev, Sergey Frenkel, Boris Kryzhanovsky, Alexandr Palagushkin, Michael Rosenblit, and Victor Zakharov  »View Author Affiliations


JOSA A, Vol. 30, Issue 9, pp. 1845-1853 (2013)
http://dx.doi.org/10.1364/JOSAA.30.001845


View Full Text Article

Enhanced HTML    Acrobat PDF (931 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

We present an optical computing system to solve NP-hard problems. As nano-optical computing is a promising venue for the next generation of computers performing parallel computations, we investigate the application of submicron, or even subwavelength, computing device designs. The system utilizes a setup of exponential sized masks with exponential space complexity produced in polynomial time preprocessing. The masks are later used to solve the problem in polynomial time. The size of the masks is reduced to nanoscaled density. Simulations were done to choose a proper design, and actual implementations show the feasibility of such a system.

© 2013 Optical Society of America

OCIS Codes
(200.0200) Optics in computing : Optics in computing
(200.3760) Optics in computing : Logic-based optical processing
(200.4560) Optics in computing : Optical data processing
(200.4660) Optics in computing : Optical logic
(200.4740) Optics in computing : Optical processing
(200.4860) Optics in computing : Optical vector-matrix systems

ToC Category:
Optics in Computing

History
Original Manuscript: April 18, 2013
Revised Manuscript: June 23, 2013
Manuscript Accepted: June 24, 2013
Published: August 22, 2013

Citation
Eyal Cohen, Shlomi Dolev, Sergey Frenkel, Boris Kryzhanovsky, Alexandr Palagushkin, Michael Rosenblit, and Victor Zakharov, "Optical solver of combinatorial problems: nanotechnological approach," J. Opt. Soc. Am. A 30, 1845-1853 (2013)
http://www.opticsinfobase.org/josaa/abstract.cfm?URI=josaa-30-9-1845


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. H. J. Caulfield and S. Dolev, “Why future supercomputing requires optics,” Nat. Photonics 4, 261263 (2010). [CrossRef]
  2. J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of optical beam tracing,” in 31st Annual IEEE Symposium on Foundations of Computer Science (1990), pp. 106–114.
  3. J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of ray tracing,” Discrete Comput. Geom., 11, 265–288 (1994). [CrossRef]
  4. S. Dolev and N. Yuval, “Optical implementation of bounded non-deterministic Turing machines,” U.S. patent7,130,093 B2 (October31, 2006).
  5. M. Oltean, “A light-based device for solving the Hamiltonian path problem,” in Proceedings of Unconventional Computing, C. Calude, M. J. Dinneen, G. Păun, G. Rozenberg, and S. Stepney, eds., Vol. 4135 of Lecture Notes in Computer Science (Springer-Verlag, 2006), pp. 217–227.
  6. T. Haist and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15, 10473–10482 (2007). [CrossRef]
  7. S. Dolev and H. Fitoussi, “Primitive operations for graph-optical processor,” presented at 6th Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms, May2006.
  8. S. Dolev and H. Fitoussi, “The traveling beams: optical solutions for bounded NP-complete problems,” (Ben Gurion University of the Negev, 2007).
  9. 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). [CrossRef]
  10. E. Cohen, S. Dolev, S. Frenkel, R. Puzis, and M. Rosenblit, “Nanotechnology based optical solution for NP-hard problems,” in Proceedings of Optical Super Computing (2010), pp. 86–99.
  11. D. Gutfreund, R. Shaltiel, and A. Ta-Shma, “If NP languages are hard on the worst-case, then it is easy to find their hard instances,” Comput. Complex. 16, 412–441 (2007). [CrossRef]
  12. G. Feitelson, Optical Computing: A Survey for Computer Scientists (MIT, 1988).
  13. A. D. McAulay, Optical Computer Architectures (Wiley, 1991).
  14. A. Hyman, Charles Babbage: Pioneer of the Computer (Princeton University, 1982).
  15. S. Arora and B. Barak, Complexity Theory: A Modern Approach (Cambridge University, 2009).
  16. Lenslet LTD, “Lenslet Demonstrates First Commercial Optical Processor,” http://www.taborcommunications.com/hpcwire/hpcwireWWW/03/1017/106185.html .
  17. N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP-complete problems,” Appl. Opt. 46, 711–724 (2007). [CrossRef]
  18. D. E. Tamir, N. T. Shaked, P. J. Wilson, and S. Dolev, “Electro-optical DSP of tera operation per second and beyond,” in Proceedings of the First International Workshop on Optical Super Computing, Vol. 5172 of Lecture Notes in Computer Science (Springer-Verlag, 2008), pp. 56–59.
  19. P. van Emde Boas, “Machine models and simulation,” in Handbook of Theoretical Computer Science, Vol.  A of Algorithms and Complexity (Elsevier, 1990), pp. 1–66.
  20. S. Dolev, E. Korach, and G. Uzan, “A method for encryption and decryption of messages,” Patent applicationPCT/IL2005/000669 (December7, 2006).
  21. A. Anter and S. Dolev, “Optical solution for hard on average #P-complete instances,” Natural Comput. 9, 891–902 (2010). [CrossRef]
  22. H. J. Mann, W. Ulrich, and G. Seitz, “8-mirror microlithography projection objective,” U.S. patent7,177,076 B2 (February13, 2007).
  23. W. Xiajun, X. Zhao, A. Bermak, and F. Boussaid, “An AER based CMOS polarization image sensor with photo-aligned micropolarizer array,” in Proceedings of 1st Asia Symposium on Quality Electronic Design (IEEE, 2009), pp. 126–130.
  24. S. Goliaei and M.-H. Foroughmand-Araabi, “Lower bounds on the complexity of the wavelength-based machine,” in Unconventional Computation and Natural Computation, Vol. 7445 of Lecture Notes in Computer Science (2012), pp. 94–105.
  25. B. V. Kryzhanovsky, A. N. Palagushkin, S. A. Prokopenko, A. P. Sergeev, and A. O. Melikyan, “Controlling reflectivity of silver-corundum-silver nanostructure by DC voltage,.” Opt. Mem. Neural Netw. 22, 1–7 (2013). [CrossRef]
  26. W. Zhou, J. Lee, J. Nanda, S. T. Pantelides, S. J. Pennycook, and J. C. Idrobo, “Atomically localized plasmon enhancement in monolayer graphene,” Nat. Nanotechnol. 7, 161–165 (2012). [CrossRef]

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited