But we do know that BQP \ P is non-empty, which is what I was trying to say. In fact, factoring large integers lies in BQP \ P, and is also the basis of some commonly used encryption algorithms.

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 points out this would directly lead to a proof that P != NP (since we DO know that factoring is in NP).

Also, I don't mean to pile on, but this wasn't what you were trying to say in the paragraph I quoted: in that paragraph, you said that we just had to pick problems outside BQP to make cryptography work despite quantum computers. I don't know if that's what you had in mind, but for such an algorithm to be tractable, it should at least be in NP (nobody with a deterministic computer wants to spend an exponential amount of time establishing an SSL connection): so the mathematical statement is whether NP \ BQP is non-empty. Did I miss something?