Computational Complexity and Explanations in Physics
Scott Aaronson (The University of Texas at Austin)
Distinguished Lecture Series
Thursday, January 8, 2026, 3:30 pm
Gates Center (CSE2), G20 | Amazon Auditorium
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 lecture will be streamed live on the Allen School's YouTube channel (https://www.youtube.com/@uwcse), unless otherwise noted. The link will be available on that page one hour prior to the event.
The University of Washington is committed to providing access, equal opportunity and reasonable accommodation in its services, programs, activities, education and employment for individuals with disabilities. Live captioning will be provided for this event. To request disability accommodation such as ASL interpretation, contact the Disability Services Office at least ten days in advance of the event at: (206) 543-6450/V, (206) 543-6452/TTY, (206) 685-7264 (FAX), or email at dso@u.washington.edu.