Quantum Computing and the Limits of the Efficiently Computable - 2011 Buhl Lecture

Scott Aaronson, an expert in the realm of computational complexity theory and the founder of ComplexityZoo.com online encyclopedia of computational complexity theory delivered Carnegie Mellon University's 2011 Buhl Lecture.

In his lecture titled "Quantum Computing and the Limits of the Efficiently Computable," Aaronson discusses what quantum computers are, whether they can be built on a large scale, and what's known today about their capabilities and limitations. He goes beyond quantum computers to touch on speculative models of computation, including closed time-like curves and nonlinearities in the Schrodinger equation — an equation that describes how the quantum state of a physical system changes in time.

An associate professor of electrical engineering and computer science at the Massachusetts Institute of Technology, Aaronson's work on the subject of quantum computing has included limitations of quantum algorithms in the black-box model, the learnability of quantum states, and quantum versus classical proofs and advice. He writes a popular blog (www.scottaaronson.com/blog).

For more on the Buhl Lectures, visit: http://www.cmu.edu/physics/seminars-and-events/buhl-lectures/

Category:

Education

Tags:

• Carnegie
• Mellon
• University
• Buhl
• lecture
• Scott
• Aaronson
• quantum
• computing

[yp06407012]

Scott Aaronson starts at 4:30

[carl14706]

love how giddy he gets when he talks about P and NP. really shows his enthusiasm for the field

[bustybossoms]

okay, ummkay, okay, mmkay

[ACogloc]

@55t1

What Aaronson is saying is that your exponential run time task is not done in linear time because of a sort of massively parallel calculation, but because of the essence of the quantum computer: you shoot the electrons just once and get ONE task done, not many tasks simultaneously.

Think about a computer automatically counting in the base of the size of your input. You don't have to try many solutions (e.g SAT values combinations), all of them are checked in one calculation.

[55t1]

He obviously knows this stuff, he appears to have spent years researching this, but I don't understand the part where he says that QC cannot be thought of as parallel computing. If an quantum system sits in an state of superposition of all possible solutions, it is not only parallel, it is massively parallel, even hyper-parallel.

[Blankname101]

This was interesting.

[Kricardose]

I am very happy to see the vidoe Scott Aaronson, an expert in the realm of computational complexity theory and the founder after you give this

[bebeheuy]

I Love The Video Scott Aaronson, an expert in the realm of computational complexity theory and the founder It Can Increase My Knowledge

[Mjhond]

Steady I Really Like This Video Scott Aaronson, an expert in the realm of computational complexity theory and the founder

[Paumonsu]

mmmmm...okay

[MinNyeAccount]

@MarthamadaySaamanu new to me!

[reshad1]

Jazz hands..OK?... Actually sarcasm aside..this was a very interesting talk thank you Scott :)