CS 294: Quantum Complexity Theory

• Aug 25: Course overview; definition of BQP; BQP ⊆ PSPACE
  Quantum Complexity Theory by Ethan Bernstein and Umesh Vazirani
  Lecture 24 of Ryan O'Donnell's quantum computing course: quantum complexity theory
• Aug 30: BQP ⊆ PP; introduction to oracles
  Worlds to Die Harder For: Open Oracle Questions for the 21st Century by Lance Fortnow
  
• Sept 1: Oracle separation of BQP with P
• Sept 6: Oracle separation of BQP with BPP
• Sept 8: Oracle separation of BQP and PH, Part I
  BQP and the Polynomial Hierarchy by Scott Aaronson
  
• Sept 13: Oracle separation of BQP and PH, Part II
  Oracle separation of BQP and PH by Ran Raz and Avishay Tal
  Oracle Separation of BQP and the Polynomial Hierarchy video of a talk by Avishay Tal
• Sept 15: Quantum query lower bounds via the polynomial method
  Lecture 11 of Ryan O'Donnell's and my quantum computing course: Quantum Query Lower Bounds Using Polynomials
• Sept 20: Quantum query lower bounds via the adversary method
  Lecture 13 of Ryan O'Donnell's and my quantum computing course: Lower Bounds using the Adversary Method
  Applications of the Adversary Method in Quantum Query Algorithms, Aleksandrs Belovs' Ph.D. thesis
• Sept 22: Structure in quantum speed-ups
  The Need for Structure in Quantum Speedups by Scott Aaronson and Andris Ambainis
  How Much Structure Is Needed for Huge Quantum Speedups? by Scott Aaronson
• Sept 27: Random oracle separation of BPP-Search and BQP-Search
  Verifiable Quantum Advantage without Structure by Yamakawa and Zhandry

• BQP
  Basic properties and relations with other classes
  Oracle separations versus classical classes
  The need for structure. Aaronson-Ambainis and Yamakawa-Zhandry
• QMA
  QMA-completeness of the local Hamiltonian problem
  Friends of QMA: QCMA and QMA(2)
  The Quantum PCP conjecture
• Interactive proofs
  QIP = PSPACE
  The power of multiple provers: MIP* = RE
  Classical verification of quantum computation
• Near-term quantum complexity
  Short-depth circuits: Bene Watts-Kothari-Schaeffer-Tal
  Quantum advantage with random quantum circuits