Optically solving the Distance Geometry Problem
Several problems are too complex for conventional computers, or require large computational resources to be solved. New methods utilizing light can offer speedier results, which can be particularly interesting when approaching NP-complete problems by reducing the time complexity via, e.g., massive parallel computing. Here, we propose an optical scheme to solve the one-dimensional Distance Geometry Problem (DGP1). We focus on a class of DGP1 instances consisting of a sequence of n vertices with known distances to its immediate predecessor. We also suppose that the distance between the first and the n-th vertex is known. Although arranging to a final closed graph, the possible solutions are still exponentially growing up to the last (but first) vertex, making this kind of instances hard to solve in practice. We propose to reformulate the DGP1 instance in a matrix formalism and map it to a spatial modulation of light. We then combine the modulated light polarization with lenses to perform the required matrix operations in the seek for a solution. In this talk, I will present our approach and discuss its potential advantages and limitations.