Complexity and Applications of Random Circuit Sampling
summary
A polynomial-time classical algorithm is presented that, given M samples from a noisy random circuit sampling (RCS) experiment, produces M spoofed samples in time poly(M) and achieves indistinguishability by setting total variation error roughly 1/M, though practical runtime scales as M^(1/γ) where γ is noise per gate. The method uses a Pauli path integral ordering of dominant paths. For benchmarking, XEB fidelity shows XEB decay e^{-t d} allowing estimation of total layer error t and supporting the claim of largely uncorrelated noise.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:46Quantum supremacy experiments
- 2:37Understanding evidence of high complexity
- 3:57The complexity of noisy RCS
- 6:09The role of circuit depth
- 7:02Prior argument: Feynman path integral
- 7:40Our algorithm: Pauli path integral
- 8:52Discussion
- 12:24Challenge: crosstalk and correlated errors
- 13:24Multi-qubit noise benchmarking methods
- 13:48Motivation: Google's quantum supremacy experiment [Arute et al 19]
- 16:28Overview of RCS benchmarking
- 16:58Theory of RCS benchmarking
- 18:26Correlated errors in fidelity estimation
- 19:42Conclusion
related talks
49mExponential improvements to the average-case hardness of random circuits
45mNoise vs Imprecision in the Hardness of Random Quantum Circuits
33mSpoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
53mFrom randomized benchmarking to cycle error reconstruction
50mQuantum Benchmarking
51mCircuit Conspiracies
01h 02mHow did we miss the random purification channel?
51mPeaked quantum advantage using error correction