[thebzax]

Unfortunately, not quite. Note from the blog post that "Since P sits in BQP which sits in PSPACE we can't prove outright any separations for BQP without separating P from PSPACE". We still haven't proven P isn't equal to PSPACE.

What BQP does efficiently solve, which classical computers do not, is a particular "Promise Problem" of the form "Input X is either of type A, B, or C, please classify it as either A or B". The promise is that I won't give you any inputs of type C, but you don't know how to tell if I break the promise.

Note also that

>> "In particular, it has been shown there exist languages A and B such that P^A=NP^A and P^B≠NP^B (Baker, Gill, and Solovay 1975). The fact the P = NP question relativizes both ways is taken as evidence that answering this question is difficult, because a proof technique that relativizes (i.e., unaffected by the addition of an oracle) will not answer the P = NP question. Most proof techniques relativize."

from https://en.wikipedia.org/wiki/Oracle_machine#Complexity_clas...

[zitterbewegung]

Yea, Its been awhile since I studied quantum computation. Thanks!