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

Det här avsnittet är hämtat från ett öppet RSS-flöde och publiceras inte av Podme. Det kan innehålla reklam.

Avsnitt(59)

Building Quantum Computers at Semiconductor Scale | John Martinis on Qolab + Superconducting Qubits

Building Quantum Computers at Semiconductor Scale | John Martinis on Qolab + Superconducting Qubits

What does it actually take to build a quantum computer that can scale to millions of qubits?Learn more about Qolab here: https://qolab.ai/In this episode, we speak with John Martinis, recipient of the...

22 Sep 2h 4min

Diffraction Limit, Microscopy, and Cell Biology | Eric Betzig on Super-Resolution Microscopy

Diffraction Limit, Microscopy, and Cell Biology | Eric Betzig on Super-Resolution Microscopy

What does a cell actually look like when you can see its molecules in action?In this episode, we speak with Nobel Prize-winning scientist Eric Betzig, whose pioneering work in super-resolution microsc...

8 Sep 2h 40min

The Hybrid Architecture Behind Quantum Computing | Yonatan Cohen Quantum Machines CTO

The Hybrid Architecture Behind Quantum Computing | Yonatan Cohen Quantum Machines CTO

Why is controlling a quantum hardware becoming one of the biggest challenges in scaling quantum computers?In this episode, we speak with Yonatan Cohen, co-founder and CTO of Quantum Machines, a compan...

18 Aug 1h 52min

How DNA Sequencing Was Discovered By Accident | Walter Gilbert on Biogen, Industry, and Art

How DNA Sequencing Was Discovered By Accident | Walter Gilbert on Biogen, Industry, and Art

How did we go from knowing almost nothing about genes to sequencing the entire human genome?In this episode, we speak with Nobel Prize-winning molecular biologist Walter Gilbert, whose discoveries hel...

4 Aug 2h 8min

How Bacteria Evolved Rotary Motors | Michael Manson

How Bacteria Evolved Rotary Motors | Michael Manson

How do bacteria power one of the most sophisticated molecular machines in nature?In this episode, we speak with Dr. Michael Manson, one of the pioneers of bacterial motility research, whose nearly 50-...

21 Juli 3h 26min

The Atomic Physics Behind Neutral Atom Computers | Mark Saffman

The Atomic Physics Behind Neutral Atom Computers | Mark Saffman

Why are so many companies betting on neutral atoms to build the first useful quantum computers?In this episode, we speak with Mark Saffman, professor at the University of Wisconsin–Madison and one of ...

30 Juni 1h 23min

Silicon Photonics and the Future of AI Scaling | John Bowers

Silicon Photonics and the Future of AI Scaling | John Bowers

Why are some of the world's largest technology companies betting on silicon photonics?In this episode, we speak with John Bowers, professor at UC Santa Barbara and one of the pioneers of silicon photo...

16 Juni 1h 39min

Bioelectricity, Morphogenesis, and Two-Headed Worms | Michael Levin

Bioelectricity, Morphogenesis, and Two-Headed Worms | Michael Levin

How can a flatworm regenerate a complete head after being cut in half?In this episode, we speak with Michael Levin, developmental biologist and director of the Allen Discovery Center at Tufts Universi...

2 Juni 1h 27min

Populärt inom Vetenskap

dumma-manniskor
p3-dystopia
rss-mottagningen
allt-du-velat-veta
angestpodden
rss-ronden
kapitalet-en-podd-om-ekonomi
det-morka-psyket
rss-ufobortom-rimligt-tvivel
svd-nyhetsartiklar
4health-med-anna-sparre
bildningspodden
rss-vetenskapsradion
rss-geopodden-2
sexet
rss-vetenskapsradion-2
rss-odla
ufo-sverige
rss-spraket
ideer-som-forandrar-varlden