CS 59300ADS - Purdue University

Course Details

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

Course feedback: Here

Lectures

The schedule will be updated as we progress through the course.

Date	Topic	Materials	Resources
Aug 26	Introduction; Quantum supremacy and classical spoofing	[slides]	History of supremacy experiments and classical spoofings: [LaRose '2024] Google's supremacy experiment in 2019: [Arute et al. '2019]
Aug 28	Tensors (I): Jennrich's algorithm	[slides]	Book chapter on theoretical tensor decomposition: [Vijayaraghavan '2020] Perturbation analysis for Jennrich's algorithm: [Bhaskara et al. '2013]
Sep 2	Tensor (II): Iterative methods	[slides]	Tensor power method: [Sharan-Valiant '2017]
Sep 6	Tensors (III): Overcomplete tensor decomposition	[slides]	Smoothed analysis for tensor decomposition: [Bhaskara et al. '2013] and [Anari et al. '2018]
Sep 9	Tensors (IV.I): Tensor networks: basics	[slides]	tensornetwork.org Lecture notes on tensor networks: [Bridgeman-Chubb] and [Banuls]
Sep 11	Tensors (IV.II): Tensor networks: applications in quantum (quantum circuit simulation and DMRG)	[slides]	Classical simulation of quantum circuits: [Markov-Shi '2005]
Sep 16 - 18	Tensors (V): Tensor networks: applications in cryo-EM (orbit recovery)	[slides]	List recovery of SO(2) MRA: [Moitra-Wein '2018] Invariant theory for orbit recovery: [Bandeira et al. '2017] and [Liu-Moitra '2021]
Sep 23	Super-resolution (I)	[slides]	1-D super-resolution limit: [Moitra '2015] Noisy super-resolution: [Ding et al. '2024]
Sep 25	Super-resolution (II)	[slides]	2-D diffraction limit: [Chen-Moitra '2020]
Sep 30	Sum-of-Squares (I)	[slides]	Quantum separability problem: [Barak-Kothari-Steurer '2017] Recent breakthrough result: QMA+(2)=NEXP: [Jeronimo-Wu '2023]
Oct 2	Sum-of-Squares (II)	[slides]	SoS for robust mean estimation: [Hopkins-Li '2017], [Kothari-Steurer '2017] SoS lecture notes: [Kunisky '2022], [Potechin '2018] Semialgebraic Proofs and Efficient Algorithm Design: [Fleming-Kothari-Pitassi '2021] [Proofs, beliefs, and algorithms through the lens of sum-of-squares]
Oct 7	Sum-of-Squares (III)	[slides]	Quantum Max Cut (with product state): [Parekh-Thompson '2022] Current record for the approximation ratio: [Gribling-Sinjorgo-Sotirov '2025] Hardness of approximation (assuming UGC): [Hwang et al. '2021]
Oct 9 - 16	Sampling (I): Variational inference	[slides]	Mean-field approximaiton: [Jain-Koehler-Risteski '2018] Variational inference and convex relaxation: [Risteski '2016] Stochastic localization for mean-field approximation: [Eldan '2020] Bethe free energy and belief propagation: [Koehler '2019]
Oct 21	Sampling (II): Stochastic calculus	[slides]	Logconcave Sampling: [Sinho Chewi] Lecture notes: [Kevin Tian '2025]
Oct 23	Sampling (III): Diffusion model	[slides]	Diffusion models: references are provided in the slides Stochastic localization review: [Shi-Tian-Zhang '2025]
Oct 28	Quantum eigenvalue problems (I): Quantum phase estimation	[slides]
Oct 30	Quantum eigenvalue problems (II): Early fault-tolerant phase estimation	[slides]
Nov 4	Quantum linear algebra (I)	[slides]	Block-encoding: [Lin '22, Chapter 6]
Nov 6	Quantum linear algebra (II)	[slides]	Quantum linear system solvers survey: [Morales et al. '2025]
Nov 11 - 13	Quantum linear algebra (III)	[slides]	Quantum eigenvalue transformation/Qubitization: [Lin '22, Chapter 7] Quantum singular value transformation: [Gilyén et al. '2018], [Tang-Tian '2023] QSP and phase factor finding survey: [Lin '2025]
Nov 18	Quantum linear algebra (IV)	[slides]	Quantum walk: [Childs '25, Part III], [Lin '22, Section 7.2] Hamiltonian simulation: high-order Trotterization [Childs et al. '19], time-dependent Hamiltonian [Fang-Liu-Sarkar '24] Quantum ODE solvers: [Lin '22, Chapter 4], [An et al. '25], nonlinear ODE [Liu et al. '21]
Nov 20	LCHS; Intro to open quantum systems (I)	[slides]	Lecture notes on open quantum system: [Lidar '20]
Nov 25	Open Quantum Systems (II): Lindblad simulations	[slides]	A short note on Davies generator: [Lin '24]
Dec 2	Open Quantum Systems (III): Ground state/Gibbs state preparation; Hamiltonian learning	[slides]	Survey on the dissipative preparation of quantum states [Lin '25] Lecture notes on quantum learning theory: [Sitan Chen and Jordan Cotler (Harvard)], [John Wright (UC Berkeley)]
Dec 4	Project presentation
Dec 9	Project presentation
Dec 11	Project presentation

CS 59300 Algorithms for Data Science, Fall 2025

Course Details

Announcements

Assignments

Lectures

Resources