Among the basic algorithms of quantum computations Lov Grover's result on quantum search stands out, both in regards to its intrinsic interest, and for its undisputable elegance.

Grover's algorithm enables one to search an unsorted database of N elements in $O(N^{1/2})$ time, which is pretty remarkable.

However, I do have one perplexity, which perhaps someone here can dissipate.

The starting point of Grover is this one (from the wiki entry):

Consider an unsorted database with N entries. The algorithm requires an N-dimensional state space H, which can be supplied by n=log2 N qubits. Consider the problem of determining the index of the database entry which satisfies some search criterion.

Let f be the function which maps database entries to 0 or 1, where f(ω)=1 if and only if ω satisfies the search criterion. We are provided with (quantum black box) access to a subroutine in the form of a unitary operator, $U_{f}$, which acts as:

$U_{f}|\omega \rangle =-|\omega \rangle$

and

$U_{f}|x \rangle = |x \rangle $ $\forall x \neq > \omega$

Now, my problem with Grover is this:

IF you have your unitary oracle, THEN you can find your needle in the haystack. But, suppose a real life scenario, in which you have your database and you have your $f$ above as given input data.

You still need a preliminary step to create your operator, FROM $f$.

If there is a simple way to write a program which carries out this preliminary step, you are cool. But if this step turned out to be expensive, you must add this cost in the total bill (and that in turn might erode your quantum benefits).

Assuming you have $f$, how complicated is it to produce $U_{f}$?