So from my casual reading of the Blog post and Paper BQP is now proven to have sets of problems that aren't efficiently solvable from classical computers?
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."
5 comments
[ 2.6 ms ] story [ 22.6 ms ] threadWhat 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...