Syllabus & Reading

Syllabus

The most recent version of the syllabus can be found here (updated 13.10.2020).

Reading

• All lecture notes compiled into a single document: Lecture notes.

• October 26: Classical complexity theory review (lecture notes, video).
• November 2: Quantum computation review (lecture notes, video).
• November 9: Bounded error quantum polynomial time (BQP) (lecture notes, video).
• November 16: Linear systems of equations and a BQP-complete problem (lecture notes, video).
• November 23: Quantum Merlin Arthur (QMA) and strong error reduction (lecture notes, video).
• November 30: The Quantum Cook-Levin Theorem (lecture notes, video).
• December 7: Quantum-Classical Merlin Arthur (QCMA) and Ground State Connectivity (lecture notes, video).
• December 14, 21: Quantum Interactive Proofs (QIP), semidefinite programs, and multiplicative weights (lecture notes, video (part 1),video (part 2)).
• January 11: Boson Sampling (lecture notes,video).
• January 18: BQP versus the Polynomial Hierarchy (lecture notes, video).