Scott Aaronson, Massachusetts Institute of Technology
April 1, 2014

Aaronson will discuss how computational complexity---the study of what can and can't be feasibly computed---has been interacting with physics in interesting and unexpected ways. He'll first give a crash course about computer science's P vs. NP problem, as well as about the capabilities and limits of quantum computers. He'll then touch on speculative models of computation that would go even beyond quantum computers, using (for example) hypothetical nonlinearities in the Schrodinger equation. Finally, he'll discuss BosonSampling---a proposal for a simple form of quantum computing, which nevertheless seems intractable to simulate using a classical computer---as well as the role of computational complexity in the black hole information puzzle.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Colloquia are held Tuesdays in Room 1412 at 4:00 pm (preceded by light refreshments at 3:30). If you have additional questions, please call 301-405-5946.