Separating Quantum from Classical with k-fold Forrelation and Friends
summary
k-fold Forrelation is easy for quantum machines (about k/2 queries, BQP-complete) but hard for simple classical models: any decision tree or parity decision tree needs about n^{1-1/k} classical lower bound queries (k constant, so k=2 gives ≈√n). The proof uses l1-Fourier growth to bound level-wise Fourier weight and pathwise analysis/Gaussian interpolation (Talagrand’s smart path, integration by parts) to cancel high-degree terms so only low-level moments matter.
AI-written summary · about
chapters (10)
- 0:00Start
- 7:002-fold Forrelation
- 11:253-fold Forrelation
- 23:05Lower Bounds via Fourier Growth
- 26:06Smart Path Method
- 27:56Main Theorem
- 31:50Fourier Growth of Decision Trees
- 37:53Gaussian Interpolation
- 50:31Gaussian Integration by Parts
- 53:32Summary
related talks
32mCan We Get Verifiable Quantum Advantage from Forrelation
21mQuantum versus Randomized Communication Complexity, with Efficient Players
01h 10mQuantum Advantage with Shallow Clifford Circuits
20mA Quantum Interpretation of Separating Conjunction for Local Reasoning of Quantu
59mQuantum cryptography and quantum complexity
45mClassical Verification of Quantum Computational Advantage
15mClassical algorithms and quantum limitations for maximum cut on high-girth graphs
33mLightning Talks