Quantum complexity theory

Lectures: 2 sessions / week, 1.5 hours / session

This course is an 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.

Grades will be determined roughly as follows:

All students are expected to complete a course project. This will involve submitting a written report, as well as giving a 10-minute presentation toward the end of class. The projects can be either original research or literature surveys on some topic in quantum complexity theory (or related areas of quantum information science). Survey projects should be individual, while research projects can be done either individually or in teams of two. Many possibilities for projects will be discussed as the course progresses. Solving a significant open problem pretty much guarantees an A in the course.

There will be 4-5 problem sets. Problem sets will be due about two weeks after being assigned. Students are welcome to collaborate on problem sets; however, if they do so, they must list the names of collaborators.

Notes (taken by the students) from a previous offering of the course are available in the Lecture Notes section. We will not follow the 2008 notes exactly this semester, but will follow them for perhaps 70-80% of the course. Since no book exists that covers much of the material, the notes should be an extremely useful resource. However, please be warned that the notes haven't been carefully proofread and contain some errors and omissions.

The course has no official textbook. However, students may find the following books helpful:

Nielsen, Michael, and Issac Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2011. ISBN: 9781107002173.

Mermin, David. Quantum Computer Science: An Introduction. Cambridge University Press, 2007. ISBN: 9780521876582.

Arora, Sanjeev, and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ISBN: 9780521424264.

Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Course Technology, 2005. ISBN: 9780534950972.

In addition, students might benefit from the following online resources:

Watrous, John. "Quantum Computational Complexity."

Quantum Computing Since Democritus: Lecture Notes

No prior knowledge of quantum mechanics is assumed. Open to students who have taken a previous course on computational complexity theory (such as 6.045 or 6.840), or a previous course on quantum computing and information (such as 18.435).

"Who Ordered Quantum Mechanics?"
Classical Complexity Theory Crash Course
Defining BQP: Bounded-Error Quantum Polynomial-Time
Universal Sets of Quantum Gates
Basic Closure Properties of BQP
How BQP Relates to Classical Complexity Classes: P, BPP, PP, P#P, PSPACE
Coping with Imprecision
Basic Quantum Algorithms: Deutsch-Jozsa, Bernstein-Vazirani, Shor, Grover
The Hidden Subgroup Framework

II. The Quantum Black-Box Model

Defining and Motivating the Quantum Black-Box Model
Oracle Separations: The Baker-Gill-Solovay Paradigm
Oracle Separation of BQP from BPP
Oracle Separation of NP from BQP: The BBBV Hybrid Argument
The Polynomial Method for Quantum Lower Bounds
Quantum/Classical Relation for Total Boolean Functions
Ambainis's Adversary Method, with Application to Game-Tree Search
Quantum Lower Bound for the Collision Problem

III. The Zoo of Quantum Complexity Classes

BQPSPACE: Quantum Polynomial Space
QMA: Quantum Merlin-Arthur (and QMA-completeness)
QCMA: Quantum Classical Merlin-Arthur
QIP: Quantum Interactive Proofs
BQP/qpoly: Quantum Computing with Quantum Advice
PostBQP: Quantum Computing with Postselection

IV. Other Topics

Quantum Communication Complexity: Separations and Lower Bounds
Dense Quantum Coding and Learnability of Quantum States
The Stabilizer Formalism
Alternative Quantum Computing Paradigms: Adiabatic, Cluster States, ...
Quantum Computing with Noninteracting Bosons and Fermions
Hypothetical Models Beyond Quantum Computing: Nonlinear QM, Closed Timelike Curves, ...
More depending on student interest

V. Student Project Presentations

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare