Validated Quantum Advantage via Bell Sampling
summary
Proposes a concrete model that samples 2n-bit outcomes by applying a two-copy transversal Bell measurement to C ⊗ C, gives complexity-theoretic evidence that sampling from random circuits is classically intractable, and shows the Bell distribution is supported on the symmetric subspace (instead of 4^n full space it collapses to stabilizer-sized supports ~2^n for Clifford-like states). Practical notes: Bell readout fits Rydberg/ion-trap single-layer architectures; purity and fidelity become efficiently estimable and learning a Clifford+T circuit needs about n log n Bell samples plus ~2^t additional operations.
AI-written summary · about
chapters (20)
- 0:00Intro
- 0:37Quantum advantage demonstrations
- 4:23Evidence for hardness
- 5:25The outcome distribution
- 6:48Verification & benchmarking of QRS
- 10:16Bell sampling is realistic
- 10:59Bell sampling is hard: the Stockmeyer argument
- 13:21The Bell sampling distribution has structure!
- 14:51Support & the SWAP test
- 18:03Correlations & the subsystem SWAP test
- 22:30Stabilizer dimension & magic test
- 31:00Noisy quantum random sampling
- 32:47Noisy Bell sampling
- 37:37Error detection
- 40:08Classical algorithms
- 45:07Proposed quantum advantage test
- 47:03Measuring fidelity in experiments
- 50:07On robustness to noisy simulation algorithms
- 53:05Bell sampling highlights
- 53:49Outlook & questions
related talks
38mQuantum Technologies: Quantum Computing & Secure Quantum Communication
22mSecurity of Quantum Machine Learning Systems
34mQuantum and Classical Coin-flipping Protocols Based on Bit-commitment and their Point Games
40mThe Double-Edged Qubit: Strategic Perspectives on Quantum for Defence
11mSecuring the Quantum Future: Exploiting Crosstalk and Controller Vulnerabilities
35mQuantum Cryptography: From Theory to Practice
43mWhen the Internet Is Ruled by Schrödinger's Cats
34mRecent Advances in Asynchronous Multi-Party Computation