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**

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

**Optional Problem Sets**