Quantum Complexity: Scott Aaronson on P vs NP and the Future
632nm15 Heinä 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

Tämä jakso on lisätty Podme-palveluun avoimen RSS-syötteen kautta eikä se ole Podmen omaa tuotantoa. Siksi jakso saattaa sisältää mainontaa.

Jaksot(62)

Reinforcement Learning and Quantum Decoding | Vlad Sivak Google Quantum AI

Reinforcement Learning and Quantum Decoding | Vlad Sivak Google Quantum AI

How can reinforcement learning help quantum computers learn from their own errors?In this episode, Vlad Sivak, researcher at Google Quantum AI, joins us to discuss how reinforcement learning can impro...

3 Marras 1h 41min

Where Does Intelligence Live? | Michael Levin on Evolution, AI, and Platonic Space

Where Does Intelligence Live? | Michael Levin on Evolution, AI, and Platonic Space

What is intelligence, and where does it come from?Watch Part 1 here: https://youtu.be/t6EFV2gSSmg?si=VIztbK2CM5Nwj7QAIn this episode, Michael Levin, professor of biology at Tufts University, returns t...

20 Loka 1h 28min

AI, Cancer Vaccines, and the Future of Personalized Medicine | Sid Sijbrandij on GitLab + Biotech

AI, Cancer Vaccines, and the Future of Personalized Medicine | Sid Sijbrandij on GitLab + Biotech

Can AI help design personalized cancer vaccines?Visit Future of Cancer Care Today: https://sijbrandijfoundation.org/fcctIn this episode, we speak with Sid Sijbrandij, founder of GitLab who went "Found...

6 Loka 1h 40min

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 Syys 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 Syys 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 Elo 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 Elo 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 Heinä 3h 26min

Suosittua kategoriassa Tiede

rss-mita-tulisi-tietaa
utelias-mieli
tiedekulma-podcast
rss-hereilla
hippokrateen-vastaanotolla
rss-lihavuudesta-podcast
rss-duodecim-lehti
docemilia
university-of-eastern-finland
radio-antro
rss-poliisin-mieli
rss-ranskaa-raakana
rss-vaasan-yliopiston-podcastit
rss-jyvaskylan-yliopisto
rss-tiedetta-vai-tarinaa
rss-sosiopodi
rss-ylistys-elaimille