Quantum Cryptography (CSE 190, 2024 Winter)

Course Information

Location: WLH 2207

Time: Tuesday and Thursday, 11:00 am - 12:20 pm

TA(s): Sudhansh Peddabomma (speddabomma@ucsd.edu)

Office Hours:

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)

Grading: 

Evaluation is based on 4 psets and one final exam. 

80% homeworks + 20% final (take-home) exam

Course Description

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.

Tentative Schedule

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

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.

Homework

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]

Other Materials

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)