Status  Confirmed 
Seminar Series  SEMLPTHE 
Subjects  condmat.statmech 
Date  Friday 19 October 2018 
Time  11:00 
Institute  LPTHE 
Seminar Room  Bibliothèque 
Speaker's Last Name  Kourtis 
Speaker's First Name  Stefanos 
Speaker's Email Address  
Speaker's Institution  Boston University 
Title  Quantuminspired approaches to hard computational problems 
Abstract  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 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. 
arXiv Preprint Number  
Comments  
Attachments 
To Generate a poster for this seminar : [ Postscript  PDF ]

[ English version ] 