# Quantum Computing and the Limits of the Efficiently Computable

- Institution: CERN
- Department: CERN Colloquium
- Speaker: Scott Aaronson
- Year: 2015
- Language: English
- Subjects: Physics, Computer science
- Source: [CERN](https://videos.cern.ch/record/3008740)
- Licence: [CERN](http://copyright.web.cern.ch)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

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

0:17:45 Slide 11

0:20:36 Slide 12

0:21:04 Slide 13

0:22:41 Slide 14

0:24:12 Slide 15

0:28:04 Slide 16

0:30:22 Slide 17

0:30:56 Slide 18

0:33:01 Slide 19

0:33:10 Slide 20

0:33:14 Slide 21

0:33:23 Slide 22

0:34:49 Slide 23

0:37:59 Slide 24

0:39:03 Slide 25

0:42:10 Slide 26

0:43:43 Slide 27

0:44:13 Slide 28

0:44:20 Slide 29

0:44:31 Slide 30

0:45:01 Slide 31

0:46:50 Slide 32

0:47:22 Slide 33

0:50:18 Slide 34

0:50:37 Slide 35

0:53:49 Slide 36

0:55:26 Slide 37

0:55:44 Slide 38

0:57:41 Slide 39

1:02:34 Slide 40

1:03:47 Slide 41

1:04:01 Slide 42

1:04:10 Slide 43

1:04:39 Slide 44

## Lectures

1. [Quantum Computing and the Limits of the Efficiently Computable](https://invisiblenetwork.ai/learn/cern/3008740/bae0ce16bbd0), 1 h 24 min (CERN's player)