Quantum Query Complexity: The Adversary Method - Lecture 4

Learn about quantum query complexity and the adversary method in this 57-minute lecture from the IAS Park City Mathematics Institute's 2023 Graduate Summer School on Quantum Computation. Explore fundamental lower bound techniques in quantum computing, focusing on polynomial and adversary methods used to analyze quantum algorithm speedups. Delve into new variants like the compressed oracle technique, examine the role of duals in these methods, and discover how they lead to tight bounds and novel algorithms. Study significant quantum speedups from the Bernstein-Vazirani algorithm to the recent Yamakawa-Zhandry supremacy breakthrough, while investigating the theoretical limits of quantum queries that have intrigued researchers since quantum computing's early days.