Verifiable Quantum Supremacy: What I Hope Will Be Done
summary
Argues for a concrete research program: design circuits that are NISQ-implementable, provably hard for classical simulation, yet classically efficiently verifiable; analyzes why current random-circuit and BosonSampling experiments fail that third goal because fidelity decays exponentially and verification ties to hardness (the linear cross-entropy benchmark problem). Proposes studying the structure of postselected “peaked” random circuits, searching for short appendices that force outputs, and pursuing an unconditional experimental demonstration via Quantum Information Supremacy / hidden-matching ideas with ~20 qubits.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 5:00Scott Aronson
- 6:47Recap
- 14:55Classical Computing
- 21:00Random Circuit Sampling
- 24:54No Error Correction
- 33:35Quantum Advantage
- 35:39Physics Simulation
- 41:50Random Peak Circuits
- 47:55Adding an Appendix
- 49:45Paths through Hilberts Space
- 55:38Preliminary Data
related talks
01h 02mQuantum Computing Deep Dive
41mState of Quantum Computing in programming
59mDiving Into Q#
20mMonte Carlo on noisy quantum computers
41mQuantum Computing deep dive
01h 01mEmpowering the Quantum revolution with Q#
25mQuantum NP and Beyond
22mQuantum space, ground space traversal, and how to embed multi-prover...