Quantum Cryptography (CSE 291, 2023 Fall)

Course Information

Location: DIB 121

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

TA(s): Pisit Wajanasara (pwajanasara@ucsd.edu)

Office Hours:

Qipeng, Tuesday 3:30 - 4:30 pm or by appointment (qipengliu@ucsd.edu), CSE 4226

Pisit, Monday 3:00 - 4:00 pm, CSE B240A (basement)

Grading:

Evaluation is based on 2 or 3 assignments plus a final project, scribing, and a final project (a written report and a presentation).

30% homeworks, 30% scribing for one topic (that may cover more than 1 lecture), 40% final project

Course Description

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.

Tentative Schedule

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
presentations

Lecture 0 (Sept 28): Welcome! + Introduction to quantum cryptography + single-qubit quantum states

Course Materials: [Slides], [Written Notes], [Nielsen-Chuang, page 13-16, single and multi qubits].

Advanced Readings: [Why we need complex numbers for quantum?]

Lecture 1 (Oct 3): Multi-qubit states, recap on linear alegebra, born rule and the Hidden Matching Problem

Course Materials: [Nielsen-Chuang, section 2.1.1-2.1.5, basics of linear algebra].

Advanced Readings: [Wikipedia on Hidden Matching]

Scribing: [File]

Lecture 2 (Oct 5): Single-qubit gates, multi-qubit gates, unitaries

Course Materials: [Written Notes]

Scribing: [File]

Lecture 3 (Oct 10): More on unitaries: CCNOT, universal gate set, coherent computation and a quick look at QFT

Course Materials: continued with the same notes in Lecture 2.

Scribing: [File] by Yizhao Zhang

Lecture 4 (Oct 12): Pre-image finding, Password Hashing and Grover's algorithms

Course Materials: [Written Notes]

Scribing: [File] by Yizhao Zhang

Lecture 5 (Oct 17): Alternative view on Grover's algorithms, and quantum collision finding algorithms (BHT algorithm)

Course Materials: continued with the same notes in Lecture 4

Advanced Readings: [Lower bounds for Grover's algorithm, Sec 4, BBBV lower bound] (notes from Daniel Grier's course)

Scribing: [File] by Rishabh Ranjan

Lecture 6 (Oct 19): Quantum Fourier Transform (QFT): a unified way to look at quantum algorithms

Course Materials: [Written Notes]

Scribing: [File] by Rishabh Ranjan

Lecture 7 (Oct 24): Quantum Fourier Transform (QFT): continued (Shor's algorithm)

Course Materials: continued with the same notes in Lecture 6, [Nielsen-Chuang, sec 5]

Advanced Readings: [An Efficient Quantum Factoring Algorithm], and a follow-up [Optimizing Space in Regev's Factoring Algorithm]

Scribing: [File] by Deepak Aryal

Lecture 8 (Oct 26): mixed states and density matrices

Course Materials: [Written Notes]

Scribing: [File] by Deepak Aryal

Lecture 9 (Oct 30, virtual): density matrices and quantum OTP

Course Materials: continued with the same notes in Lecture 8

Recording:

You will need to use Notability to see the video. When I was recording this, I did not realize Notability was for Mac OS/iOS (iPhone or iPad) only.

Let me know if you need a video version of the recording. I provide a PDF + audio below, but it lacks of the features of seeing the writing along with the audio.

``Video'' version: [Link]

PDF + audio version: [Link]

Scribing: [File] by Sudhansh Peddabomma

Lecture 10 (Nov 2): unclonability, state discrimination and Wiesner's states (BB84 states)

Course Materials: [Written Notes]

Scribing: [File] by Sudhansh Peddabomma

Lecture 11 (Nov 7): private-key quantum money, attacks on Wiesner's quantum money

Course Materials: continued with the same notes in Lecture 10

Advanced Readings: [Proof of direct-product hardness, Sec 6], [Proof of Monogamy-of-entanglement bound]

Scribing: [File] by Linhui Fu

Lecture 12 (Nov 9): subspace states and public key quantum money

Course Materials: continued with the same notes in Lecture 10

Advanced Readings: [Quantum money from subspaces], [Using iO to construct quantum money, Sec 6]

For those who want to learn more on unclonable cryptography: (Youtube) [Mark Zhandry's talk, part 1], [part 2]

Scribing: [File] by Linhui Fu

Lecture 13 (Nov 14): trapdoor claw-free functions and proof of quantumness

Course Materials: [Written Notes]

Scribing: [File] by Jack Morris

Lecture 14 (Nov 16): position verification, teleportation and an attack

Course Materials: [Written Notes]

Scribing: [File] by Jack Morris

Lecture 15 (Nov 21): port-based teleportation, non-local simultaneous computation

Course Materials: continued with the same notes in Lecture 14

Scribing: [File] by Pisit Wajanasara

Lecture 16 (Nov 28): quantum pseudorandomness

Course Materials: [Written Notes]

Lecture 17 (Nov 30): quantum pseudorandomness, continued

Course Materials: continued with the same notes in Lecture 16

Scribing Template: [Overleaf Link]

Homework

2 or 3 assignments will be added. One question will be released per week. If more than one, you can choose **one** to answer.

You will only need to submit the solutions when (1) we finish all lectures about quantum algorithms (up to Grover's and Shor's algorithms); (2) we finish all lectures about quantum information + quantum cryptography (up to position verification); (3) we finish connections to quantum physics.

Solutions should be typeset in LaTeX.

HW 1. [File] due on Nov 3

HW 2. [File] due on Nov 3

HW 3. [File] due on Nov 30

HW 4. [File] due on Dec 8

Final Project

[File]

Other Materials

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

Google Sites

Report abuse