Quantum Complexity Theory
CSE 291 / Math 277A - Fall 2022

Place and Time:CSE 4140, TTh 3:30pm-4:50pm
Instructor:Daniel Grier (dgrier@ucsd.edu)
TA:Sihan Liu (sil046@ucsd.edu)
Course materials:Canvas

Daniel's office hours:Thursday after class and by appointment in CSE 4218
Sihan's office hours:Tuesday from 2pm-3pm in CSE 4232


The scribe notes were initially prepared by students in the class, but were then modified by me. You can assume any errors are my own. Find an error? Feel free to let me know!
Lecture 1 Quantum basics: probability theory vs. quantum theory, unitary matrices, and quantum states scribe
notes
Lecture 2 More quantum basics: No-cloning, mixed states, partial trace, and purification scribe
notes
Lecture 3 Quantum circuits, universality scribe
notes
Lecture 4 More quantum circuits, Nobel prizes, and the CHSH game scribe
notes
Lecture 5 Classical complexity classes, relationships, and BQP scribe
notes
Lecture 6 BQP vs. classical complexity classes and Deutsch's algorithm scribe
notes
Lecture 7 Quantum query algorithms continued: Deutsch-Jozsa, Berstein-Vazirani, and Simon's problem scribe
notes
Lecture 8 Maximal query separations and the forrelation problem scribe
notes
Lecture 9 Grover's algorithm and the BBBV lower bound scribe
notes
Lecture 10 More quantum query lower bounds: the polynomial method and Adversary bound scribe
notes
Lecture 11 Clifford circuits, the Pauli group, and the Gottesman-Knill Theorem scribe
notes
Lecture 12 Stabilizer groups continued, constant-depth circuit classes, and the GHZ game scribe
notes
Lecture 13 GHZ game continued, Bravyi-Gosset-König separation between constant-depth quantum and classical circuits scribe
notes
Lecture 14 NC/AC Hierarchy, hardness of simulating interactive protocols with low-depth Clifford circuits scribe
notes

Overview

This is a graduate-level course that will use tools from complexity theory to understand the fundamental differences between quantum and classical computers. After an introduction to the basics of quantum computation, the course will explore several settings in which quantum computers provably outperform their classical counterparts. This will take us to the forefront of quantum computing research, where we'll look at the complexity-theoretic foundations of recent quantum computing experiments.

Prerequisites: A previous course in complexity theory (CSE 200 or equivalent) is highly recommended. No prerequisite knowledge of physics or quantum computation is required. That said, this is an advanced research-level course and is not intended as an introduction to quantum computation and information.

Topics
  • Quantum foundations: states, operations, measurements
  • Quantum algorithms: Deutsch-Jozsa, Simon, Grover
  • Lower bounds from query complexity: polynomial method, adversary method
  • Classical vs. quantum complexity classes: P vs. BQP, NP vs. QMA
  • Quantum satisfiability and the local Hamiltonian problem
  • Classical simulation: Clifford circuits, tensor networks
  • Near-term computational advantage: Shallow circuits, BosonSampling
Grading
  • Project (55%): The majority of the course grade will come from the final research project, which consists of a written report and a presentation. The project will be an in-depth study of a topic related to quantum complexity theory.
  • Homework (20%): There will be 2-3 homework assignments throughout the course.
  • Scribing (15%): You will be asked to scribe one lecture by carefully writing notes during class and TeX'ing up the final results. A template will be provided for this.
  • Participation (10%): Students should actively engage with the material in class and/or office hours.
Useful Resources