Noise vs Imprecision in the Hardness of Random Quantum Circuits
summary
Proves average‑to‑worst‑case hardness for random circuit output probabilities using Feynman path integrals, polynomial structure and a Stockmeyer reduction, upgrading prior bounds to 2^{-O(m log m)} additive error and extending the argument to local depolarizing noise. The core tool is a Taylor‑series truncation of small gate perturbations to restore polynomial extrapolation; shows noisy circuits remain Sharp‑P hard at that precision while trivial uniform guessing succeeds at about 2^{-O(m)}, creating a noise barrier that forces new proof techniques.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:50The first "Quantum supremacy" claims have now been made...
- 1:43These experiments have a similar theoretical framework
- 4:05Proof first step: from sampling to computing
- 5:55Formal statement of q. supremacy conjecture
- 7:51Hardness conjecture for BosonSampling
- 9:11Roadmap for the rest of talk
- 10:47Average case hardness for Permanent [Lipton '91]
- 15:31[BFNV'18]: Hardness for Random Quantum Circuits
- 16:48First attempt at adapting Lipton's proof
- 18:39Correlating via quantumness
- 23:27How to motivate the truncations?
- 27:55On robustness to imprecision BFLL'21
- 33:18Understanding hardness of noisy random quantum circuits BFLL'21
- 36:10Similar hardness arguments work with noise!
- 40:31The noise barrier to improving robustness
- 42:15Conclusions
related talks
49mExponential improvements to the average-case hardness of random circuits
53mFundamental limits to quantum computation
53mFrom randomized benchmarking to cycle error reconstruction
50mQuantum Benchmarking
33mSpoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
01h 08mPutting Quantum Supremacy on a Rigorous Footing
51mCircuit Conspiracies
01h 37mFault-Tolerance Against Adversarial Errors & PCPs