Regensburg 2019 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

DY: Fachverband Dynamik und Statistische Physik

DY 19: Complex Systems

DY 19.4: Talk

Tuesday, April 2, 2019, 12:30–12:45, H6

Contracting projected entangled pair states is average-case hard — •Jonas Haferkamp, Dominik Hangleiter, Jens Eisert, and Marek Gluza — Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany

An accurate calculation of the properties of quantum many-body systems is one of the most important yet intricate challenges of modern physics and computer science. In recent years, the tensor network ansatz has established itself as one of the most promising approaches. In higher dimensions, however, a connection to the field of computational complexity theory has shown that the accurate normalization of the two-dimensional tensor networks called projected entangled pair states (PEPS) is #P complete. Therefore, an efficient algorithm for PEPS contraction would allow to solve exceedingly difficult combinatorial counting problems, which is considered highly unlikely. Due to the importance of understanding two- and three-dimensional systems the question currently remains: Are the known constructions typical of states relevant for quantum many-body systems? In this work, we show that an accurate evaluation of normalization or expectation values of PEPS is as hard to compute for typical instances as for special configurations of highest computational hardness.