Putting Quantum Supremacy on a Rigorous Footing

on YouTube ↗01h 08m

" summary

Google builds a superconducting device with 52 qubits and ~depth 20 circuits (≈1,000 gates, each failing ~1/100) and reports a linear cross-entropy score ~1.002/2^n; the claim is that sampling from that noisy distribution is classically intractable unless the polynomial hierarchy collapses. Rigorous work targets a worst‑to‑average reduction via small‑theta gate perturbations, polynomial/Taylor interpolation or Cayley paths, highlights an m (gates) versus n (qubits) gap, and shows boson sampling needs n bosons in ~n^2 modes with exponentially small error tolerance.

AI-written summary · about

" chapters (8)

1. 0:00Start
2. 2:36Backdrop
3. 3:30What Quantum Supremacy Is
4. 3:54Why Is Quantum Supremacy So Important
5. 45:19Heavy Output Generation
6. 47:55Trivial Estimate
7. 56:56Classes of Algorithms
8. 1:02:03The Analog of the Exponential Time Hypothesis

" related talks

• 48mStatistics In Quantum Computational SupremacyYazhen Wang · Statistics in the Big Data Era 2022
• 24mQuantum Computing: a Treasure Hunt, not a Gold RushIgor Markov · MLconf SF 2019
• 01h 09mRecent Progress in Quantum AdvantageScott Aaronson · Quantum and Lattices Joint Reunion Workshop
• 28mThe Problem with QubitsJohn Martinis · Quantum Industry Day 2022
• 01h 02mQuantum Computing ConceptsJohn Azariah · NDC Copenhagen 2019
• 02h 42mQuantum Computing Exposed: Deep DiveJohan Vos, James Weaver · Devoxx Belgium 2017
• 53mThe quantum computers are comingAlasdair Collinson · Voxxed Days Bucharest 2018
• 34mQuantum Computing: Between Hope and HypeScott Aaronson · Post-Quantum Cryptography Conference Austin 2025