This course develops the basics of quantum complexity theory by focusing on the notion of a "quantum proof."
Our main focus (approx. 6 lectures) will be the study of the complexity class QMA (or, "quantum NP") and its complete problem, the local Hamiltonian problem. We will define the class, show basic structural properties (error reduction, etc.), introduce the local Hamiltonian problem and show that it is a complete problem.
We will then move on to study quantum interactive proofs. We will study the class QIP, for quantum single-prover interactive proofs, give different characterizations of it and show the famous result QIP=PSPACE. This will take approx. 3 lectures. 3 additional lectures will be devoted to multiprover interactive proofs (the classes MIP* and QMIP*) and their connection with the study of quantum entanglement and nonlocal games.
The remaining 2 lectures will be devoted to topics of recent interest, such as the classes QCMA (classical proof, quantum verifier) or QMA(2) (two unentangled quantum proofs).