Prerequisites: 6.845 or 2.111
Instructor: Prof. Scott Aaronson (firstname.lastname@example.org)
Schedule: TR2:30-4, room 5-134
This is an advanced graduate course about recent connections between computational complexity and physics, going beyond the fundamental connection established by quantum computing. Topics will include: quantum computing with bosons and fermions (e.g., BosonSampling and FermionSampling);
computational aspects of the black-hole firewall problem and the AdS/CFT correspondence; complexity of quantum states and unitary transformations; universality of gates, cellular automata, and billiard-ball models; and quantum computing with closed timelike curves. A major part of the course is to read a recent paper and give an in-class presentation about it. The course is open to students who have taken a previous course on quantum computation, such as 6.845 or 2.111.