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

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

The Science of Drug Discovery: Insights from Artem Evdokimov

The Science of Drug Discovery: Insights from Artem Evdokimov

In this episode, drug discovery scientist Artem Evdokimov discusses the science of pharmaceutical development, from historical breakthroughs to the current landscape. He shares insights on antibiotics...

18 Marras 20242h 50min

Optical Metatronics: Nader Engheta on Electromagnetics and Scientific Curiosity

Optical Metatronics: Nader Engheta on Electromagnetics and Scientific Curiosity

In this episode of the 632nm podcast, Nader Engheta shares his journey and experiences within the field of electromagnetics, from his early days at the University of Tehran and Caltech, to his current...

11 Marras 20241h 54min

Quantum Computing: Peter Zoller and Ignacio Cirac on the Quantum Revolution

Quantum Computing: Peter Zoller and Ignacio Cirac on the Quantum Revolution

In this episode of the 632-nanometer podcast, we explore the evolution of quantum computing with theoretical physicists and experimentalists Peter Zoller and Ignacio Cirac, two pioneers in the field. ...

4 Marras 20241h 16min

Gravitational Waves: Rainer Weiss (Nobel Prize 2017) on Laser Interferometer Observation

Gravitational Waves: Rainer Weiss (Nobel Prize 2017) on Laser Interferometer Observation

In 1916, Einstein predicted the existence of gravitational waves, however, it took almost a century for researchers to detect them. In this episode of the 632-nanometer podcast, the team has a firesid...

28 Loka 20241h 21min

Synthetic Biology: George Church on Genome Sequencing and De-Extinction

Synthetic Biology: George Church on Genome Sequencing and De-Extinction

The great George Church takes us through the revolutionary journey of DNA sequencing from his early groundbreaking work to the latest advancements. He discusses the evolution of sequencing methods, in...

22 Loka 20241h 10min

Suosittua kategoriassa Tiede

rss-mita-tulisi-tietaa
tiedekulma-podcast
rss-poliisin-mieli
utelias-mieli
rss-duodecim-lehti
radio-antro
mielipaivakirja
rss-ylistys-elaimille
rss-lihavuudesta-podcast
rss-sosiopodi
docemilia
menologeja-tutkimusmatka-vaihdevuosiin
rss-tiedetta-vai-tarinaa