6.845
Quantum Complexity Theory
Fall 2010
Topics
- Quantum basics
- More quantum basics
- Quantum circuits
- BQP and classical friends
- Quantum algorithms: Deutsch-Jozsa
- Quantum algorithms: Simon’s algorithm
- Shor’s algorithm and the hidden subgroup problem
- Hidden subgroup problem and Grover’s algorithm
- Grover’s algorithm and BBBV
- Quantum query complexity lower bounds
- More quantum query complexity
- Query complexity and the collision problem
- The collision problem
- BQP vs. PH and QMA
- QMA
- QMA and variants
- QIP
- PostBQP
- Closed timelike curves
- BQP/qpoly
- Quantum communication complexity
- More quantum communication complexity
- Classical simulation
- Grab bag
- Student project presentations
- Student project presentations (cont.)
Readings
- 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.
- Sipser, Michael. Introduction to the Theory of Computation . 2nd ed. Course Technology, 2005. ISBN: 9780534950972.
- Bernstein, Ethan, and Umesh Vazirani. “Quantum Complexity Theory.” SIAM Journal on Computing 26 (1997): 1411-1473.
- Bennett, Charles, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. “Strengths and Weaknesses of Quantum Computing.” SIAM Journal on Computing 26 (1997): 1510-1523.
- Kitaev, Alexei, and John Watrous. “Parallelization, Amplification, and Exponential Time Simulation of Quantum Interactive Proof Systems.” Proceedings of the 32nd ACM Symposium on Theory of Computing (2000): 608-617.
Sources
- Course catalogue ↗Historical OpenCourseWare
- MIT OCW calendar ↗
- MIT OCW readings ↗
- MIT OCW syllabus ↗
- Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.