Status | Confirmed |
Seminar Series | SEM-LPTHE |
Subjects | cond-mat.stat-mech |
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 | Quantum-inspired 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 many-body 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 state-of-the-art 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 near-term quantum circuits. |
arXiv Preprint Number | |
Comments | |
Attachments |
To Generate a poster for this seminar : [ Postscript | PDF ]
|
[ English version ] |