Jun 29, 2018 · 1h 14m · y-combinator
Scott Aaronson on Computational Complexity Theory and Quantum Computers · Y Combinator
0:00 / 0:00
▶ Watch on YouTube →
gold bands on the timeline = statements, start to end. Hover to read, click to jump. CC turns on captions
In this engaging podcast interview, computer scientist Scott Aaronson explores the core principles of quantum computing, computational complexity theory, and the deep theoretical connections between computer science and fundamental physics. He also shares insights on certified quantum randomness, AI safety, mathematical unprovability, online discourse, and his personal academic journey.
How this conversation actually went
Every chapter scored 0–10 on four independent dynamics. Hover any point for the reasoning behind the score. How this is scored →
The partners as informed peer 2.8 Guest teaching 5.5 Guest disagreement 1.4 The partners pushing back 1.2
speaking balance: gold is the partners, purple is the guest (3 minute bins)
Sharpest disagreement ▶ 53:01 Pushing back against dismissing AI risk
When Tan characterizes existential AI risk as a 'silly mental game' assuming overnight catastrophe, Aaronson rejects the dismissive framing, arguing theoretical inquiry into existential safety remains valid.
Hardest push from the partners ▶ 23:58 Challenging the sparse-copy assumptionTan directly halts Aaronson's explanation to press him on why the assumption of limited quantum state copies is necessary.
Biggest teaching moment ▶ 0:23 Correcting the standard quantum computing explanationAaronson explicitly dismantles the ubiquitous science journalism trope that quantum computers solve problems by testing all combinations simultaneously in parallel universes.
The partners hold their own ▶ 30:22 Precise formulation of P vs NPTan showcases solid theoretical grasp by providing an accurate, concise definition of P vs NP, which Aaronson immediately validates as the correct standard framing.
the scores for every segment, with the reasoning behind each
| Chapter | Topic | The partners as informed peer | Guest teaching | Guest disagreement | The partners pushing back | Why |
|---|---|---|---|---|---|---|
| Demystifying Quantum Computing Misconceptions | 2 | 7 | 2 | 1 | Tan opens by reading the core thesis from Aaronson's blog banner. Aaronson delivers an extended educational breakdown debunking the popular misconception that quantum computers simply try all answers in parallel, explaining amplitude interference instead. | |
| Quantum Computing as Fundamental Physics | 3 | 6 | 2 | 2 | Tan asks an insightful question about why quantum computing is categorized as technology rather than fundamental science like LIGO. Aaronson explains how testing quantum mechanics in the computational regime is fundamental physics, not just engineering. | |
| Certifying Randomness with Near-Term Quantum Devices | 4 | 6 | 1 | 1 | Tan interjects with relevant points on hardware limits (50 qubits) and NIST backdoors ('Allegedly random'). Aaronson details his protocol for certified randomness generation using near-term quantum devices. | |
| Shadow Tomography and Differential Privacy | 3 | 7 | 2 | 2 | Tan challenges Aaronson's theoretical premise by asking why one would assume copies are limited. Aaronson explains state tomography, gentle quantum measurement, and its surprising mathematical duality with differential privacy. | |
| The P versus NP Problem Explained | 4 | 6 | 1 | 1 | Tan demonstrates good fluency by giving a clean colloquial definition of P vs NP. Aaronson affirms it and explains polynomial time algorithms, factoring, and why proving lower bounds is notoriously hard. | |
| Bridging Computer Science and Theoretical Physics | 3 | 5 | 1 | 1 | Tan brings up their previous interview with Leonard Susskind. Aaronson describes the growing convergence between computer science and high-energy theoretical physics. | |
| The Holographic Principle and Black Hole Firewalls | 4 | 8 | 1 | 1 | Tan prompts Aaronson to bridge AdS/CFT holography with the black hole firewall paradox, offering metaphors like a fly hitting a windshield. Aaronson gives a comprehensive lecture on quantum error correcting codes in spacetime. | |
| AI Risk, Existential Threat, and Human Stupidity | 3 | 5 | 3 | 2 | Tan prompts Aaronson on AI safety and dismisses doom scenarios as a 'silly mental game'. Aaronson gently pushes back against total dismissal, arguing that foundational alignment thinking has value even if near-term human stupidity is more concerning. | |
| Busy Beaver Numbers and Limits of Mathematical Knowledge | 2 | 8 | 1 | 1 | Tan reads an audience question on Busy Beaver numbers and ZF independence. Aaronson provides a clear masterclass on computability, uncomputable growth, Gödel's incompleteness theorem, and his student's 8000-state machine. | |
| Blogging vs. Social Media Outrage Culture | 2 | 4 | 2 | 1 | Tan asks why Aaronson stays off social media while maintaining an active blog. Aaronson critiques Twitter's outrage-driven architecture in contrast to long-form discursive blogging. | |
| Advice for Young Nerds and Personal Academic Journey | 3 | 4 | 1 | 1 | Tan connects Aaronson's advice for young nerds directly to Paul Graham's 'Why Nerds Are Unpopular' essay. Aaronson shares his personal journey of leaving high school at 15 and entering Cornell at 16. | |
| Interview Conclusion and Channel Subscribe Screen | 0 | 0 | 0 | 0 | Brief outro wrap-up and thanking the guest. |
Statements from this episode (14)
Aaronson: Quantum speedups require choreographing destructive interference for wrong answers
“The entire hope of getting a speed advantage from a quantum computer is to exploit the way that amplitudes work differently. It's to try to choreograph a pattern of interference Where for each wrong answer to your computational problem, like some of the paths …”
Aaronson: Quantum error correction turned scaling into an engineering challenge
“What changed everything for most of us in the nineties was the discovery of quantum error correction, right? And quantum fault tolerance. The upshot of which was if you want to build a scalable quantum computer, you don't need to get perfect qubits. That are p…”
Aaronson: Most important quantum computing use case is simulating nature
“Maybe the most important application that we know about is just giving us this new way to simulate nature, simulate physics and chemistry, and maybe discover new drugs, discover new materials, right?”
Aaronson: Certified randomness may be quantum computing's first near-term application
“As far as I can see, may be the first application of quantum computing that people could actually be able to realize with, like, near-term devices with 50 or 60 or 70 qubits. And this application is to generate cryptographically secure random bits.”
Aaronson: Snowden documents revealed NIST pseudorandom standard was NSA-backdoored
“In fact, you know, NIST did have a standard for pseudorandom bits, which we learned a few years ago because of the Snowden documents was backdoored. By most likely by the NSA, right?”
Aaronson: Differential privacy and quantum shadow tomography share a mathematical connection
“There's a, you know, precise mathematical connection between these two problems. You can prove it. You know, it goes in both directions, and then we were actually able to use it to, you know, take work that's been done in differential privacy by people who don…”
Aaronson: P vs NP is likely this century's most important math problem
“Well, I think it's, you know a strong contender for the most important unsolved problem in math, you know, of this century.”
Aaronson: Physics and computer science have converged around statistical mechanics and optimization
“Large parts of physics and CS have been coming together in the last decades you know, partly statistical physics made this very, very deep connection between like spin glasses and condensed matter physics and combinatorial optimization problems.”
Aaronson: Holographic bulk-boundary mapping is a quantum error-correcting code
“The mapping between the bulk theory and the boundary theory in recent years, people realize that it is literally an example of one of these quantum error correcting codes that I talked, told you about before.”
Aaronson: Laws of physics allow intelligence far beyond human level
“There's no reason to believe that we are near the limits of intelligence that are allowed by the laws of physics, right? And so, eventually, sure, you know, it could be possible to produce beings that are much more intelligent than we are.”
Aaronson: Human stupidity is a bigger near-term threat than superintelligent AI
“When I think about, like, the future of civilization, you know, let's say the next 20 years, the next 50 years, I tend to worry less about super intelligence than I do about super stupidity. You know, I tend to worry about, you know, killing ourselves off or y…”
Aaronson: Busy Beaver grows faster than any computable function
“The amazing thing about this function is that it increases more rapidly than any function that could be calculated by any computer program. This is provable, right? So you know, it is a ridiculously quickly growing function.”
Aaronson: Set theory can only determine finitely many Busy Beaver values
“Axioms of set theory can only determine finitely many values of this function. Okay, so in some sense, beyond a certain point, you know, the standard rules of mathematics cannot even prove what are the values of this function.”