Events
Event Information:

Tue25Sep20184:00 pmLewis Hall 101
Colloquium: Quantuminspired Approaches to Hard Computational Problems
Stefanos Kourtis
Physics Department
Boston UniversityQuantuminspired Approaches to Hard Computational Problems
Many classes of complex computational problems admit no efficient solution or even approximation, yet have a vast reach in applications across science and industry. From a physics perspective, computational complexity originates from strong correlations between bits of information. It is reasonable to ask whether computational approaches to quantum manybody problems can be practically useful in this context. In this talk, I will present newly found cases where the answer is affirmative. I will introduce constraint satisfaction problems (CSPs) and reformulate them as interacting models whose ground states represent the solution manifold. A procedure that reaches the ground states of these models implements a protocol of computation. In some protocols, the complexity that arises during computation can be viewed as quantum entanglement, and efficiency is achieved by controlling its growth. Using this reasoning, I will introduce practical methods for solving CSPs based on tensor network contraction and demonstrate that they outperform stateoftheart solvers for some of these problems by a significant margin. I will conclude with an outline of ongoing work on extensions and applications to problems of current interest, such as the simulation of existing and nearterm quantum circuits.