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

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

• Note related question here: mathoverflow.net/questions/44519/… . Jul 21, 2012 at 1:37
• Thanks Steve! Yes, related (and full of interesting comments too), but not a duplicate, if I understand it correctly. My issue is not with the algorithm itself, but with the "preprocessing" as it were, or what it would take to make it useful in real life search (assuming of course we had a quantum machine to begin with), where people would throw different fs at you (different search criteria). Jul 21, 2012 at 10:38

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

• How exactly does this "uncomputation trick" work? The input to f is not a binary string, its a quantum state. If f is a measurement which will give only a probabilistic result and will destroy the state. At the end of the day U_f is the reflection matrix through the hyperplane orthogonal to w, where w is state you are searching for. The "phone book" may be represented by a permutation matrix P. If v is a phone number and w is a name then Pw = v. Given v, we wish to find w. If we had the inverse matrix P^{-1} then life would be easy, but we don't. Let R_v denote the reflection matrix around the
– user42156
Oct 31, 2013 at 19:47
• ... hyperplane orthogonal to v. This is cheap and easy to construct. Now: R_w = P^{-1} R_v P R_w is the oracle. With only P and v as input we cannot construct R_w without first constructing P^{-1} - which entirely defeats the purpose of the algorithm.
– user42156
Oct 31, 2013 at 19:47
• @skeptic: I don't understand. By assumption (this is part of the question), $f$ is a map that accepts database entries (binary strings) as input and outputs 0 or 1. $f(x)$ is 1 if and only if $x = w$, where $w$ is the string we are looking for. Nov 1, 2013 at 6:40