Back to Listing

Physics Colloquium: "Quantum Computing and the Limits of Efficient Computation "

Event Type
Physics Department
141 Loomis
Oct 23, 2013   4:00 pm  
Professor Scott Aaronson, MIT, Electrical Engineering & Computer Science
Originating Calendar
Physics - Colloquium

I'll discuss places where computational complexity theory---the study of what can and can't be feasibly computed---has interacted with fundamental physics in interesting and unexpected ways in recent years.  I'll first give a crash course about computer science's P versus NP problem, as well as about quantum computers: what they are, whether they can be scalably built, and what's known today about their capabilities and limitations.  Then 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.  Finally, I'll discuss BosonSampling---a proposal for a rudimentary form of linear-optical quantum computing, which nevertheless seems intractable to simulate using a classical computer---as well as the role of computational complexity in the black hole firewall debate.

link for robots only