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.