CERN Colloquium

Quantum Computing and the Limits of the Efficiently Computable

by Scott Aaronson (MIT)

Europe/Zurich
500/1-001 - Main Auditorium (CERN)

500/1-001 - Main Auditorium

CERN

60
Show room on map
Description
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.
Poster
Video in CDS
Organized by

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

Webcast
There is a live webcast for this event