CSE 599C: "Quantum Learning Theory"
(Winter 2025)
Course Information
Instructor: Andrea Coladangelo
Time & location: Tuesdays and Thursdays 11.30am-12.50pm, CSE2 G04
Class Q&A: Ed Discussion
Office hours: Thursdays 4:30-5.30 (CSE2 212)
Course Description
This course is an introduction to the topic of “quantum learning theory”, in the sense of learning properties of a quantum state given copies of it. Unlike a classical string, whose description is entirely known from reading it once, it is not in general possible to learn the “description” of a quantum state given a single copy of it, since a measurement in general disturbs it. This leads to the question: when can we learn (a useful description of) a quantum state? We will explore various settings starting from foundational results on quantum state “discrimination” (i.e. identifying a state from a known family) and quantum state ”tomography” (i.e. learning the entire description of the state given a large number of copies), and then moving to recent developments on “shadow tomography” (i.e. learning useful classical descriptions of a state given few copies).
This is an advanced class: familiarity with the contents of the graduate course “Quantum Information and Computation” (CSE 534) (or equivalent background) is a prerequisite.
Approximate List of Topics
We will be taking inspiration from John Wright's recent course. We will be following a somewhat similar outline, and you can find good lecture notes there. A tentative list of topics:
Quantum State Discrimination (identifying a state from a known finite collection of states)
Quantum State Tomography (learning a full description or specific properties of an arbitrary state)
Shadow Tomography (learning short but useful descriptions of states that can be used to approximately predict many properties of interest)
Learning in various specialized settings (depending on time, we will explore applications of the techniques we learnt to some settings of interest, e.g. learning local Hamiltonians, learning states generatable in short-depth, distinguishing random from pseudorandom states).
Schedule
01/07: General framework for quantum learning; review of quantum information; "Quantum State Discrimination" for two pure states (notes)
01/09: Quantum State Discrimination for two mixed states (given a single copy); trace distance (notes)
01/14: Quantum State Discrimination for two mixed states (given multiples copies); fidelity (notes)
01/16: Quantum State Discrimination in the general setting; the "Pretty Good Measurement" (notes)
01/21: Equality and Purity Testing; the SWAP test (notes)
01/23: SWAP test and the symmetric subspace (notes)
01/28: Symmetric subspace (continued); intro to Quantum State Tomography (notes)
01/30: "Tomography" for classical distributions; single-qubit tomography (notes)
02/04: Single-qubit tomography (continued); intro to the "Pauli tomography algorithm'' (notes)
02/06: (no class)
02/11: The "Pauli tomography algorithm" (notes)
02/13: The Haar Measure (notes)
02/18: The Haar measure (continued); optimal pure state tomography (notes)
02/20: Unitary designs; The "quantum OR lemma" (intro) (notes)
02/25: The "quantum OR lemma": an algorithm based on Marriott-Watrous estimation (notes)
03/04: "Classical shadow tomography" (part 1) (notes)
03/06: "Classical shadow tomography" (part 2) (notes)
03/11: "Classical shadow tomography" (part 3) (notes)
03/13: Quantum state certification of almost all states from few single-qubit measurements (notes)
Grading
5 homeworks, each worth 20% of the grade.
Late submissions
You have three tokens for a 24h late submission (no questions asked). You may use more than one on the same homework.