Sur ce site

Sur le Web du CNRS

Accueil du site > Séminaires > Séminaires 2018 > Quantum-inspired approaches to hard computational problems

Mardi 16 octobre 2018 - 14:15

Quantum-inspired approaches to hard computational problems

Stefanos Kourtis (Boston University)

par Revaz Ramazashvili - 16 octobre 2018

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.

Post-scriptum :

contact : F. Alet