Despite large advances in both algorithms and computer technology, even typical instances of certain computationally hard problems (NP-hard) may be too difficult to be solved on today’s computers. In certain areas of application unconventional computational devices could help to overcome these limitations. This research project aims at ultrafast analog simulations of classical spin systems using a large-scale network of coupled photon Bose-Einstein condensates.
An important goal of this project is to use photon BEC networks as a tool for solving the ground-state energy problem (GSE) in the disordered XY model faster than any other computer today. The ground-state energy problem in XY spin glasses, which corresponds to finding the lowest energy state in a frustrated magnet, is a difficult combinatorial problem that is known to be NP-hard. The latter implies that every other NP problem can be mapped onto the GSE problem in XY spin glasses in polynomial time. A computer that solves the GSE problem, thus, solves the whole class of NP problems. That includes, for example, instances of the famous traveling salesman, graph coloring, and partitioning problem. A device that significantly speeds up such calculations would represent a tremendous breakthrough in computing.
- D. Dung, C. Kurtscheid, T. Damm, J. Schmitt, F. Vewinger, M. Weitz, and J. Klaers, “Variable potentials for thermalized light and coupled condensates”, Nature Photonics 11, 565 (2017). link