Name: Quantum Computing and the Limits of the Efficiently Computable
Start: 2015-01-15T16:30:00+01:00
End: 2015-01-15T17:30:00+01:00
Location: CERN

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.

Organised by

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

Webcast

There is a live webcast for this event

Quantum Computing and the Limits of the Efficiently Computable

by Scott Aaronson (MIT)

500/1-001 - Main Auditorium

CERN