The Power of Random Quantum Circuits

Explore the intricacies of random quantum circuits in this comprehensive lecture from the Simons Institute. Delve into the concept of quantum advantage in the NISQ era, focusing on quantum supremacy and Random Quantum Circuit Sampling (RCS). Examine why random circuits are an attractive proposal and the challenges of classical computation in this context. Investigate the hardness of computing output probabilities of noisy random circuits, including average case hardness for Permanent and the BFNV'18 hardness results. Learn about worst-to-average reduction attempts, new approaches to scrambling gates, and the BFNV'19 construction. Consider ongoing research on the difficulty of computing noisy random circuit probabilities, including worst-case hardness and new easiness results. Analyze numerical results for noisy 1D RCS, presented with illustrative plots. Gain valuable insights into the power and potential of random quantum circuits in the field of quantum computing.

Intro
Quantum advantage in the NISQ era
Quantum supremacy
Random Quantum Circuit Sampling (RCS)
Why are Random Circuits an attractive proposal?
Why is RCS hard classically?
Today's focus: hardness of computing output probabilities of noisy random circuits
Average case hardness for Permanent [Lipton '91]
(BFNV'18): Hardness for Random Quantum Circuits
Worst-to-Average Reduction - Attempt 1: Copy Lipton's proof
New approach to scramble gates of fixed circuit
Correlating via quantumness
Understanding the BFNV'19 construction
Is it hard to (nearly exactly) compute noisy random circuit probabilities? ongoing joint work
Noisy circuit output probability
Worst-case hardness of computing noisy
New easiness results
Numerical results for noisy 1D RCS [Noh, Jiang, F'20]
Plots from [Noh, Jiang, F'20] (1)
Conclusions