Computational Complexity and Explanations in Physics
Scott Aaronson (University of Texas at Austin)
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?
Readings:
S. Aaronson, "Why Philosophers Should Care About Computational Complexity"
https://arxiv.org/abs/1108.1791
Sections 2, 3, 8, 10
D. Harlow and P. Hayden, "Quantum Computation vs. Firewalls"
https://arxiv.org/abs/1301.4504
**************RSVP BY OCTOBER 2**************