3 ms·

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 un

• jessriedel 7y ago
  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. https://quantumcomputing.stackexchange.com/questions/2166/grovers-algorithm-and-its-relation-to-complexity-classes https://quantumcomputing.stackexchange.com/questions/2166/gr... 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. https://link.springer.com/chapter/10.1007/978-3-540-78773-0_67 https://link.springer.com/chapter/10.1007/978-3-540-78773-0_... (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.)
  • voxic11 7y ago
    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?
    • jessriedel 7y ago
      That's what my last two sentences address.