Those are all about problems started in terms of querying some blackbox oracle. Whether the speedup holds up with a concrete instantiation of the blackbox is unknown.
Could you elaborate? You can search for the solution to any computational problem for which there is a binary function f(n) mapping candidates n to {0,1}, depending on whether it's a solution. Here, f is the "oracle", but it's only playing the role of representing the problem you're trying to solve, and I believe an f exists for all problems in NP.
If your set of solutions has N candidates, this requires only O(sqrt(N)) evaluations rather than O(N). If that function takes exponential time, then there is still of course no polynomial-time solution, but the quadratic speedup holds.
There are some NP problems for which we know techniques that are faster than brute-force search, but even then we can generally speed up those techniques in the same way.
(I guess you could worry that for every problem there is an unknown techniques for classically speeding things up over brute-force search, but I thought this was known to be false, and in any case is unrelated to your point. I'm not an expert though.)
But is there actually a proof that these are improvements over all possible classical algorithms or are they just improvements over the best currently known classical algorithms?
