2 ms·

Only if you assume that the classical counterparts of it are optimal. There's no proof of that.

• 21 8y ago
  For Groover algorithm, which is applied to the problem of search you can prove that there is no classical algorithm faster than O(N) - looking at each item in the worst case scenario.
  • wolfgke 8y ago
    > For Groover algorithm, which is applied to the problem of search you can prove that there is no classical algorithm faster than O(N) - looking at each item in the worst case scenario. Assuming that you cannot "look into the black box of the oracle" (i.e. we are only allowed to use a given oracle to evaluate an item at an index).
    • 21 8y ago
      You still have the case of a list of perfect random numbers. There is nothing in the box then.
      • wolfgke 8y ago
        But perfect random numbers cannot be evaluated by an algorithm. Evaluating the black box/oracle must be done in a run of Grovers's algorithm.
        • deleted 8y ago
          [deleted]