Quantum Hamiltonian Complexity

In quantum computing, a local Hamiltonian is the quantum analogue of a classical constraint satisfaction problem (CSP): it is a collection of local constraints acting on a system of n qubits, as opposed to n bits. As 3-SAT is NP-complete, the local Hamiltonian problem (LHP) is QMA-complete, where QMA is the quantum analogue of the complexity class NP. More than just a quantum analogue of classical CSPs, local Hamiltonians are used to model physical constraints on an n-particle system. Studying the complexity of problems associated with local Hamiltonians, such as the ground state energy or ground state entanglement, is a way to use complexity theory to provide insights into hard probems from physics.
The course will first introduce the local Hamiltonian problem and the class QMA, and we will show the celebrated QMA-completeness result due to Kitaev, which builds on the notion of a "history state" for quantum computations.
Starting from this foundation we will discuss further topics in Hamiltonian complexity, among the following:

*    QMA-hardness of restricted families of local Hamiltonians: quantum 2-SAT, quantum MAXCUT, etc.
*    The complexity of the commuting local Hamiltonian problem
*    Entanglement in ground states of local Hamiltonians: the area law and succinct representations via matrix product states
*    Monogamy of entanglement via de Finetti-type results
*    The quantum PCP conjecture.

For an introduction to Hamiltonian complexity, we can recommend the following survey: https://arxiv.org/pdf/1401.3916. (We will not follow the survey, but it is a good introduction.) For a discussion of the quantum PCP conjecture, which provides motivation for this course, see https://arxiv.org/abs/1309.7495.
In terms of background, it is expected that all students will have some prior exposure to quantum information, having taken a course either in physics or computer science that covers qubits, quantum operations, measurements, and, ideally, quantum circuits. A strong grasp of finite-dimensional linear algebra is recommended. In addition, some introduction to complexity theory, or if not complexity then algorithms, is expected to be able to grasp elementary concepts such as complexity classes, reductions, etc.