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:
- The basic framework of qubits, quantum gates, and quantum circuits
- BQP and its relationship with classical complexity classes
- The complexity of quantum states and unitary transformations; the Unitary Synthesis Problem
- Quantum versus classical proofs and advice
- Quantum money
- Applications of quantum complexity to AdS/CFT and the black-hole information problem
- Quantum versus classical query complexity; recent separations; maximum possible separations
- BosonSampling and the complexity of the permanent
- BQP versus the polynomial hierarchy
Resources
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