Term: Semester A
Lectures: Tuesday 11:15-13:00, Ziskind Room 155
Instructor: Thomas Vidick
Office Hour: Sundays 16:00-17:00, Ziskind Room 202
Course description
This course develops the basics of quantum complexity theory by focusing on the notion of a "quantum proof." This starts with the definition of the complexity class QMA (or, "quantum NP") and its complete problem, the local Hamiltonian problem. We will introduce various complete problems and show basic structural properties (error reduction, etc.) of QMA, contrasting them to the analogue property for NP (or MA). We will also look at interesting variants of QMA such as Zero-knowledge proofs, QMA(2) (two non-entangled quantum proofs), and QCMA (classical proof, quantum verifier).
We will then move on to study quantum interactive proofs. Our main focus will be on the class QIP, for quantum single-prover interactive proofs. Here again we will study important structural properties, such as parallelization of protocols to 3 rounds and parallel repetition of protocols. We will prove the famous result QIP=PSPACE, which goes through the use of semidefinite programming and fast parallel solvers for them based on the matrix multiplicative weights update method.
Finally, time permitting we will introduce different models of quantum multiprover interactive proofs (the classes MIP* and QMIP*) and connect them to the study of quantum entanglement and nonlocal games.
Prerequisites
We will assume familiarity with the basics of quantum computing, e.g. qubits and the quantum circuit model. In addition it is preferable, though not required, that the student has some familiarity with the basics of complexity theory, such as the classes NP and IP. We do not expect knowledge of advanced complexity theory such as IP=PSPACE.
Evaluation & workload
Attendance to lecture is required when possible. The workload is divided between reading & digestion of lecture and biweekly problem sets.
Indicative schedule of lectures
- Lecture 1 (12/12): Introduction. The class QMA. Some problems in QMA.
Sections from the book covered: 2.1, 2.3, 3.1, first page of 3.3.
- Lecture 2 (19/12): Error reduction for QMA: in parallel and sequential. See Section 3.2 in the book. For Jordan's lemma (and an analysis of "in-place" error reduction close to the one done in class), see these notes.
- Homework 1: Problems, Solutions
- Lecture 3 (26/12): The local Hamiltonian problem. We covered the definition, some examples, containment in QMA, and the start of QMA-hardness.
The LH problem is covered at a high level in Section 3.3.1 of the book. A more technical discussion, roughly at the level covered in class, is in section 14.2 and 14.3 of the notes by de Wolf. Finally, for anyone interested in going further, a good discussion of the relevance of the local Hamiltonian problem for quantum complexity theory is in this survey.
- Lecture 4 (2/01): The Kitaev clock construction. The class QMA(2)
For the clock construction, see the references above. For the class QMA(2), see Section 3.4.3 of the book. For more on the protocol that we discussed (for 3COL), see this paper.
- Lecture 5 (9/01): QIP: quantum interactive proofs. We discussed the formalism for interactive games, worked through an example, and defined QIP and stated basic properties. In the book, this corresponds to Section 4.1. We also reviewed basic facts about the fidelity, and I encourage you to go over Section 2.2.4 in the book.
- Lecture 6 (14/01): Parallelization of QIPs to 3 messages. Semidefinite programming formulation of QIP and error reduction.
For parallelization, we followed Section 4.2. in the book closely. For error reduction in parallel, see Section 4.3, which we also followed closely except that we did not explicitly write down the dual semidefinite program.
To gain some intuition about semidefinite programs, Chapter 3 in Lovasz' notes available here is only 5 pages and quite clear. (The previous chapter has background on linear programming, which may help if you do not have it.) Some notes by Watrous have the advantage of using notation consistent with the book; but they are a bit more technical than Lovasz'.
- Homework 2: Problems, Solutions
- Lecture 7 (23/01): QIP = PSPACE. We followed the book quite closely, see Section 4.4.
- Lecture 8 : (30/01): Zero-knowledge proofs. We covered the general definition (see Section 5.1 in the book), but not yet the "honest verifier" one (Section 5.1.2). We saw the general rewinding lemma (Section 5.2.1), with a slightly different proof than stated in the book, and the application to graph isomorphism (Section 5.2.2).
- Homework 3: Problems, Solutions
- Lecture 9 : (06/02): Zero-knowledge, cont'd. We continued following the book closely: the definition of the close quantum states problem in Section 5.3.1, its inclusion in QSZK in Section 5.3.3 (on which most of the lecture was spent), and finally the definition of honest-verifier zero knowledge (HVQSZK), the reduction to close images from Section 5.3.2 and the corollary QSZK=HVQSZK.
- Homework 4: Problems.
- Lecture 10 : (20/02): Quantum multiprover interactive proofs: MIP*, QMIP and QMIP*. We covered the material in Sections 6.1 and 6.2.1 in the book.
- Lecture 11 : (25/02): Quantum multiprover interactive proofs: XOR games. We covered Section 6.2.3 in the book, as well as Section 2 in these notes. For more on XOR games, I recommend this paper.
- Homework 5: Problems, Solutions.
Resources
We will follow (parts of) the Quantum Proofs book. We will occasionally discuss more recent material, in which case I will provide specific pointers to the relevant literature.