Exponential improvements to the average-case hardness of random circuits
summary
Claims an exponential improvement in robustness for estimating output probabilities of random circuits and BosonSampling, tightening the error from essentially 2^{-n} to matching the first two exponent terms e^{-n log n - n - n^{ε}} and leaving only an O(log n) gap; introduces new tools—dilution, coefficient extraction, rare events lemmas—that reduce polynomial degree and extrapolation distance; proves a first nontrivial average-case sampling hardness that rules out any classical sampler that succeeds on all but a 2^{-N^{1/3}} fraction of inputs; constructions overcome depth and JSV barriers and rely on anti-concentration and Gaussian-shift tails.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 0:42Why sampling from random circuits is fascinating
- 4:34Unproven conjectures
- 6:18Status of proof
- 8:20Why is progress so difficult
- 8:58Hardness of sampling
- 14:05Worst to average case reduction
- 16:54New tools
- 17:32Dilution
- 24:40Depth Barrier
- 26:35Permanent
- 29:47JSV barrier
- 31:38Improving robustness
- 34:05Key idea
- 37:15Technical details
- 40:15Questions
related talks
45mNoise vs Imprecision in the Hardness of Random Quantum Circuits
22mComplexity and Applications of Random Circuit Sampling
01h 09mRecent Progress in Quantum Advantage
53mFrom randomized benchmarking to cycle error reconstruction
33mSpoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
01h 08mPutting Quantum Supremacy on a Rigorous Footing
48mStatistics In Quantum Computational Supremacy
53mFundamental limits to quantum computation