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]]>

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.]]>

One of the more important slides from Scott Aaronson's talk at the Austin Quantum Computing meetup shows a diagram where the BQP - bounded-error quantum polynomial time complexity class - fits in with other complexity classes. BQP encompasses P -- polynomial complexity class -- but it is widely believed there are many NP-complete problems that are not in BQP. That means there are (most likely) no polynomial time algorithms for those problems, not even on quantum computers.

On the other hand, it is possible that there problems solvable by quantum computer with bounded errors in polynomial time that are not in NP. That is to say, if we can guess a possible solution, it is not possible to verify in polynomial time whether or not it is a solution. We would need a quantum computer to verify it.

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]]>

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]]>

Dr. Brian La Cour from University of Texas at Austin gave a presentation on the latest state of quantum computing to Austin's Quantum Computing meetup. In short, his points were these.

Several big companies are getting into quantum computing now: Google, Microsoft, IBM -- and there are significant differences between their approaches. Then there is D-Wave with their adiabatic quantum computer, but most researchers are skeptical whether D-Wave computer really provides a speedup over classical computers.

Meanwhile, Microsoft's approach to quantum computing is very far fetched and technologically unlikely, however, Microsoft is also creating high-level programming languages for quantum computer. Some open-source developers around the world are doing the same, and this is a good time for developers to get involved.

Speaking of community outreach, many researchers are creating games to teach the general public about quantum computing, or to give them a fun way to help researchers.

Finally, there were, as always, some unexpected questions from the audience.

More about it in my blog post.

March 2017.]]>