Materials Research Laboratory

Materials Research Laboratory

skip to events

calendar tabs

  •  All 
  • Grid
  • Month
  • Week
  • Day
  • (Selected tab) Detail

Event Detail Information

Event Detail Information

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

Speaker Professor Scott Aaronson, MIT, Electrical Engineering & Computer Science
Date Oct 23, 2013
Time 4:00 pm  
Location 141 Loomis
Sponsor Physics Department
Contact Marjorie Gamel
Phone 217-333-3762
Event type Physics Colloquium
Views 5584
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.