Complexity

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" (https://arxiv.org/abs/quant-ph/0210077)
More conceptual explanations of the above in Sections 1-3 of Dorit Aharonov, Itai Arad and Thomas Vidick, "The Quantum PCP Conjecture" (http://arxiv.org/abs/1309.7495)
(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" (https://arxiv.org/abs/1212.6312)

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" (http://arxiv.org/abs/0712.0483)
QMA completeness of the Consistency of density matrices problem:
Yi-Kai Liu, "Consistency of Local Density Matrices is QMA-complete" (https://arxiv.org/abs/quant-ph/0604166)
1D translationaly invariant hamiltonians are hard:
Daniel Gottesman and Sandy Irani, "The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems" (https://arxiv.org/abs/0905.2419


 


Focus Lecture 1 : Adam Bouland, MIT

FOCUS LECTURE 2 : ADAM BOULAND, MIT