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

Jaksot(44)

How Edison Inspired Eli Yablonovitch to Create Four World-Changing Inventions

How Edison Inspired Eli Yablonovitch to Create Four World-Changing Inventions

Eli Yablonovitch shares how Thomas Edison's approach of requiring "a thousand failed discoveries for every one that works" shaped his scientific philosophy. From solar cells to semiconductor lasers to...

14 Maalis 20253h

From Failed PhD to Nobel Prize | John Mather’s Journey to Revolutionize Astronomy

From Failed PhD to Nobel Prize | John Mather’s Journey to Revolutionize Astronomy

Join the 632nm team as we sit down with Nobel laureate Dr. John Mather. From his childhood days of building radios and telescopes to leading NASA's groundbreaking COBE mission, learn how a spectacular...

25 Helmi 20251h 53min

Hunting for Alien Artifacts | Avi Loeb

Hunting for Alien Artifacts | Avi Loeb

Join the 632nm team as we sit down with Harvard Professor Avi Loeb, in this fascinating exploration of astronomy, alien life, and the intersection of science and politics. From discussing the mysterio...

18 Helmi 20253h 37min

Are We Doomed? | Dan Aronovich on Norbert Wiener's 1948 “Cybernetics”

Are We Doomed? | Dan Aronovich on Norbert Wiener's 1948 “Cybernetics”

In this episode, the 632nm team sits down with Dan Aronovich (Data Science Decoded Podcast) to explore predictions about technology and society, starting with MIT pioneer Norbert Wiener's remarkably p...

10 Helmi 202558min

Information, Entropy & Reality | MIT Professor Seth Lloyd on Quantum Computing

Information, Entropy & Reality | MIT Professor Seth Lloyd on Quantum Computing

The 632nm team sat down with MIT professor Seth Lloyd for a mind-bending journey through quantum mechanics, information theory, and the early days of quantum computing. Lloyd shares fascinating storie...

3 Helmi 20252h 3min

From Medieval Glass to Nobel Prize | Moungi Bawendi on Mastering Quantum Dots

From Medieval Glass to Nobel Prize | Moungi Bawendi on Mastering Quantum Dots

In this episode, the 632 team interviewed Nobel laureate Moungi Bawendi, revealing his serendipitous journey to the discovery and development of quantum dots. From a summer internship at Bell Labs to ...

27 Tammi 20251h 31min

How a Vision Disorder Led to Shocking Brain Science Discoveries | Mark Bear on Neuroplasticity

How a Vision Disorder Led to Shocking Brain Science Discoveries | Mark Bear on Neuroplasticity

In this captivating episode, we explore how Mark Bear's personal experience with congenital nystagmus sparked a revolutionary career in neuroscience. Mark shares his remarkable journey from struggling...

20 Tammi 20251h 35min

The Current Reality of Quantum Computing | Yudong Cao on Deploying Quantum for Real-Life Problems

The Current Reality of Quantum Computing | Yudong Cao on Deploying Quantum for Real-Life Problems

In this eye-opening episode, former Zapata Computing CEO Yudong Chen reveals the sobering truth about quantum computing's potential impact on drug discovery and the industry's inflated market expectat...

13 Tammi 20251h 52min

Suosittua kategoriassa Tiede

rss-mita-tulisi-tietaa
tiedekulma-podcast
rss-poliisin-mieli
utelias-mieli
rss-lihavuudesta-podcast
rss-duodecim-lehti
rss-laakaripodi
rss-opeklubi
docemilia
sotataidon-ytimessa
hippokrateen-vastaanotolla
mielipaivakirja
rss-vaasan-yliopiston-podcastit
rss-mental-race
rss-ylistys-elaimille