Quantum Advantage with Shallow Clifford Circuits
summary
Constant-depth Clifford circuits on 2D graph states provably solve a relation that bounded‑fan‑in constant‑depth classical circuits cannot: the GHZ game gives quantum win 1 vs classical 3/4, and that local lightcone counting scales to a big GHZ embedding on the grid. Random‑restriction + multiswitching turns AC0 impossibility into NC0 impossibility, and two‑round interactive measurement simulators would lift any classical simulator to parity‑L‑hard computation, so interaction yields exponentially stronger hardness than noninteractive sampling.
AI-written summary · about
chapters (8)
- 0:00Introduction and motivation
- 1:14Defining quantum advantage
- 7:20Sampling and relation problems
- 16:22Non-locality and circuit depth
- 21:30GHZ game and circuit bounds
- 37:13Interactive protocol overview
- 40:16Interactive simulation leverage
- 51:00Open questions and future work
related talks
15mScalable Equivalence Checking and Verification of Shallow Quantum Circuits
01h 09mRecent Progress in Quantum Advantage
45mClassical Verification of Quantum Computational Advantage
46mProbing the limits of classical computing with arbitrarily connected quantum circuits
48mQuantum Linear Algebra Using Subspace States
01h 03mConstant depth pseudoentanglement - Shallow circuits, deep backstory
42mLearning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time
42mTests for "Quantumness"