Theory of Near-Term Quantum Advantage - Part 4

Explore quantum computation theory and near-term quantum advantage in this comprehensive lecture from the University of Chicago's Bill Fefferman at the Park City Mathematics Institute. Delve into the critical goal of demonstrating quantum computations that surpass classical computer capabilities, examining both theoretical foundations and practical implications. Learn about experimental quantum advantage as a milestone toward fault-tolerant quantum computers and its role in testing quantum theory in high complexity scenarios. Examine current evidence supporting near-term quantum experiments' potential to solve classically intractable problems, while understanding classical simulation algorithms' limitations. Cover key concepts including the Porter Thomas property, heavy output generation, linear crossentropy, and simulation results. Part of the 2023 PCMI Graduate Summer School program focusing on quantum computation, this lecture integrates with a broader curriculum featuring expert-led minicourses on quantum learning, information theory, linear-algebraic algorithms, error-correcting codes, and the complexity theory of random circuits and Hamiltonians.