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 clas

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 https://www.scottaaronson.com/democritus/lec10.html