6.845 Quantum Complexity Theory
Fall 2014
Instructor: Scott Aaronson
TA: Adam Michael Bouland
Lecture:
W2-5
(34-301)
TA Office Hours: W10:30-12
(32-G630)
Information:
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 required. 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)
Announcements
Final project reports
Thank you for the excellent project presentations today!
As a reminder the final project report is due tomorrow (Thursday December 11) by 11:59PM. Please turn in the projects online via Stellar. We are grading the reports on Friday so the deadline will be strictly enforced.
Thanks and good luck writing up!
Best,
Adam
Announced on 10 December 2014 5:45 p.m. by Adam Michael Bouland
Project presentations - email slides by 11:30AM Wednesday
Our final project presentations will be this Wednesday from 2PM-5PM in 34-301. If you would like to use beamer/powerpoint for your presentation, please let Scott and me know by Tuesday at 5PM, and most importantly email Scott and me your final slides by Wednesday at *11:30AM* sharp. We will load everyone's slides on a single laptop. You're also welcome to give your talk on the blackboard! As a reminder all presentations will be limited to 5 minutes with 1 minute for questions between talks.
Good luck preparing your presentations, and see you Wednesday!
Best,
Adam
Announced on 08 December 2014 5:04 p.m. by Adam Michael Bouland
Class on Wednesday
Hi everyone,Just a quick note to let you know that there *will* be class this coming Wednesday. Of course, if your Thanksgiving plans prevent you from attending, I'll fully understand. But if you *are* around, then I wouldn't want you to miss the chance to learn about Holevo's theorem, superdense coding, quantum 1-way communication complexity, and stabilizer circuits.
Best,
Scott
Announced on 23 November 2014 7:30 p.m. by Scott Aaronson
Problem 8(b) on pset3
Hi everyone,Problem 8(b) on the pset asks you to give an O(N^{4/9})-query quantum algorithm for finding 3-way collisions in a 3-to-1 functions. While such an algorithm exists, it's actually possible to do even better, and get O(N^{3/7}). So if you get O(N^{3/7}), that doesn't mean that you made a mistake---on the contrary, extra credit will be awarded for that. (And if you can *beat* N^{3/7} -- something that I don't even know to be possible -- you get EXTRA extra credit! :-) )
Best,
Scott
Announced on 22 October 2014 11:05 a.m. by Scott Aaronson
Office hours tomorrow
Best,
Adam
Announced on 21 October 2014 3:37 p.m. by Adam Michael Bouland
