[ctchocula]

From watching a couple of Scott Aaronson videos, I was under the understanding that Grover's algorithm shows that you don't get an exponential speedup over classical Turing machines from quantum computation in general, but only for specific problems that exhibit structure such as integer factorization à la Shor's algorithm. Here's a quotation from Lecture 10 of his Quantum Computing series [1]:

"So the bottom line is that, for "generic" or "unstructured" search problems, quantum computers can give some speedup over classical computers -- specifically, a quadratic speedup -- but nothing like the exponential speedup of Shor's factoring algorithm."

[1] https://www.scottaaronson.com/democritus/lec10.html

[sdenton4]

Right. But even having some individual problem that gives an exponential speedup will break the hypothesis.