IMG_20170524_203441 Scott Aaronson at the Austin Quantum Computing meetup
On May 24, 2017 Scott Aaronson gave a talk at the Austin Quantum Computing meetup. The talk reiterated many important points and themes from Scott Aaronson's blog in the same entertaining, inspiring, and humorous way.
Scott Aaronson started his speech by considering alternative forms of computing, based on exotic physics models, and asked if they violate the Extended Church-Turing thesis (roughly speaking, can they be fundamentally faster than conventional computers). Turns out that relativity computer or Zeno's computer, which would be capable of doing that, can't exist in the physical world. But quantum computing appears to violate the Extended Church-Turing thesis. That's not to say that it can solve NP-complete problems in polynomial time. It also doesn't mean that it tries every answer simultaneously (this fallacy is one of Scott's major peeves), but rather uses interference to get the right answer.
He also examined for what kinds of problems quantum computers can achieve speedup over classical computers (hint: not NP-complete problems, but rather a special complexity class called BQP), and whether achieving speedup should even be the most important application of quantum computing (Scott thinks not).
Then he talked about how could P != NP manifest in the physical world, and connected this to D-Wave's adiabatic quantum computer.
Here is a link to my complete blog post about Scott Aaronson's speech at the Austin Quantum Computing meetup