Course Identification

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).

You will learn the analogue of the theory of NP-completeness for quantum computation, and further study quantum interactive proof systems and their peculiar properties. These topics are central in quantum complexity theory, with applications to areas such as delegated computation, testing, and others.

The class will, for the most part, follow the survey on "Quantum Proofs" available here: https://arxiv.org/abs/1610.01664.

For additional background on quantum complexity theory, we recommend the book "Classical and Quantum Computation" by Kitaev, Shen and Vyalyi, as well as the survey on "Quantum Computational Complexity" by Watrous (https://arxiv.org/abs/0804.3401).