[adrianN]

Quantum computers can't solve NP complete problems any better than classical computers as far as we know. You can at best hope for polynomial speedups. That is the scientific consensus, I don't know what weight of opinion you're talking about.

[ikeboy]

He seems to be misunderstanding Scott as claiming that no quantum computers will beat classical ones (even for factoring and the like), whereas Scott only makes the claim for NP-complete problems.

[mhurd]

Yes. That is right. I misunderstood Scott. He makes sense. BQP covers factorisation which is different to NPC.

That said, it is unclear how far Adiabatic notions will take us but it seems there are limits there too with respect to the spectral issues.