## Optical solver of combinatorial problems: nanotechnological approach |

JOSA A, Vol. 30, Issue 9, pp. 1845-1853 (2013)

http://dx.doi.org/10.1364/JOSAA.30.001845

Enhanced HTML Acrobat PDF (931 KB)

### 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: Year | Journal | Reset

### References

- H. J. Caulfield and S. Dolev, “Why future supercomputing requires optics,” Nat. Photonics 4, 261263 (2010). [CrossRef]
- 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.
- J. H. Reif, D. Tygar, and A. Yoshida, “The computability and complexity of ray tracing,” Discrete Comput. Geom., 11, 265–288 (1994). [CrossRef]
- S. Dolev and N. Yuval, “Optical implementation of bounded non-deterministic Turing machines,” U.S. patent7,130,093 B2 (October31, 2006).
- 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.
- T. Haist and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15, 10473–10482 (2007). [CrossRef]
- 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.
- S. Dolev and H. Fitoussi, “The traveling beams: optical solutions for bounded NP-complete problems,” (Ben Gurion University of the Negev, 2007).
- 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]
- 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.
- 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]
- G. Feitelson, Optical Computing: A Survey for Computer Scientists (MIT, 1988).
- A. D. McAulay, Optical Computer Architectures (Wiley, 1991).
- A. Hyman, Charles Babbage: Pioneer of the Computer (Princeton University, 1982).
- S. Arora and B. Barak, Complexity Theory: A Modern Approach (Cambridge University, 2009).
- Lenslet LTD, “Lenslet Demonstrates First Commercial Optical Processor,” http://www.taborcommunications.com/hpcwire/hpcwireWWW/03/1017/106185.html .
- N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP-complete problems,” Appl. Opt. 46, 711–724 (2007). [CrossRef]
- 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.
- 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.
- S. Dolev, E. Korach, and G. Uzan, “A method for encryption and decryption of messages,” Patent applicationPCT/IL2005/000669 (December7, 2006).
- A. Anter and S. Dolev, “Optical solution for hard on average #P-complete instances,” Natural Comput. 9, 891–902 (2010). [CrossRef]
- H. J. Mann, W. Ulrich, and G. Seitz, “8-mirror microlithography projection objective,” U.S. patent7,177,076 B2 (February13, 2007).
- 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.
- 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.
- 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]
- 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.