About
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..
0:00:00 Slide 1
0:02:03 Slide 2
0:02:14 Slide 3
0:02:19 Slide 4
0:02:25 Slide 5
0:03:49 Slide 6
0:04:45 Slide 7
0:05:00 Slide 8
0:12:47 Slide 9
0:16:42 Slide 10
The talk
Credits and licence
- Institution
- CERN
- Department
- CERN Colloquium
- Speaker
- Scott Aaronson
- Year
- 2015
- Language
- English
- Subjects
- Physics, Computer science
- Source
- CERN
- Licence
- CERN, as CERN states it. CERN's terms
- Attribution
- © CERN. CERN provides its audiovisual media free of charge for educational and informational use, credited to CERN; this lecture is shown in CERN's own player.
- Who can watch
- CERN gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed