How much does a quantum oracle to find a needle in a haystack really cost?

Question

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}$?

Answer 1

$U_f$ is easy to create from a circuit that computes $f$. (I'm assuming you have a circuit that computes $f$. If you have a Turing machine, convert it to a circuit in the standard way.)

Now given a circuit (using AND, OR, NOT gates) of G gates that computes $f$, i.e., accepts a binary string $x$ as input and outputs the 1 bit answer $f(x)$, this can be converted to a quantum circuit that uses a Toffoli gate and NOT gates to simulate the AND and OR gates. This will create a unitary matrix that on input $|x\rangle|0^k\rangle$ gives you $|f(x)\rangle|\text{junk}(x)\rangle$. Using the standard "uncomputation trick", you can now get a circuit that performs $|x\rangle|b\rangle \mapsto |x\rangle |b \oplus f(x)\rangle$. Finally, if you put in the state $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ for $|b\rangle$, you'll get a circuit that exactly implements $U_f$.

Note that this circuit for $U_f$ has increased the size and depth of the original circuit for $f$ by only a constant factor. Thus if $f$ had an efficient circuit, then so does $U_f$.