Separating Quantum from Classical with K-Fold Forrelation and Friends

Explore a comprehensive lecture on quantum-classical separations through the lens of k-fold Forrelation problem. Delve into the challenges of differentiating quantum and classical complexity classes, and discover how concrete models like query and communication complexity provide valuable insights. Examine recent quantum-classical separations, including oracle separation of BQP and PH, optimal separations between quantum and classical algorithms, and oracle separation of one-way functions from quantum cryptographic primitives. Gain understanding of key analytical tools such as l1-Fourier growth and pathwise analysis, and their broader applications in pseudorandomness and statistical physics. Learn about the work of Makrand Sinha and Nikhil Bansal, as well as contributions from other researchers in this field.