Quantum Hamiltonian Complexity

Understand

Constraint satisfaction problems are a central pillar of modern computational complexity theory.

• This survey provides an introduction to the rapidly growing field of Quantum Hamiltonian Complexity, which includes the study of quantum constraint satisfaction problems.
• Over the past decade and a half, this field has witnessed fundamental breakthroughs, ranging from the establishment of a "Quantum Cook-Levin Theorem" to deep insights into the structure of 1D low-temperature quantum systems via so-called area laws.
• Our aim here is to provide a computer science-oriented introduction to the subject in order to help bridge the language barrier between computer scientists and physicists in the field.