Lecture 1 : Dorit Aharonov, The Hebrew University of Jerusalem

Problem Set

Supplementary reading for this course:
Survey of the circuit-to-Hamiltonian construction and Kitaev's proof that local Hamiltonian is QMA complete:
Dorit Aharonov, Tomer Naveh, "Quantum NP - A Survey" (
More conceptual explanations of the above in Sections 1-3 of Dorit Aharonov, Itai Arad and Thomas Vidick, "The Quantum PCP Conjecture" (
(section 1.3 explains the connection between QMA hardness and the time of relaxation to the Gibbs state or ground state. Section 3 explains the difficulties in Kitaev's proof of QMA completeness of the local Hamiltonian problem)
Long list of QMA-complete problems:
Adam D. Bookatz, "QMA-complete problems" (

More specialized material:

Hardness of physically motivated Hamiltonians (2D Hubbard and 2D Heisenberg):
Norbert Schuch and Frank Verstraete, "Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory" (
QMA completeness of the Consistency of density matrices problem:
Yi-Kai Liu, "Consistency of Local Density Matrices is QMA-complete" (
1D translationaly invariant hamiltonians are hard:
Daniel Gottesman and Sandy Irani, "The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems" (


Focus Lecture 1 : Adam Bouland, MIT