Speakers

Back to Listing

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

Event Type
Seminar/Symposium
Topic
physics
Sponsor
Physics Department
Location
141 Loomis
Date
Oct 23, 2013   4:00 pm  
Speaker
Professor Scott Aaronson, MIT, Electrical Engineering & Computer Science
Contact
Marjorie Gamel
E-Mail
mgamel@illinois.edu
Phone
217-333-3762
Views
5585
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