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