> It's possible that quantum optimizers could be exponentially faster than existing optimization techniques by evaluating multiple minima simultaneously.
Is there any known quantum algorithm that gives a speedup over classical algorithms? I don't mean "call Grover as a subroutine" during your standard classical optimization algorithm.
I don't understand this question? Grover's algorithm is itself faster than classical search algos.
It is as of yet unknown whether quantum computers are more powerful than classical computers; there is no proof that BQP is strictly bigger than P. There is oracle separation but that's not the same thing.
that's what everyone says but imagine 10 years from now someone proves BQP < P. since that proof will entail a ptime reduction you'll immediately have a ptime shor's and etc.
Is there any known quantum algorithm that gives a speedup over classical algorithms? I don't mean "call Grover as a subroutine" during your standard classical optimization algorithm.