No, we don't know that either. For all we know, we could have BQP = P: today, we don't know any algorithm in P to factor integers, but that's not a proof that it doesn't exist. If we had such a proof, as mcpherrinm…
We aren't: https://en.wikipedia.org/wiki/BQP However a quantum machine that would be capable of post-selection is described by the more powerful class PostBQP = PP, and we know that PP includes NP, so this justifies…
Yes, and that part of his comment would also imply P != NP: > Fortunately, there are problems which are NOT in BQP We don't know yet if NP \ BQP is non-empty (and neither do we know if BQP \ NP is non-empty).
No, we don't know that either. For all we know, we could have BQP = P: today, we don't know any algorithm in P to factor integers, but that's not a proof that it doesn't exist. If we had such a proof, as mcpherrinm…
We aren't: https://en.wikipedia.org/wiki/BQP However a quantum machine that would be capable of post-selection is described by the more powerful class PostBQP = PP, and we know that PP includes NP, so this justifies…
Yes, and that part of his comment would also imply P != NP: > Fortunately, there are problems which are NOT in BQP We don't know yet if NP \ BQP is non-empty (and neither do we know if BQP \ NP is non-empty).