Quantum Hamiltonian Complexity

Abstract

Constraint satisfaction problems are a central pillar of modern computational\ncomplexity theory. This survey provides an introduction to the rapidly growing\nfield of Quantum Hamiltonian Complexity, which includes the study of quantum\nconstraint satisfaction problems. Over the past decade and a half, this field\nhas witnessed fundamental breakthroughs, ranging from the establishment of a\n"Quantum Cook-Levin Theorem" to deep insights into the structure of 1D\nlow-temperature quantum systems via so-called area laws. Our aim here is to\nprovide a computer science-oriented introduction to the subject in order to\nhelp bridge the language barrier between computer scientists and physicists in\nthe field. As such, we include the following in this survey: (1) The\nmotivations and history of the field, (2) a glossary of condensed matter\nphysics terms explained in computer-science friendly language, (3) overviews of\ncentral ideas from condensed matter physics, such as indistinguishable\nparticles, mean field theory, tensor networks, and area laws, and (4) brief\nexpositions of selected computer science-based results in the area. For\nexample, as part of the latter, we provide a novel information theoretic\npresentation of Bravyi's polynomial time algorithm for Quantum 2-SAT.\n