Friday, 13 July 2012, 4:00 pm
\nRoom G.07, School of Informatics
\n10 Crichton Street, Edinburgh EH8 9AB
\nand afterwards for a drinks and canap\u00e9 reception<\/p>\n
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.<\/p>\n
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\u00a0 computations have observable consequences.<\/p>\n","protected":false},"excerpt":{"rendered":"
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\u00e9 reception Quantum Computing and the Limits of the Efficiently Computable I’ll discuss what can and can’t be feasibly computed according to physical law. I’ll argue that this is a fundamental question, … Continue reading Scott Aaronson Distinguished Lecture at the Informatics Forum<\/span>