Quantum Complexity Theory
CSE 291 / Math 277A

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

Lecture 1 Quantum basics: probability theory vs. quantum theory, unitary matrices, and quantum states scribe


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.

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