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

Place and Time:WLH 2207, TTh 3:30pm-4:50pm
Instructor:Daniel Grier (dgrier@ucsd.edu)
TA:Shinjini Halder (shhalder@ucsd.edu)
Resources:Canvas, Gradescope, Piazza

Daniel's office hours:Thursday after class and by appointment in CSE 4218
Shinjini's office hours:Wednesday from 12pm-1pm in CSE B240A


Assignments

These lecture notes are intended to be a comprehensive reflection of the course material. They will be updated throughout the quarter (last updated: 12/9/24). When possible, I have also included links below to other resources for specific topics.
Lecture 1 Foundations of quantum mechanics pg 1-5
Lecture 2 Tensor products, partial measurements, Dirac notation pg 1-8, pg 6-8
Lecture 3 Quantum circuits pg 2-5
Lecture 4 The complexity class BQP pg 1-4
Lecture 5 BQP vs. PSPACE, query algorithms pg 5-6, pg 3-6
Lecture 6 Deutsch-Jozsa, Berstein-Vazirani, and Simon's Problem pg 3-6, pg 1-5
Lecture 7 Grover's algorithm and the BBBV lower bound pg 1-6, pg 1-5
Lecture 8 The polynomial method pg 90-94
Lecture 9 Clifford gates, Gottesman-Knill theorem pg 48-55
Lecture 10 Stabilizer review, parity-L pg 55-57
Lecture 11 Low-depth circuit classes, GHZ game pg 56-61
Lecture 12 Separating NC^0 from QNC^0 with a cat state pg 58-66
Lecture 13 Separating NC^0 from QNC^0 pg 65-71
Lecture 14 Measurement-based quantum computation pg 71-74
Lecture 15 NC^1-hardness of interactive shallow Clifford circuits pg 79-84
Lecture 16 Classically sampling quantum circuits implies PH collapse pg 84-92
Lecture 17 Hardness of sampling with additive error TBD
Lecture 18 Verification of Random Circuit Sampling TBD
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
Evaluation
  • Homework (55%): There will be 5-6 homework assignments throughout the course.
  • Project (20%): The project consists of a written report/survey of a topic related to quantum complexity theory. Attempts at novel research are encouraged but not required.
  • Peer Grading (15%): Each student will be required to help grade at least one homework assignment during the quarter.
  • Participation (10%): Participation is based entirely on Gradescope quizzes given during class. The quizzes are graded for completion rather than correctness. There will be roughly 1 quiz per week, and you are allowed to miss 3 quizzes without penalty.
Accommodations
Students requesting accommodations for this course due to a disability must provide a current Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities. Students are required to discuss accommodation arrangements with instructors and OSD liaisons in the department in advance of any exams or assignments.
Useful Resources