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(45)

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

From Failed Project to 40 Million Eye Scans: David Huang on the Birth of OCT

From Failed Project to 40 Million Eye Scans: David Huang on the Birth of OCT

Dr. David Huang shares the remarkable journey of how a failed laser surgery project during his MD-PhD studies at MIT led to the invention of Optical Coherence Tomography (OCT), now used in over 40 mil...

6 Tammi 20251h 29min

Origins of Life | Anna Wang on Artificial Cells and Nano-Robots

Origins of Life | Anna Wang on Artificial Cells and Nano-Robots

Origins of life researcher Anna Wang takes us on a fascinating journey through the latest theories about how life began, revealing why Darwin's "warm little ponds" are making a comeback and how ocean ...

30 Joulu 20241h 15min

The Future of Fusion | Dennis Whyte on Nuclear Fusion and MIT Plasma Science

The Future of Fusion | Dennis Whyte on Nuclear Fusion and MIT Plasma Science

MIT Professor Dennis Whyte's path to becoming a fusion energy pioneer began with an unlikely source - a Ripley's Believe It or Not comic strip he read as a teenager in rural Saskatchewan. The comic de...

23 Joulu 20242h 51min

Origins of Life | Jack Szostak on Basement Experiments to Nobel Prize-Winning Discoveries

Origins of Life | Jack Szostak on Basement Experiments to Nobel Prize-Winning Discoveries

Nobel laureate Jack Szostak takes us on a fascinating journey through his remarkable scientific career, from conducting dangerous chemistry experiments in his basement as a curious child to making gro...

16 Joulu 20241h 26min

The God Particle | Christoph Paus on Higgs Boson, CERN, and CMS

The God Particle | Christoph Paus on Higgs Boson, CERN, and CMS

Professor Christoph Paus, a key figure in the discovery of the Higgs Boson at CERN's Large Hadron Collider, discusses his journey in high-energy physics, the challenges of leading large international ...

9 Joulu 20241h 42min

Cold Atoms: Mikhail Lukin on Quantum Optics and Neutral Atom Computing

Cold Atoms: Mikhail Lukin on Quantum Optics and Neutral Atom Computing

In this episode, Harvard Professor Mikhail Lukin discusses his pioneering work in quantum computing using neutral atoms. He shares the journey from his early work in quantum optics and electromagnetic...

2 Joulu 202450min

Einstein Was Wrong: John Clauser on Bell's Theorem and the Nature of Reality

Einstein Was Wrong: John Clauser on Bell's Theorem and the Nature of Reality

In this episode, we sit down with Nobel laureate John Clauser to discuss his experiments from the early 1960’s, testing Bell's inequalities and quantum entanglement. Clauser shares the story of how, a...

25 Marras 20242h 9min

Suosittua kategoriassa Tiede

tiedekulma-podcast
rss-mita-tulisi-tietaa
rss-poliisin-mieli
docemilia
radio-antro
rss-duodecim-lehti
rss-ammamafia
rss-sosiopodi
utelias-mieli
ihanat-ipanat
mielipaivakirja
filocast-filosofian-perusteet
rss-bios-podcast
rss-tiedetta-vai-tarinaa