CERN Colloquium

Quantum Computing and the Limits of the Efficiently Computable

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

by Scott Aaronson (MIT)

Thursday 15 Jan 2015, 16:30 → 17:30 Europe/Zurich

500/1-001 - Main Auditorium (CERN)

500/1-001 - Main Auditorium

CERN

400

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.

Organised by

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

Webcast

There is a live webcast for this event

Choose timezone

Quantum Computing and the Limits of the Efficiently Computable

by Scott Aaronson (MIT)

500/1-001 - Main Auditorium

CERN

Share this page

Direct link

Social networks

Calendaring