We've known since the 90s that there is no exponential quantum advantage for solving non-structured black-box problems. The resolution of the Aaronson–Ambainis conjecture tells us the same result holds even if the algorithms only need to get most inputs correct.
