Randomized versus quantum query complexity

How many input bits must an algorithm read to compute a Boolean function: deterministic, randomized and quantum query complexity. The quantum query model with a proof that measurements can be deferred; amplitude amplification; the adversary bound; Huang's theorem on the sensitivity graph; the inequality D(f) <= C Q(f)^4 for total functions, with complete proofs. Functions with quantum complexity about sqrt(m) and randomized complexity about m^(2-1/k), which show that the exponent 4 is optimal; the randomized lower bound uses one named hypothesis, the Forrelation lower bound of Bansal and Sinha. The course is an exposition of OpenAI's proof (2026).

Six lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.

1. Query complexity and a function with outward pointers
2. The quantum query model
3. Amplitude amplification and the Forrelation test
4. A tournament with probabilistic comparisons
5. The randomized lower bound
6. The quartic upper bound and the optimal exponent

Theorems and assumptions · Reader and editable sources · Course record

Prerequisites

• Alignment of lists: patterns, minimax and Ramsey's theorem (Large independent sets in three-colorable graphs)
• Linear algebra with complex inner products and unitary maps (core course Linear Algebra); finite probability. No physics.