{"type":"rich","version":"1.0","provider_name":"Transistor","provider_url":"https://transistor.fm","author_name":"632nm","title":"Quantum Complexity: Scott Aaronson on P vs NP and the Future","html":"<iframe width=\"100%\" height=\"180\" frameborder=\"no\" scrolling=\"no\" seamless src=\"https://share.transistor.fm/e/c1c22cb1\"></iframe>","width":"100%","height":180,"duration":7309,"description":"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.\nAaronson 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.\n02:01 Early Fascination with Mathematics\n05:10 Exploring Complexity Theory\n09:10 Understanding P vs NP\n22:38 The Significance of P vs NP in Cryptography and AI\n35:04 Mapping Problems and NP Completeness\n38:37 Quantum Computing and BQP\n41:41 Shor's Algorithm and Cryptography\n45:39 Simulating Quantum Systems\n52:04 Digital vs Analog Quantum Computers\n58:18 Grover's Algorithm and Quantum Speedup\n01:02:04 Challenges in Quantum Algorithm Development\n01:06:41 Beam Splitter Networks and Quantum Sampling\n01:15:22 Quantum Computing and Information Storage\n01:17:24 Shor's Algorithm and Factoring Numbers\n01:20:56 Google's Quantum Supremacy Demonstration\n01:49:19 Quantum Money and Unclonable Cash\n01:57:15 The Future of Quantum Computing\n\nFollow us:\nTwitter: https://x.com/632nmPodcast\nSubstack: https://632nmpodcast.substack.com/\nMichael Dubrovsky: https://x.com/MikeDubrovsky\nMisha Shalaginov: https://x.com/MYShalaginov\nXinghui Yin: https://x.com/XinghuiYin\nSubscribe:\nApple Podcasts: https://podcasts.apple.com/us/podcast/632nm/id1751170269\nSpotify:...","thumbnail_url":"https://img.transistorcdn.com/GydlQqnUybBqv7mvA947eCIsz_CyOG8rEnboLv3Hs_I/rs:fill:0:0:1/w:400/h:400/q:60/mb:500000/aHR0cHM6Ly9pbWct/dXBsb2FkLXByb2R1/Y3Rpb24udHJhbnNp/c3Rvci5mbS8yOGMz/YTliMThlODIyYzYw/OGVjOWNiZWNlNmQ1/ZmQ0Ni5qcGc.webp","thumbnail_width":300,"thumbnail_height":300}