CERN Colloquium

Quantum Computing and the Limits of the Efficiently Computable

by Scott Aaronson (MIT)

500/1-001 - Main Auditorium (CERN)

500/1-001 - Main Auditorium


Show room on map
I'll 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. I'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. I'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, I'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.
Video in CDS
Organized by

Wolfgang LERCHE PH/TH...............Tea and coffee will be served at 16h00

There is a live webcast for this event