[maxander]

I was about to post the very same quotation.

Its not naively clear where the line is drawn between "speedup that could be obtained through clever heuristic/nondeterministic/whatever classical algorithms" and "speedup that is necessarily the domain of quantum computation." I suspect the question is a deep (open?) one in computational complexity theory.