Skip to content
lectern.tv
Editorial path·Theory & Algos·research·Carnegie Mellon University

Boolean Fourier Analysis to Quantum Complexity

Harmonic analysis on the hypercube, linearity testing, social choice, and quantum circuits

Connects Ryan O'Donnell's CMU sequences on Analysis of Boolean Functions and Quantum Computation to reveal how multilinear polynomials govern both classical property testing and quantum interference.

Start Step 16 steps · 8h total
Lecture 1: The Fourier Expansion and Basic Formulas (15-859)
Step 1 of 6

Curriculum sequence

6
Step 1·Carnegie Mellon University·Ryan O'Donnell·15-859· 1:11:25

Lecture 1: The Fourier Expansion and Basic Formulas (15-859)

Develops the orthonormal parity basis and Parseval/Plancherel identities over the Boolean hypercube.

Step 2·Carnegie Mellon University·Ryan O'Donnell·15-859· 1:12:46

Lecture 2: Probability Densities and BLR Linearity Testing (15-859)

Applies Fourier coefficients directly to analyze Blum-Luby-Rubinfeld (BLR) linearity testing.

Step 3·Carnegie Mellon University·Ryan O'Donnell·15-859· 1:17:33

Lecture 3: Social Choice and Influences (15-859)

Links coordinate influences and noise stability to Arrow's impossibility theorem in social choice.

Step 4·Carnegie Mellon University·Ryan O'Donnell·15-859BB· 1:08:48

Lecture 1: 10^500 Parallel Universes (15-859BB)

Transitions from classical probability distributions to exponential complex amplitude vectors.

Step 5·Carnegie Mellon University·Ryan O'Donnell·15-859BB· 1:20:24

Lecture 2: Rotate, Compute, Rotate (15-859BB)

Shows how Hadamard transforms — the mod-2 Fourier transform — create constructive and destructive interference.

Step 6·Carnegie Mellon University·Ryan O'Donnell·15-859BB· 1:21:29

Lecture 3: Understanding and Measuring One Qubit (15-859BB)

Formalizes single-qubit unitary geometry, Bloch-sphere rotations, and projective measurement.