IMG_20170524_195449 Scott Aaronson's research on quantum computing and black holes
Scott Aaronson ended his talk with a true cliffhanger when he mentioned his last year's resarch paper connecting quantum computation to the black hole firewall problem. He briefly mentioned it and said that there wasn't enough time to discuss it at this presentation. All he said was what is on this slide: "More broadly: We've been able to use ideas from quantum computing theory to get new insights into condensed-matter physics, quantum gravity, and even classical computer science (e.g. "quantum proofs for classical theorems")."
So after the presentation me and some other people asked him about it. He pointed us to more information about the black hole firewall / quantum computing connection paper on his blog.
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