6.845  Quantum Complexity Theory

[Syllabus]

[6.845 Piazza site]

Introduction to quantum computational complexity theory, the study of the fundamental capabilities and limitations of quantum computers. Topics include complexity classes, lower bounds, communication complexity, proofs, advice, and interactive proof systems in the quantum world. The objective is to bring students to the research frontier.

Prerequisites: No prior knowledge of quantum mechanics is assumed. Aimed at students who have taken a previous course in computational complexity theory (such as 6.840), OR quantum computing and information (such as 2.111 or 18.435).

Units: 3-0-9. Qualifies as a Theoretical CS Engineering Concentration subject.

Requirements: 3-5 psets and a reading or research project.

Instructor: S. Aaronson (aaronson@csail.mit.edu, www.scottaaronson.com, 32-G638)