Quantum Complexity: Scott Aaronson on P vs NP and the Future
632nm15 Juli 2025

Quantum Complexity: Scott Aaronson on P vs NP and the Future

In this episode of the 632nm podcast, Scott Aaronson shares his early fascination with calculus at age 11 and how “rediscovering” old mathematics led him toward groundbreaking work in complexity theory. He gives a lucid explanation of P vs NP, revealing how seemingly trivial questions about verifying solutions speak to some of the deepest unsolved problems in all of computing.

Aaronson also explores the frontiers of quantum computing, from the nuances of quantum supremacy experiments to the idea of quantum money and certified randomness. He explains how amplitudes—rather than straightforward probabilities—unlock powerful interference effects, yet still face limits imposed by measurement. The conversation concludes with a look at the future of fault-tolerant quantum computers and the possibility that we’ve finally reached the ultimate horizon of computability—unless nature has even stranger surprises in store.

02:01 Early Fascination with Mathematics
05:10 Exploring Complexity Theory
09:10 Understanding P vs NP
22:38 The Significance of P vs NP in Cryptography and AI
35:04 Mapping Problems and NP Completeness
38:37 Quantum Computing and BQP
41:41 Shor's Algorithm and Cryptography
45:39 Simulating Quantum Systems
52:04 Digital vs Analog Quantum Computers
58:18 Grover's Algorithm and Quantum Speedup
01:02:04 Challenges in Quantum Algorithm Development
01:06:41 Beam Splitter Networks and Quantum Sampling
01:15:22 Quantum Computing and Information Storage
01:17:24 Shor's Algorithm and Factoring Numbers
01:20:56 Google's Quantum Supremacy Demonstration
01:49:19 Quantum Money and Unclonable Cash
01:57:15 The Future of Quantum Computing

Follow us:

Twitter: https://x.com/632nmPodcast
Substack: https://632nmpodcast.substack.com/
Michael Dubrovsky: https://x.com/MikeDubrovsky
Misha Shalaginov: https://x.com/MYShalaginov
Xinghui Yin: https://x.com/XinghuiYin

Subscribe:

Apple Podcasts: https://podcasts.apple.com/us/podcast/632nm/id1751170269
Spotify: https://open.spotify.com/show/4aVH9vT5qp5UUUvQ6Uf6OR
Website: https://www.632nm.com

Avsnitt(44)

How Visual Experience Rewires the Brain | Mark Bear on Neuroplasticity

How Visual Experience Rewires the Brain | Mark Bear on Neuroplasticity

How does experience rewire the brain—and why is vision the ideal system for understanding neuroplasticity?In this episode, we speak with Mark Bear, MIT neuroscientist and a pioneer in the study of exp...

3 Feb 1h 55min

Snell's Law, Metasurfaces, and Metalenses  | Federico Capasso

Snell's Law, Metasurfaces, and Metalenses | Federico Capasso

How can flat surfaces shape light as powerfully as bulky lenses?In this episode, we speak with Federico Capasso, Harvard physicist and pioneer of metasurfaces, metalenses, and nanophotonics. Capasso t...

20 Jan 2h 13min

Graphene, Nanotubes, and Quantum Hall Physics | Philip Kim

Graphene, Nanotubes, and Quantum Hall Physics | Philip Kim

How do electrons behave when they’re confined to a single layer, and why do entirely new laws of physics emerge when dimensions shrink?Papers discussed in this episode:Experimental observation of the ...

6 Jan 2h 47min

Quantum Matter, Super-conductors, and Black Holes | Subir Sachdev on the SYK Model

Quantum Matter, Super-conductors, and Black Holes | Subir Sachdev on the SYK Model

What makes high-temperature superconductors and “strange metals” some of the most perplexing systems in modern physics?In this episode, we speak with Dr. Subir Sachdev: Harvard physicist and one of th...

23 Dec 20252h 34min

How to Build Fault-Tolerant Quantum Computers | Austin Fowler on Surface Codes + TQEC

How to Build Fault-Tolerant Quantum Computers | Austin Fowler on Surface Codes + TQEC

Would we get a quantum computer sooner if everything was open source?In this episode, we speak with Austin Fowler, one of the architects of quantum error correction and a pioneer of the surface code u...

9 Dec 20251h 50min

Why Syncing Atomic Clocks is Virtually Impossible | Judah Levine on UTC

Why Syncing Atomic Clocks is Virtually Impossible | Judah Levine on UTC

Why is syncing atomic clocks still one of the hardest problems in physics and engineering?In this episode, we speak with Judah Levine—legendary NIST physicist and one of the key architects of modern t...

26 Nov 20252h 4min

Can We Predict History Like the Weather? | Peter Turchin on Cliodynamics

Can We Predict History Like the Weather? | Peter Turchin on Cliodynamics

Why do civilizations rise, prosper, and then collapse? Here's what the math tells us.In this episode, we sit down with Peter Turchin, complexity scientist and founder of the field of cliodynamics, whi...

4 Nov 20251h 18min

Why Do Quantum Computers Make So Many Mistakes? | Mikhail Lukin on Quantum Error Correction

Why Do Quantum Computers Make So Many Mistakes? | Mikhail Lukin on Quantum Error Correction

You can’t copy a qubit. So how do quantum computers remember anything?In this episode, we sit down with Mikhail Lukin, Harvard physicist and co-director of the Harvard Quantum Initiative, whose lab is...

21 Okt 20251h

Populärt inom Vetenskap

p3-dystopia
pojkmottagningen
svd-nyhetsartiklar
dumma-manniskor
allt-du-velat-veta
kapitalet-en-podd-om-ekonomi
det-morka-psyket
4health-med-anna-sparre
sexet
medicinvetarna
halsorevolutionen
rss-vetenskapsradion-2
rss-ufobortom-rimligt-tvivel-2
rss-vetenskapsradion
dumforklarat
rss-spraket
hacka-livet
paranormalt-med-caroline-giertz
bildningspodden
vetenskapsradion