Quantum Computing and the Limits of the Efficiently Computable

Scott Aaronson

How does physics limit what we can compute? This is a fundamental question, not just for mathematics and computer science, but also for physics. I'll argue that the infeasibility of certain computational problems could be taken as a physical principle, analogous to the Second Law of Thermodynamics, or the impossibility of superluminal signalling. I'll first explain what is computational complexity, and then introduce quantum computers: what they are, whether they can be built, and what's known about their capabilities and limitations. Finally, I'll touch on speculative models of computation that would go even beyond quantum computers, using (for example) closed timelike curves or nonlinear Schrodinger equations. I'll emphasize that, even if "intractable" computations occur in a physical system, what really matters is whether those computations have observable consequences.

NOTE: This is the first of two consecutive PITP events. On the following evening, Jaan Tallinn (co-creator, 'Skype', 'Kazaa'; Bluemoon software) will speak (see separate notice), and Scott Aaronson will take part in a panel discussion after Jaan's talk.

Additional resources for this talk: slides and video.