The Power of Random Quantum Circuits - Bill Fefferman

Explore the power of random quantum circuits in this conference talk from the Noisy Intermediate-Scale Quantum Systems: Advances and Applications conference. Delve into the concept of classical intractability and simulation algorithms for quantum systems. Examine the quantum supremacy conjecture and its formal statement. Follow the roadmap through average case hardness for Permanent, hardness for Random Quantum Circuits, and attempts to adapt Lipton's proof. Investigate the extensions to previous research and understand the challenges of noisy random quantum circuits. Discover the "noise barrier" to improving robustness and consider future directions regarding Random Circuit Sampling. Gain insights from Bill Fefferman of the University of Chicago in this 49-minute presentation, which offers a comprehensive overview of recent advances in integrable models across mathematical physics, condensed-matter physics, and string theory.

Intro
What do we mean by "classically intractable"?
What do we mean by "classical simulation" algorithm?
Proof first step: from sampling to computing
Formal statement of q. supremacy conjecture
Roadmap for the rest of talk
Average case hardness for Permanent [Lipton '91]
[BFNV18]: Hardness for Random Quantum Circuits
First attempt at adapting Lipton's proof
Extensions to [BFNV'19]
Understanding hardness of noisy random quantum circuits BFLL'21
Similar hardness arguments work with noise!
But there's also a (trivial) classical algorithm!
The "noise barrier" to improving robustness
Future directions regarding RCS