Interview, Fireside Chat
Scott Aaronson: Quantum Supremacy | AI Podcast Clips
- Quantum supremacy remains the preferred term for distinguishing quantum performance, as no superior alternative exists, while quantum computers operate strictly within Alan Turing's computational limits and cannot solve the halting problem or other uncomputable tasks.
- Achieving supremacy on 50 qubits necessitates tracking $2^{50}$ numbers classically, with performance scaling such that 100 qubits would yield significantly faster quantum speeds compared to classical counterparts.
- Supremacy on sampling problems, such as those targeted in 2011 by the speaker and colleagues, does not require error correction and suffices to refute claims that quantum computers will never outperform classical systems.
- The Google device utilized 53 qubits generating $2^{53}$ possible outputs with varying probabilities, requiring a linear cross-entropy benchmark calculation of approximately nine quadrillion classical operations.
- Verification of 53-qubit results is barely feasible on the Summit supercomputer at Oak Ridge National Lab, whereas results for 100 qubits currently cannot be verified because methods to do so are unknown.
- Once classical verification capabilities are surpassed, researchers anticipate shifting away from sampling experiments toward other types of computation as these specific experiments lose interest.
- Definitive exclusion of fast classical algorithms for simulating quantum mechanics remains an open problem, though any such algorithm would need to differ significantly from known methods.
- Evidence from 2015 regarding the hardness of simulating these experiments contributed to Google's decision to proceed, despite the speaker acknowledging the current reduction evidence is unsatisfactory and represents a major open research challenge.
- A sampling problem run perfectly on a quantum computer would likely never produce the same output twice, highlighting the unique nature of the data generated.
- Material discussions on complexity are anticipated to be extensive, potentially requiring several hours of conversation that may not be fully covered in the current context.