Computational Complexity & Physics Explanations by Scott Aaronson

2025-26 Allen School Distinguished Lecture Series
Title: Computational Complexity and Explanations in Physics
Speaker: Scott Aaronson (University of Texas at Austin)
Date: January 8, 2026

Abstract: The fact, or conjecture, of certain computational problems being intractable (that is, needing astronomical amounts of time to solve) clearly affects our ability to learn about physics. But could computational intractability also play a direct role in physical explanations themselves? I'll consider this question by examining three possibilities:

(1) If quantum computers really take exponential time to simulate using classical computers, does that militate toward the many-worlds interpretation of quantum mechanics, as David Deutsch famously proposed?

(2) Are certain speculative physical ideas (e.g., time travel to the past or nonlinearities in quantum mechanics) disfavored, over and above any other reasons to disfavor them, because they would lead to "absurd computational superpowers"?

(3) Do certain effective descriptions in physics work only because of the computational intractability of violating those descriptions -- as for example with Harlow and Hayden's resolution of the "firewall paradox" in black hole thermodynamics, or perhaps even the Second Law of Thermodynamics itself?

Bio: Scott Aaronson is Schlumberger Chair of Computer Science at the University of Texas at Austin, and founding director of its Quantum Information Center. He received his bachelor's from Cornell University and his PhD from UC Berkeley. Aaronson's research in theoretical computer science has focused mainly on the capabilities and limits of quantum computers. His first book, Quantum Computing Since Democritus, was published in 2013 by Cambridge University Press. He received the National Science Foundation’s Alan T. Waterman Award, the United States PECASE Award, the Tomassoni-Chisesi Prize in Physics, and the ACM Prize in Computing, and is a Fellow of the ACM and the AAAS. He blogs at "Shtetl-Optimized," https://www.scottaaronson.com/blog

This video is closed captioned.