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

Place and Time:PCYNH 120, TTh 2:00pm-3:20pm
Instructor:Daniel Grier (dgrier@ucsd.edu)
Resources:Canvas, Piazza

Daniel's office hours:Thursday after class and by appointment in CSE 4218
Jacks's office hours:Friday 11-12pm in CSE BA250

Assignments

These lecture notes are intended to be a comprehensive reflection of the course material. They will be updated throughout the quarter (last updated: 9/24/25).
Lecture 1 Foundations of quantum mechanics 1.1-1.2
Lecture 2 Multi-qubit states, tensor products 1.2
Lecture 3 Partial measurements, Dirac notation, inner products 1.3
Lecture 4 Quantum circuits, Deutsch's problem 2.1-2.2
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 will go far beyond a simple 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 6 homework assignments throughout the course.
  • Project (30%): Written report of a topic related to quantum complexity theory.
  • Peer Grading (15%): Each student will be required to help grade one homework assignment.
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