I was about to post the very same quotation.<p>Its not naively clear where the line is drawn between &quot;speedup that could be obtained through clever heuristic&#x2F;nondeterministic&#x2F;whatever classical algorithms&quot; and &quot;speedup that is <i>necessarily</i> the domain of quantum computation.&quot;  I suspect the question is a deep (open?) one in computational complexity theory.