dc.contributor.author
Haferkamp, Jonas
dc.contributor.author
Hangleiter, Dominik
dc.contributor.author
Eisert, Jens
dc.contributor.author
Gluza, Marek
dc.date.accessioned
2021-11-08T12:40:03Z
dc.date.available
2021-11-08T12:40:03Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/30338
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-30079
dc.description.abstract
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 enabling striking efficiency of simulating static properties of one-dimensional systems and abounding numerical applications in condensed matter theory. 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 solving 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. We discuss the structural property of average-case hardness in relation to the current research on efficient algorithms attempting tensor network contraction, hinting at a wealth of possible further insights into the average-case hardness of important problems in quantum many-body theory.
en
dc.format.extent
9 Seiten
dc.rights.uri
https://creativecommons.org/licenses/by/4.0/
dc.subject
Quantum entanglement
en
dc.subject
Computational complexity
en
dc.subject
Many-body techniques
en
dc.subject
Tensor network methods
en
dc.subject
Quantum Information
en
dc.subject.ddc
500 Naturwissenschaften und Mathematik::530 Physik::539 Moderne Physik
dc.title
Contracting projected entangled pair states is average-case hard
dc.type
Wissenschaftlicher Artikel
dc.identifier.sepid
81405
dcterms.bibliographicCitation.articlenumber
013010
dcterms.bibliographicCitation.doi
10.1103/PhysRevResearch.2.013010
dcterms.bibliographicCitation.journaltitle
Physical Review Research
dcterms.bibliographicCitation.number
1
dcterms.bibliographicCitation.originalpublishername
American Physical Society
dcterms.bibliographicCitation.originalpublisherplace
College Park, MD
dcterms.bibliographicCitation.volume
2
dcterms.bibliographicCitation.url
https://link.aps.org/doi/10.1103/PhysRevResearch.2.013010
refubium.affiliation
Physik
refubium.affiliation.other
Institut für Theoretische Physik
![Dieser Normdateneintrag wurde von einer Benutzerin oder einem Benutzer als gültig bestätigt.](/cache_202e45ad85b55efaeb29160f63cd3f3b/themes/FuCD/images/authority_control/invisible.gif)
refubium.resourceType.isindependentpub
no
dcterms.accessRights.openaire
open access
dcterms.isPartOf.issn
2643-1564