Classical and Quantum Approaches
Description: This is a graduate-level course that explores the classical and quantum algorithmic foundations of machine learning and data science, with a focus on techniques that provide provable guarantees. The course is divided into two parts. The first half introduces a number of classical techniques for algorithm design, including tensor methods, Sum-of-Squares (SoS), spectral analysis, MCMC, and diffusion. The second half presents a self-contained introduction to quantum algorithms for optimization and machine learning, including quantum linear algebra, quantum sampling, and learning from quantum data. Throughout the course, we will cover applications across a range of domains, including but not limited to robust statistics, generative modeling, statistical and quantum physics. We aim to provide a unified perspective on how advanced algorithmic techniques—both classical and quantum—can be applied to address key challenges in high-dimensional data analysis.
Time/Location: TTH 9:00 am, SCHM 116
Instructor: Ruizhe Zhang (rzzhang@purdue.edu)
Office hours: By appointment
Course information: Here
Assignments will be posted below and in Brightspace when they become available.
The schedule will be updated as we progress through the course.
| Date | Topic | Materials | Resources |
|---|---|---|---|
| Aug 26 | Introduction; Quantum supremacy and classical spoofing | [slides] | |
| Aug 28 | Tensors (I): Jennrich's algorithm | [slides] | |
| Sep 2 | Tensor (II): Iterative methods | [slides] | |
| Sep 6 | Tensors (III): Overcomplete tensor decomposition | ||
| Sep 9 | Tensors (IV): Tensor networks and applications; Quantum supremacy revisit | ||
| Sep 11 | Super-resolution (I) | ||
| Sep 16 | Supre-resolution (II) | ||
| Sep 18 | Sum-of-Squares (I) | ||
| Sep 23 | Sum-of-Squares (II) | ||
| Sep 25 | Sum-of-Squares (III): Non-commutative SoS and quantum max-cut | ||
| Sep 30 | Semi-definite programming (I): First-order methods | ||
| Oct 2 | Semi-definite programming (II): Second-order methods | ||
| Oct 7 | Classical sampling (I): basics MCMC | ||
| Oct 9 | Classical sampling (II) | ||
| Oct 16 | Diffusion model (I) | ||
| Oct 21 | Diffusion model (II) | ||
| Oct 23 | Quantum eigenvalue problems (I): Quantum phase estimation | ||
| Oct 28 | Quantum eigenvalue problems (II): Early fault-tolerant phase estimation | ||
| Oct 30 | Quantum eigenvalue problems (III) | ||
| Nov 4 | Quantum linear algebra (I) | ||
| Nov 6 | Quantum linear algebra (II) | ||
| Nov 11 | Quantum linear algebra (III) | ||
| Nov 13 | Quantum linear algebra (IV) | ||
| Nov 18 | Quantum sampling: Quantum walk | ||
| Nov 20 | Quantum sampling: Quantum Gibbs sampling; Intro to open quantum systems | ||
| Nov 25 | Quantum learning theory: Shadow tomography | ||
| Dec 2 | Quantum learning theory: Hamiltonian learning | ||
| Dec 4 | Project presentation | ||
| Dec 9 | Project presentation | ||
| Dec 11 | Project presentation |