Theory of Near-Term Quantum Advantage - Part 1

Learn about the theoretical foundations of near-term quantum advantage in this lecture from the Park City Mathematics Institute's Graduate Summer School program. Explore the computational complexity of quantum experiments and understand why demonstrating quantum advantage is crucial for the field of quantum computation. Delve into topics including random circuit sampling, boson sampling, and the challenges of classical simulation algorithms for quantum experiments. Examine the current evidence supporting near-term quantum experiments' ability to solve classically intractable problems. Study through detailed lecture notes and accompanying problem sets that cover quantum circuit sampling, quantum approximate sum problems, and multiplicative approximation. Part of a comprehensive three-week summer program featuring expert-led minicourses on quantum computation, this lecture contributes to a broader curriculum including quantum learning theory, quantum information theory, and quantum Hamiltonian complexity.