Scott Aaronson: Quantum Supremacy | AI Podcast Clips

Definition and Origins

• "Quantum supremacy" (technically "quantum computational supremacy") is a term coined by John Preskill in 2012 to describe the point where a quantum computer performs a well-defined task significantly faster than any known classical algorithm.
• The concept traces back to the 1980s, originating from discussions by Richard Feynman and David Deutsch regarding quantum computing.
• The task does not need to be practically useful, but it must be well-defined with verifiable right and wrong answers.
• Quantum computers do not solve uncomputable problems (e.g., the Halting Problem); they only change what is efficiently computable.

Computational Efficiency and Scaling

• Classical computers can eventually simulate any quantum operation by storing all amplitudes of the quantum state, though this process scales exponentially.
• Quantum advantage relies on polynomial scaling for time complexity relative to input size, whereas the best-known classical algorithms for these tasks scale exponentially.
• Three specific criteria define a successful demonstration:
  • Literal speed advantage (fewer seconds/minutes to solve).
  • Theoretical scaling behavior where classical scaling is exponential and quantum scaling is polynomial.
  • The observed speedup must be explainable solely by the exponential size of the quantum state (e.g., a 50-qubit state involving $2^{50}$ amplitudes).
• Error correction is not required for quantum supremacy; the demonstration itself refutes skeptics claiming quantum computers will never outperform classical ones.

Google's Experimental Approach

• Google utilized a 53-qubit processor to perform a "sampling problem" rather than a task with a single answer (like factoring numbers).
• The experiment involved applying a randomly chosen sequence of quantum operations to generate samples from a specific probability distribution over strings of 53 bits ($2^{53}$ possible outputs).
• Outputs are probabilistic; some strings are more likely due to constructive interference, while others are suppressed by destructive interference.
• Verification relies on the Linear Cross Entropy Benchmark (XEB), which compares the quantum output probabilities against classical calculations.
• Google selected 53 qubits because this scale is sufficient to challenge the world's largest supercomputer, "Summit" at Oak Ridge National Lab, while remaining just small enough for classical verification.
• Verification of the 53-qubit experiment requires a classical calculation of $2^{53}$ operations (approximately 9 quadrillion), which is barely feasible on current supercomputers.

Theoretical Justification and Skepticism

• It is currently impossible to definitively prove that no fast classical algorithm exists for simulating these sampling experiments; this relies on assumptions similar to $P \neq NP$.
• Researchers provide "reduction evidence," arguing that if a fast classical spoof existed, it would imply that other problems widely considered hard (and foundational to cryptography) would also be easy.
• Empirical validation involved testing all known classical simulation methods to ensure they exhibited exponential scaling on the specific parameters of Google's experiment.
• While the 53-qubit demonstration proves a quantum speedup, increasing to 100+ qubits would eventually make verification impossible, necessitating a shift to different computational methods.