Announcements

Course Description

This class is an MIT graduate course on quantum complexity theory, covering a broad range of topics of current interest. For last year’s Harvard-MIT joint edition of this class, which focused on the exciting area of Hamiltonian complexity, see here.

Course Information

Instructor: Anand Natarajan (anandn at mit dot edu).

Teaching assistant: Tina Zhang (tinaz at mit dot edu).

Space-time coördinates: Tuesdays & Thursdays 11:00 a.m. to 12:30 p.m., 36-153.

Office hours: Fridays 4-5pm in 32-624, starting September 18, or by appointment.

Piazza: Available here.

Lecture schedule and readings

(This schedule is provisional and subject to change.)

Handwritten notes are available here, currently up to Lecture 3.

Date Topic Additional notes or readings
9/10 BQP basics  
9/15 Classical upper bounds on BQP, and the BBBV lower bound  
9/17 The polynomial and compressed oracle methods Yassine Hamoudi’s query complexity notes, Compressed oracle notes
9/22 Error correction bootcamp  
9/24 The Yamakawa-Zhandry problem and Regev’s reduction  
9/29 QMA: basics and Marriott-Watrous amplification  
10/1 Local Hamiltonians and the Feynman-Kitaev construction  
10/6 Oracle separations between QMA and QCMA  
10/8 QMA(2) and QIP  
10/13 No class (Monday schedule)  
10/15 Introduction to quantum PCP  
10/20 Monogamy of entanglement and the Brandão-Harrow theorem  
10/22 Gap amplification and the detectability lemma  
10/27 PCPs and fault tolerance  
10/29 Gibbs states  
11/3 Consistency of local density matrices  
11/5 QSZK  
11/10 BQP and the polynomial hierarchy  
11/12 State and unitary synthesis  
11/17 Pseudorandom states and unitaries  
11/19 Interactive proofs for BQP  
11/24 Self-testing and multi-prover interactive proofs  
11/26 No class (Thanksgiving)  
12/1 The cryptographic leash  
12/3 TBD  
12/8 Final project presentations  
12/10 FInal project presentations