50% homeworks (you can scribe to replace some homework), 50% final project
This is a graduate-level course but no prior knowledge of quantum mechanics or quantum computation is needed. In this course, we will together explore how quantum computers significantly change the landscape of modern cryptography but also how cryptography helps find and forward many important concepts in quantum computing. These include but are not limited to breaking the famous RSA cryptosystem, proof of quantumness, quantum money, position verification, pseudo-entanglement and pseudo-random states (and connections of AdS/CFT and the wormhole growth paradox), and many others.
A detailed schedule will be continuously updated each week. An outline of the tentative course materials is below:
introduction + single-qubit states, multi-qubit states, measurement, recap of linear algebra over C
quantum operations: quantum gates, general measurements and quantum algorithms
Quantum Fourier Transform (QFT) and fast integer factorization (Shor's algorithm)
Grover's algorithm and quantum collision finding (BHT algorithm)
BB84 quantum states, monogamy-of-entanglement: secret-key quantum money
subspace states: public-key quantum money and quantum copy-protection
trap-door claw-free functions (TCFs) and proof of quantumness
position verification from TCFs
pseudo-random quantum states and pseudo-entanglement
Part 1: Basics
[Notes] for part 1
Lecture 0 (Jan 6): Welcome! + Introduction to quantum cryptography + single-qubit quantum states
Lecture 1 (Jan 8): Multi-qubit states, recap on linear alegebra, hidden matching problem
Lecture 2 (Jan 13): Hidden matching problem, tensor [Link]
Lecture 3 (Jan 15): Quantum gates [Link]
Lecture 4 (Jan 20): Coherent computation, QFT, Deutsch Jozsa and oracle interrogation [Link]
Part 2: Algorithms, their impacts to cryptography and post-quantum crypto
[Notes] for Grover's algorithm
Lecture 5 (Jan 22): Grover's algorithm [Link]
Lecture 6 (Jan 27): Grover's algorithm cont'd and BHT [Link]
Lecture 7 (Jan 29): Quantum Fourier Transform [Link]
Lecture 8 (Feb 2): Shor's algorithm [Link]
Lecture 9 (Feb 5): Lattice based crypto [Link]
Part 3: Quantum cryptography
Lecture 10 (Feb 10): No cloning and Wiesner's quantum money (BB84 states) [Link]
Lecture 11 (Feb 12): Weakness of private key quantum money and public key quantum money [Link]
Lecture 12 (Feb 17): Subspace state, public-key quantum money, software copy-protection [Link]
Lecture 13 (Feb 19): Proof of quantumness, Mahadev's protocol [Link]
Lecture 14 (Feb 24): Mahadev's protocol cont'd
Lecture 15 (Feb 26): Quantum FHE [Link]
Lecture 16 (Mar 3): Quantum FHE, construction and proofs [Link]
Part 4: Post-quatum cryptography (security proofs and lifting lemmas)
Lecture 17 (Mar 5): BBBV argument and why Grover's is tight; random oracle [Link]
Lecture 18 (Mar 10): Random oracle, commitment, and lifting lemmas [Link]
Extra
Lecture 19 (Mar 12): Black holes, pseudorandomness and cryptography
Scribing Template: [Overleaf Link]
3 or 4 assignments in total.
Solutions should be typeset in LaTeX.
Homework 1 [Link] [Link to LaTeX]
Homework 2[Link] [Link to LaTeX]
Homework 3[Link] [Link to LaTeX]
[File]
CSE291 in prior year
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