Quantum Computing and the Limits of the Efficiently Computable

Scott Aaronson (MIT)
Event Date and Time: 
Wed, 2012-02-15 19:30 - 21:30
St. John's College - 2111 Lower Mall (Fairmont Lounge)
Local Contact: 
Philip Stamp
Intended Audience: 

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.

Website development by Checkmark Media. Designed by Armada.

a place of mind, The University of British Columbia

Faculty of Science
Department of Physics and Astronomy
6224 Agricultural Road
Vancouver, BC V6T 1Z1
Tel 604.822.3853
Fax 604.822.5324

Emergency Procedures | Accessibility | Contact UBC | © Copyright The University of British Columbia