I have been trying to understand what could be the advantage of using Grover algorithm for searching in an arbitrary unordered database D(key, value) with N values instead of a classical search.
I assumed that the oracle function is a function f(key)=y, where y is the index of the corresponding value in the classical database.
My problem is related to the oracle. The oracle circuit has to be modified for each search is performed in the database because the key is specified in the oracle. Let's assume this is a negligible operation for simplicity.
Supposing that the oracle circuit has to be calculated classically, it would require to produce a circuit which behaves like the function f(key)=y. This function would be obtained in at least O(N) steps (except for some special cases). The oracle function circuit has to be recalculated each time a database entry is being modified/added/removed, with a cost of O(N).
I don't know if I have to consider a quantum database for obtaining a real advantage or not (this and the unreliability of quantum results convinced me is not a very good idea, but it is just conjecture).
So, where is considered the complexity for building the oracle? Have I misunderstood something?
Is "The oracle function circuit has to be recalculated each time a database entry is being modified/added/removed, with a cost of O(N)" a wrong assumption?