causal

Efficient Computability Depends on Physics

While Turing's notion of computability is invariant to the details of physics — classical or quantum, any number of spatial dimensions — the notion of efficient (polynomial-time) computability is more physics-dependent, and changing the laws from classical to quantum appears to enlarge what is computable in polynomial time, which is what led David Deutsch to invent quantum computing.

causalpending

Speaker

Scott Aaronson

Evidence Quote

“once we ask about efficient computability, polynomial-time computability... changing the laws of physics from classical to quantum, that does seem to be enough to enlarge what is computable in polynomial time”

Source

99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity— Sean Carroll's Mindscape
Created: 6/13/2026, 12:26:25 AM

Your notes

Loading notes...