Prof. Scott Aaronson - Quantum Computing and the Limits of the Efficiently Computable

Scott Aaronson, Associate Professor of Electrical Engineering and Computer Science at MIT, delivered his inaugural lecture entitled "Quantum Computing and the Limits of the Efficiently Computable".
Mr Aaronson discusses what can and can't be feasibly computed according to physical law. He argues that this is a fundamental question, not only for mathematics and computer science, but also for physics; and that the infeasibility of certain computational problems (such as NP-complete problems) could plausibly be taken as a physical principle, analogous to the Second Law or the impossibility of superluminal signalling.
He first explains the basics of computational complexity, including the infamous P versus NP problem and the Extended Church-Turing Thesis. Then he discusses quantum computers: what they are, whether they can be scalably built, and what's known today about their capabilities and limitations. Lastly, he touches on speculative models of computation that would go even beyond quantum computers, using (for example) closed timelike curves or nonlinearities in the Schrodinger equation.
Mr Aaronson emphasises that, even if "intractable" computations occur in a particular description of a physical system, what really matters is whether those computations have observable consequences.
Biography:
Scott Aaronson is an Associate Professor of Electrical Engineering and Computer Science at Massachusetts Institute of Technology (MIT). He received his PhD in computer science from University of California, Berkeley and did postdocs at the Institute for Advanced Study and the University of Waterloo.
Scott's research interests center around fundamental limits on what can efficiently be computed in the physical world. This has entailed studying quantum computing, the most powerful model of computation we have based on known physical theory.
He writes a blog (www.scottaaronson.com/blog), and is the creator of the Complexity Zoo (www.complexityzoo.com), an online encyclopedia of computational complexity theory. He was the recipient of NSF's Alan T Waterman Award for 2012.

[@jmb56]

Very interesting talk, especially the part about the laws of physics seeming to prohibit polynomial time algorithms for np problems. And his style? who cares, his passion for the subject comes across and this is enough to keep me listening

[@Serfuzz]

He's been at Berkeley. That's their way to pronounce punctuation marks..

[@joshuacook2]

Where was this given?

[@n0ZzeL]

okay

[@catsupchutney]

Wonderful talk. If he took voice coaching, he'd earn good money from his lectures.

[@millec60]

He is not a very good speaker. Obviously knows his stuff, but not a good speaker

[@elemereladrosinger979]

Dear Scott It is embarrasing to tell you : you MUST urgently get a good professional tutor to train you how to speak in public : you endlessly keep saying "you know", "OK" and "a-a-a-a-...", and gesticulate with both hands in rather silly ways ... It is indeed a great pity, and it can be corrected with some effort on your part ... And trust me, you MUST correct it urgently ... Elemer E Rosinger

[@ArumesYT]

I certainly prefer his style over all those "speakers" who just read their entire lecture from paper. Plenty of examples of those on this channel. They need help more urgently than Scott Aaronson.