Aaronson, Scott

professor at UT Austin; director of its Quantum Information Center; theoretical computer scientist specializing in quantum computing and computational complexity

Scott Aaronson: Quantum Computing

Lex Fridman Podcast · Feb 17, 2020

• Scott Aaronson
• quantum computing
• quantum supremacy
• qubits
• decoherence
• quantum error correction
• Shor's algorithm
• post-quantum cryptography
• quantum machine learning
• computational complexity

Core ideas

Aaronson opens on the relationship between philosophy and technical fields, arguing that unanswerable "eternal" philosophical questions can often be productively replaced with narrower, tractable "Q-prime" versions that capture part of the original question's spirit while admitting real mathematical or empirical progress — citing Turing's move from "can machines think?" to the imitation game, and Gödel's reframing of ancient debates about the limits of reason into precise questions about provability within formal systems. He applies this method to free will in his own work: rather than debating metaphysical definitions of freedom, he proposes asking how well, in principle and consistent with physics, a person's future behavior could be predicted without destroying their brain in the process — a question that immediately surfaces concrete, partially answerable sub-questions about the brain's necessary level of computational description (neuronal, molecular, or quantum) and about quantum mechanics' inherent measurement-disturbance limits, which could fundamentally cap how much a predictive "brain-scanning" device could learn without altering the very system it's trying to model. He argues that even without ever answering the "hard problem" of consciousness, building genuinely predictive machines (or human-level/superhuman AI) would qualitatively transform how such debates are conducted, even if the deepest metaphysical question remains formally unresolved.

Aaronson explains quantum mechanics, stripped of physics jargon, as a generalization of ordinary probability theory in which possible states of a system are assigned "amplitudes" — numbers that, unlike probabilities, can be negative or complex — and which combine via interference (as in the double-slit experiment, where blocking one path can paradoxically make an outcome more likely by removing a canceling negative amplitude) rather than simple addition. A qubit is a bit maintained in superposition of amplitudes for 0 and 1, and critically, a system of n qubits requires 2^n amplitudes to fully describe if the qubits can interact — meaning even 1,000 qubits already exceed anything classical memory could ever encode, yet a quantum computer cannot simply "try every answer in parallel," since measuring a superposition just yields one random outcome; every quantum algorithm instead has to carefully "choreograph" interference so wrong-answer amplitude paths cancel out while correct-answer paths reinforce. He explains decoherence — the fundamental engineering obstacle to scaling quantum computers, where any unwanted leakage of a qubit's state into its environment (even a stray photon) effectively performs a "measurement" and collapses the desired superposition — and describes 1990s-era quantum error correction/fault tolerance theory as the crucial theoretical breakthrough proving that reliable, arbitrarily-scaled quantum computation is achievable from imperfect physical qubits, provided their individual error rates stay below a calculable threshold; the resulting overhead, however, is severe (thousands of physical qubits per usable "logical" qubit with currently known codes), which is why quantum computers aren't yet breaking real-world cryptography.

On Google's 2019 "quantum supremacy" announcement (a term coined by John Preskill in 2012), Aaronson clarifies it demonstrates a well-defined but not necessarily useful computational task performed dramatically faster than any known classical algorithm, and distinguishes this from actual usefulness. He explains that his own theoretical work (with Alex Arkhipov and others, circa 2011) established that "sampling problems" — asking a quantum device to output samples from a specific, hard-to-classically-simulate probability distribution, rather than solve problems with a single verifiable right answer — are a far more near-term-achievable path to demonstrating quantum advantage than tasks like factoring, since even noisy, non-error-corrected qubits can generate such distributions. Google's 53-qubit device applied a pseudo-random but exactly repeatable sequence of gate operations and used a statistical test (the "linear cross-entropy benchmark") to verify its outputs were biased toward the theoretically expected higher-probability bitstrings, a check requiring roughly 2^53 calculations — just barely within reach of Oak Ridge's Summit supercomputer, which is precisely why 53 qubits was chosen (too many qubits and verification itself becomes impossible; too few and no genuine classical intractability is demonstrated). He notes the underlying hardness claim rests on reduction-style evidence, similar in spirit to (but weaker than) evidence for P≠NP, rather than an airtight mathematical proof.

Addressing public misconceptions, Aaronson pushes back on Andrew Yang's tweet that quantum computing makes "no code uncrackable," clarifying that Shor's algorithm (the 1994 discovery that launched quantum computing as a field) can break widely-used RSA-style public-key cryptography only with millions of high-quality, error-corrected physical qubits — vastly beyond Google's 53-qubit noisy demonstration — while "post-quantum cryptography" (notably lattice-based cryptosystems, now the subject of a NIST standardization competition) already offers believed-quantum-resistant alternatives that the internet can gradually migrate to. He identifies quantum simulation of actual quantum-mechanical systems (chemistry, materials science, drug design, and improved industrial processes like nitrogen fixation for fertilizer, still based on the century-old, poorly-understood Haber-Bosch process) as by far the most promising practical near-term application, potentially achievable with only ~100 high-quality logical qubits — though current circuit-depth estimates (millions of gate layers) mean today's noisy, non-error-corrected hardware isn't yet sufficient, and progress will require simultaneous advances in qubit fidelity, lower-overhead error correction/mitigation, and more efficient simulation algorithms.

Aaronson is sharply critical of quantum computing hype in the machine learning/optimization space, arguing that legitimate, provable quantum speedups for problems like optimization (via Grover's algorithm) are only quadratic (square-root), not exponential — a meaningful but modest gain, unlike the exponential speedups of Shor's algorithm or quantum simulation — and that much of the popular and commercial excitement rests on unproven "quantum machine learning" heuristics whose exponential-speedup claims have often later collapsed. He illustrates this with the story of his own undergraduate student, Ewin Tang, who was assigned to prove that a celebrated 2016 exponential quantum speedup for a Netflix-style recommendation algorithm (by Kerenidis and Prakash) was real — and instead, after a year of work, discovered and published a classical algorithm matching its performance, "de-quantizing" it, a result that subsequently led to the de-quantization of several other proposed quantum machine learning algorithms. He frames the core methodological red flag to watch for in any quantum computing claim as failure to rigorously address "how well could a classical computer do the same thing" — a question he says many hype-driven companies and journalists conspicuously avoid. He closes reflecting on meaning as found in discovering and sharing new knowledge, relationships with family/students/friends, and standing against what he considers genuinely harmful trends in the world, such as climate crisis and resurgent authoritarianism.

Excerpts