> We give an example of an adiabatic quantum algorithm for searching that matches the optimal quadratic speedup obtained by Grover’s search algorithm. This example demonstrates that the ‘quantum local search’, which is implicit in the adiabatic evolution, is truly non-classical in nature from a computational viewpoint.
[0]: https://people.eecs.berkeley.edu/~vazirani/pubs/adiabatic.pd...
(Note that, strictly speaking, the best classical algorithms are already sub-exponential, i.e., faster than C^n for all C, so there’s no such thing as an “exponential speedup”.)
Quotes from Scott Aaronson about the adiabatic factorization of 143: “It doesn’t ‘know’ about the special mathematical properties of factoring that make that an easy problem for quantum computers. In contrast to Shor’s algorithm, we have no reason to think it would be able to factor 10,000 digit numbers in less than astronomical amounts of time.… I didn’t see any evidence that quantum behaviour played a role in finding the factors of 143.”
https://www.newscientist.com/article/dn21699-controversial-q...