[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.