ITA Software's Technical Seminar Series

Talk Topic: Quantum Computing and the Limits of the Efficiently Computable
Scott Aaronson, MIT
March 2, 2011

Abstract

In this talk, I'll discuss what can and can't be feasibly computed according to physical law. I'll argue that this is a fundamental question for both computer science and physics; and that the infeasibility of certain computational problems (such as NP-complete problems) could plausibly be taken as a physical principle, analogous to the Second Law or the impossibility of superluminal signalling. After reviewing some basics of computational complexity, including the P versus NP problem and the Extended Church-Turing Thesis, I'll discuss quantum computers: what they are, whether they can be scalably built, and what's known today about their capabilities and limitations. Next I'll touch on speculative models of computation that would go even beyond quantum computers, using (for example) closed timelike curves or nonlinearities in the Schrodinger equation. I'll emphasize that, even if "intractable" computations occur in a particular description of a physical system, what really matters is whether those computations have observable consequences. I'll use recent work on quantum computing with linear optics, by myself and Alex Arkhipov, to illustrate this point.

Bio

Scott Aaronson is an Associate Professor of Electrical Engineering and Computer Science at MIT. He received his PhD? in computer science from University of California, Berkeley and did postdocs at the Institute for Advanced Study and the University of Waterloo. Scott's research interests center around fundamental limits on what can efficiently be computed in the physical world. This has entailed studying quantum computing, the most powerful model of computation we have based on known physical theory. Scott's work on this subject has included limitations of quantum algorithms in the black-box model, the learnability of quantum states, and quantum versus classical proofs and advice. He also writes a popular blog (www.scottaaronson.com/blog), and is the creator of the Complexity Zoo (www.complexityzoo.com), an online encyclopedia of computational complexity theory.