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.

Problem sets

Problem set 1. Due 11/3/26.

Lecture schedule and readings

(This schedule is provisional and subject to change.)

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

Lecture number Date Topic Additional notes or readings
1 9/10 BQP basics  
2 9/15 Classical upper bounds on BQP, and the BBBV lower bound  
3 9/17 The polynomial and compressed oracle methods Yassine Hamoudi’s query complexity notes, Compressed oracle notes
4 9/22 Error correction bootcamp John Wright’s course, Essential Coding Theory, Chinmay Nirkhe’s Simons talk
5 9/24 The Yamakawa-Zhandry problem and Regev’s reduction Mark Zhandry’s talk, the YZ paper, Fermi Ma’s notes
6 9/29 QMA: basics and Marriott-Watrous amplification Oded Regev’s notes
7 10/1 Local Hamiltonians and the Feynman-Kitaev construction Scribe notes from last year
8 10/6 Oracle separations between QMA and QCMA Chinmay Nirkhe’s short and long talks
9 10/8 QMA(2) A survey by Jeronimo, Leigh, and Wu
  10/13 No class (Monday schedule)  
10 10/15 Introduction to quantum PCP A survey by Aharonov, Arad, and Vidick, the Eldar-Harrow NLTS paper
11 10/20 Monogamy of entanglement and the Brandão-Harrow theorem Lecture notes from last year
12 10/22 Gap amplification and the detectability lemma (guest lecture by Tina Zhang) Quynh Nguyen’s talk
13 10/27 PCPs and fault tolerance Anshu-Breuckmann-Nguyen’s paper, Louis Golowich’s talk
14 10/29 Gibbs states (guest lecture by Alexander Zlokapa)  
15 11/3 Consistency of local density matrices Last year’s lecture, Broadbent and Grilo’s paper
16 11/5 QIP Vidick and Watrous’s survey on quantum proofs
17 11/10 BQP and the polynomial hierarchy Aaronson’s 2009 paper, Raz and Tal’s paper, Barak and Błasiok’s blogpost
18 11/12 State and unitary synthesis  
19 11/17 Pseudorandom states and unitaries  
20 11/19 Interactive proofs for BQP  
21 11/24 Self-testing and multi-prover interactive proofs  
  11/26 No class (Thanksgiving)  
22 12/1 The cryptographic leash  
23 12/3 TBD  
24 12/8 Final project presentations  
25 12/10 FInal project presentations