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)
A detailed schedule will be continuously updated each week. An outline of the tentative course materials is below:
Introduction to quantum computing: qubits, gates, unitary, measurement (We may extend this part significantly, if necessary!)
Quantum lower bounds
Famous quantum algorithms: Grover's algorithm and BBBV lower bound
Introduction to quantum random oracle model (QROM); measure-and-reprogram: a lifting lemma
A more refined tool for QROM: compressed oracle
Witness preserving amplification and non-uniform security
Quantum protocols
Proof of quantumness (Yamakawa-Zhandry protocol)
BB84 states and monogamy-of-entanglement
Subspace/coset states and unclonable cryptography
Cryptography without OWFs
Notes + Book (Nielsen and Chuang)
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
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
Lecture 7 (Jan 28): Cont'd and the beginning of hash functions/random oracles, classical lazy sampling method
Notes (Classical Lifting) Notes (Quantum Lifting) Paper1 Paper2
Notes (Compressed Oracle) Paper1
Topic 3 (Advanced Tools for Lower Bounds, Measure-and-Reprogram, and Compressed Oracles)
Lecture 8 (Jan 30): Measure-and-reprogram as a lifting lemma
Lecture 9 (Feb 4): Quantum measure-and-reprogram, lifting lemma cont'd
Lecture 10 (Feb 6): A gentle intro to compressed oracle (the oracle purification technique)
Topic 4 (Exponential Quantum Advantages in the Random Oracle Model)
Lecture 11 (Feb 11): Compressed Oracle Cont'd, AA conjecture
Lecture 12 (Feb 13): Yamakawa-Zhandry protocol
Notes Paper1(Classical) Paper2(Quantum)
Topic 5 (Non-uniform Algorithms and Lower Bounds)
Lecture 13 (Feb 18): Yamakawa-Zhandry protocol Cont'd, Hellman's algorithm (Rawinbow Table)
Lecture 14 (Feb 20): Quantum and classical non-uniform lower bounds
Lecture 15 (Feb 25): No class due to QIP
Lecture 16 (Feb 27): Homework discussions and recap of Part 1 + Quantum Goldreich-Levin
Topic 6 (Cryptography Based on Quantum Information)
Lecture 17 (Mar 4): Unclonability, state discrimination and Wiesner's states (BB84 states)
Lecture 18 (Mar 6): Private-key quantum money, attacks on Wiesner's quantum money
Lecture 19 (Mar 11): subspace states and public key quantum money
Lecture 20 (Mar 13): quantum copy-protection
Scribing Template: [Overleaf Link]
[Link] I will keep updating it, whenever I have some new ideas.
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