Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
summary
Claims a classical algorithm that uses light-cone marginals to sample from shallow random circuits, computes each marginal in poly(n)·2^L time where L is the light‑cone size, and provably achieves inverse-polynomial XEB on 2D depth‑O(log n) circuits. Analysis reduces expected linear XEB to a sum of nonnegative tensor‑network terms indexed by random‑walk paths, and the algorithm effectively “zeros out” far light cones rather than fully simulating the 2^n state.
AI-written summary · about
chapters (9)
- 0:00Motivation
- 5:02Quantum Circuits
- 6:54Random Circuit Sampling
- 10:30Linear XCD
- 13:15Google
- 17:10Theory
- 22:18Results
- 24:25Intuition
- 28:48Summary
related talks
01h 10mQuantum Advantage with Shallow Clifford Circuits
42mLearning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time
15mScalable Equivalence Checking and Verification of Shallow Quantum Circuits
59mUtility, Computational Cost, and Effective Quantum Volume of NISQ Experiments
02h 41mLightning Talks
01h 08mPutting Quantum Supremacy on a Rigorous Footing
45mNoise vs Imprecision in the Hardness of Random Quantum Circuits
01h 09mRecent Progress in Quantum Advantage