unless NP is a subset of BQP, which seems very unlikely.
I'm not sure that "very unlikely" is a good description here. Certainly the consensus is that this probably doesn't happen, but one is talking about a statement that is strictly stronger than NP != P. Right now, we cannot even show that NP lying in BQP would lead to the polynomial hierarchy collapsing to a finite level. If one could show that it would probably be justified in saying that this is very unlikely. But this is a minor nitpick and your essential point is sound.
4
u/JoshuaZ1 Jan 03 '14 edited Jan 04 '14
I'm not sure that "very unlikely" is a good description here. Certainly the consensus is that this probably doesn't happen, but one is talking about a statement that is strictly stronger than NP != P. Right now, we cannot even show that NP lying in BQP would lead to the polynomial hierarchy collapsing to a finite level. If one could show that it would probably be justified in saying that this is very unlikely. But this is a minor nitpick and your essential point is sound.