Date/Time
Date(s) - 13/07/2012
4:00 pm - 7:00 pm
Location
SHSC Conference & Training Centre, Edinburgh
An invitation to a Distinguished Lecture at the Informatics Forum …
Scott Aaronson (MIT)
Friday, 13 July 2012, 4:00 pm
Room G.07, School of Informatics
10 Crichton Street, Edinburgh EH8 9AB
and afterwards for a drinks and canapé reception
Quantum Computing and the Limits of the Efficiently Computable
Abstract
I’ll discuss what can and can’t be feasibly computed according to physical law. I’ll argue that this is a fundamental question, not only for mathematics and computer science, but also for 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. I’ll first explain the basics of computational complexity, including the infamous P versus NP problem and the Extended Church-Turing Thesis. Then I’ll discuss quantum computers: what they are, whether they can be scalably built, and what’s known today about their capabilities and limitations.
Lastly, 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.
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. 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. He is the recipient of NSF’s Alan T. Waterman Award for 2012.
