Quantum Complexity Theory
An introduction to quantum complexity: BQP, quantum algorithms, query lower bounds, QMA, QIP and communication complexity, with project ideas.
What can quantum computers fundamentally do, and what are their limits? This introduction to quantum computational complexity theory aims to bring students to the research frontier, without assuming prior knowledge of quantum mechanics. It covers quantum algorithms, query lower bounds, classes such as BQP, QMA and QIP, quantum advice and communication complexity, and it ends with student projects on current literature.
What You Will Achieve
- Explain how BQP relates to classical complexity classes
- Analyze the Deutsch-Jozsa, Simon’s, Shor’s and Grover’s algorithms
- Prove quantum query complexity lower bounds
- Survey a topic in quantum complexity from the research literature
Program Overview
Quantum Basics and Algorithms
The first lectures set up the model and its main algorithms.
- Quantum circuits
- BQP and classical friends
- Shor’s algorithm and the hidden subgroup problem
- Grover’s algorithm and BBBV
Query Lower Bounds
The next group of lectures shows what quantum algorithms cannot do.
- Quantum query complexity
- The collision problem
The Zoo of Complexity Classes
Later lectures survey further classes and related questions.
- QMA and QIP
- PostBQP and BQP/qpoly
- Closed timelike curves
- Quantum communication complexity
Course Completion
Job Outlook
This material prepares students for research in quantum computing, quantum information and theoretical computer science.
Good for: Theory students with a prior course in computational complexity or quantum information who want to reach current research in the field.
Keep in mind: The lecture notes were taken by students from a 2008 offering, and the syllabus warns of errors and omissions. There is no official textbook, and no problem set solutions are listed.
Bottom line: A route to the research frontier, from a subject where no single book covers the material.
Frequently Asked Questions
How much quantum mechanics does the class teach?
The first lectures cover quantum basics and quantum circuits, since the syllabus assumes no prior knowledge of quantum mechanics. Its focus after that is complexity, not physics.
What did the course projects involve?
Either a survey of a topic in the literature or original research, with a proposal, a 10-minute presentation and a report of up to five pages. Example topics are listed.
Which books does the syllabus suggest?
There is no official textbook. Helpful books include Nielsen and Chuang, Mermin, Arora and Barak, and Sipser, along with online notes by John Watrous and Quantum Computing Since Democritus.



There are no reviews yet.