IMG_20170524_193312 BQP - bounded-error quantum polynomial time complexity class

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.