CS395T Topics in Quantum and Classical Complexity Theory

Scott Aaronson

UT Austin, Fall 2016

Mondays, 2-5PM, Gates Dell Complex 5.516

This is an advanced graduate course about quantum complexity theory and its relationship to classical complexity theory. What that means is: we'll develop the theory of quantum computation, in a way that's accessible to computer scientists who might not even have seen quantum mechanics before. But we'll focus on a slightly unusual set of topics: ones where progress seems to depend as much on advances in classical complexity theory as it does on quantum advances, or where the whole difficulty is to rule out a classical solution to something that's known to be solvable quantumly, or where one wants to know whether one can solve a quantum problem (such as a circuit lower bound) without having to solve a corresponding classical problem. Likely topics will include:


Course Syllabus

Course Project Information

Barbados Lecture Notes on the Complexity of Quantum States and Transformations (the "textbook" for a large part of the course)

CS395T Canvas page

CS395T Piazza site

Optional Problem Sets

Problem Set 1: Quantum Basics

Problem Set 2: Through BQP