Quantum Complexity: A Cryptographic Perspective (CSE 291, 2025 Spring)

Course Information

Location: CSE 4140

Time: Tuesday and Thursday, 2:00 pm - 3:20 pm

Office Hours:  TBD

Grading:  Evaluation is based on 3-4 assignments, and a final project (a written report and maybe a presentation). 

70% homework (you can replace one homework with scribing a class), 30% final project

Course Description

This is a graduate-level course on quantum complexity and quantum cryptography. Some backgrounds on quantum computing are required, but we may provide some extra preliminary classes on the basis, depending on the enrollment. You can also watch the videos on my previous CSE 190 class for more backgrounds.

In this course, we will focus on quantum complexity that are either based on methods that are from the quantum cryptography community or problems that are interesting to cryptographers. Some examples include QMA amplification and its applications to quantum cryptography, quantum random oracle model and various proof methods, hybrid query complexity, monogamy-of-entanglement and its applications, quantum advantage protocols, minimum cryptographic assumptions.

Scribing signup: Link (Please log in using your UCSD email)

Tentative Schedule

A detailed schedule will be continuously updated each week. An outline of the tentative course materials is below: 

1. Introduction to quantum computing: qubits, gates, unitary, measurement (We may extend this part significantly, if necessary!)

Quantum lower bounds

2. Famous quantum algorithms: Grover's algorithm and BBBV lower bound

3. Introduction to quantum random oracle model (QROM); measure-and-reprogram: a lifting lemma

4. A more refined tool for QROM: compressed oracle

5. Witness preserving amplification and non-uniform security

Quantum protocols

6. Proof of quantumness (Yamakawa-Zhandry protocol)

7. BB84 states and monogamy-of-entanglement

8. Subspace/coset states and unclonable cryptography

9. Cryptography without OWFs

Notes for Topic 1 (Background) 

Lecture 1 (Jan 7): A crash course on quantum computing (part 1): syllabus, qubits, measurement 

Lecture 2 (Jan 9): No class

Lecture 3 (Jan 14): A crash course on quantum computing (part 2): multi-qubit system and hidden matching problem

Lecture 4 (Jan 16): A crash course on quantum computing (part 3): gates and circuits, coherent computation, oracle interrogation

Upperbound Lowerbound for Topic 2 (Grover's algorithm and Basic Lower Bound Techniques)

Lecture 5 (Jan 21): Grover's algorithm and BBBV lower bound

Lecture 6 (Jan 23): Cont'd

Scribing Template: [Overleaf Link]

Homework

3-4 assignments will be added. Solutions should be typeset in LaTeX. 

Problemset 1: [Link] Due Jan 31. 

Final Project

TBA

Other Materials

Grad Course (a preliminary version)  by myself

Undergrad Course by myself

Course by Dr. Zhandry

Course by Dr. Ananth

Course by Dr. Vidick

Course videos by Dr. O'Donnell

Book by Nielsen and Chuang: Quantum Computation and Quantum Information