Statut  Confirmé 
Série  SEMLPTHE 
Domaines  condmat.statmech 
Date  Vendredi 19 Octobre 2018 
Heure  11:00 
Institut  LPTHE 
Salle  Bibliothèque 
Nom de l'orateur  Kourtis 
Prenom de l'orateur  Stefanos 
Addresse email de l'orateur  
Institution de l'orateur  Boston University 
Titre  Quantuminspired approaches to hard computational problems 
Résumé  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. 
Numéro de preprint arXiv  
Commentaires  
Fichiers attachés 
Pour obtenir l' affiche de ce séminaire : [ Postscript  PDF ]

[ English version ] 