Quantum Query Complexity Basics and the Hybrid Method - Lecture 1

Learn about quantum query complexity fundamentals and the hybrid method in this graduate-level lecture from the IAS Park City Mathematics Institute's summer program on Quantum Computation. Explore one of the most productive models for studying quantum algorithms, examining significant quantum speedups from the Bernstein-Vazirani algorithm to the recent Yamakawa-Zhandry supremacy breakthrough. Delve into fundamental lower bound techniques including polynomial and adversary methods, while investigating their new variants like the compressed oracle technique. Examine the role of duals in these methods and discover how they can lead to tight bounds and novel algorithms. Access accompanying lecture notes and problem sets to reinforce understanding of query complexity basics and the hybrid method as part of a comprehensive exploration of near-term quantum computing's mathematical foundations.