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