Qipeng: Tuesday 2:00 - 3:00 pm + by appointment, CSE 4226
Sudhansh: Thursday 4:00 - 5:00 pm, outside CSE 4226 (open area with chairs and a whiteboard)
Evaluation is based on 4 psets and one final exam.
80% homeworks + 20% final (take-home) exam
This is a course on the theory/abstraction side. No prior knowledge of quantum mechanics or quantum computation is assumed.
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. In the first half, we will look at the foundations of quantum computing, including how to define qubits, quantum operation and general quantum algorithms. In the second half, we will explore topics including but not limited to breaking the famous RSA cryptosystem, Grover's algorithm, quantum money, quantum key distribution and 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, Elitzur-Vaidman bomb
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)
secret-key quantum money, fix and break
quantum key distribution
Lecture 0 (Jan 9) [Slides] : Welcome! + Introduction to quantum cryptography
Lecture 1 (Jan 11) [Notes 1] : Qubits, measurement and linear algebra recap
Lecture 2 (Jan 16) [Notes 2] : The ``polarizing filter effect'', multi qubit quantum states, general measurement, tensor and entanglement
Lecture 3 (Jan 18) [Notes 3] : Tensor, entanglement and basic quantum gates
Lecture 4 (Jan 23) [Notes 4] : Elitzur–Vaidman bomb tester
Lecture 5 (Jan 25) [Notes 5] : More on tensor, quantum unitary, and Deutsch algorithm
Lecture 6 (Jan 30) [Notes 6] : Deutsch–Jozsa algorithm, a quick look at Quantum Fourier Transform, any measurement = unitary + standard measurement
Lecture 7 (Feb 1) [Notes 7] : No-cloning, state distinguishing, approximate cloning
Lecture 8 (Feb 6) [Notes 8] : BB84 states (Weisner states), private-key quantum money
Lecture 9 (Feb 8) [Notes 9] : Break, fix, and break again
Lecture 10 (Feb 13) [Notes 10] : One-way functions, password hashing, and Grover's algorithm
Lecture 11 (Feb 15) [Notes 11] : More on Grover's algorithm and how to handle multiple pre-images
Lecture 12 (Feb 20) [Notes 12] : Grover's application, optimality, and pursuing exponential speedup (Simon's algorithm)
Lecture 13 (Feb 22) [Notes 13] : More on Simon's algorithm, its application to 3-round Feistel networks
Lecture 14 (Feb 27) [Notes 14] : RSA encryption, period finding and polynomial-time factoring algorithm (Shor's)
Lecture 15 (Feb 29) [Notes 15] : More on Shor's algorithm and how to implement Quantum Fourier Transform. (Yes, we do have Feb 29th in 2024)
Lecture 16 (Mar 5) [Notes 16] : Post-quantum cryptography -- lattices.
Lecture 17 (Mar 7) [same as above] : Post-quantum cryptography -- lattices, part 2.
Lecture 18 (Mar 12) [Slides] : Post-quantum cryptography -- lattices, part 3. How to make qubits/gates/quantum computers and a bigger picture.
Lecture 19 (Mar 14) : Course materials review and Q&A.
Prior to the class, I will share notes, and adjustments may be made to reflect the materials covered during the session. There are instances when I might cover fewer materials than what is already outlined in the notes.
Assignments will be added biweekly and due in the following week.
It is highly encouraged to typeset solutions in LaTeX.
Homework 1: [File] [Hadamard.ipynb] Due Jan 28.
Homework 2: [File] [Code] Due Feb 11.
Homework 3: [File] Due Feb 28.
Homework 4: [File] [Code] Due Mar 12.
Template: [Overleaf Link] or [Zip]
Course, a graduate version of this course
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 (although we will not focus on any specific textbook)