Is it the case that a logarithmic gap is shown for a specific problem ? Why is this a big deal ? Doesn't Grover's algorithm already demonstrate a sqrt(n) gap ?

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

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.

> 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).

You still have the case of a list of perfect random numbers. There is nothing in the box then.

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.

Grover is sqrt(n) versus n, this paper says for their problem is 1 (constant depth) versus log n:

> In contrast, we show that this problem can be solved with certainty by a constant-depth quantum circuit