4
$\begingroup$

I've been using the IBM quantum experience to learn about and simulate Grover's algorithm. When they create the algorithm, they use a different set of gates depending on which oracle function $f(x)$ they want to use. In other words, they are explicitly putting in a set of gates of what they want to find before they look for it, then they get what they want -- a self-fulfilling prophecy.

How is the oracle function really implemented so that by simply looking at the choice of oracle function you don't immediately know the answer without evaluating it?

$\endgroup$
  • $\begingroup$ Isn't that the whole point of an oracle function?! You assume its existence, for theoretical purposes. If you actually had an implementation, you wouldn't need the other function/algorithm. $\endgroup$ – MSalters Jun 16 '16 at 11:46
  • 1
    $\begingroup$ Well then what's the point, how will this ever be useful when real quantum computers exist? I may have some array to search through, and decide to use Grover's algorithm. But in creating the oracle function I'd have to visit all of the bits in order to figure out how to construct the gate so that I could send my qubits through it for Grover's algorithm! $\endgroup$ – user53686 Jun 16 '16 at 11:58
5
$\begingroup$

Here's the problem Grover's algorithm helps you solve:

Input: a function $f$
Output: a value $r$ such that $f(r)=0$

If you're paying attention, you should ask how $f$ is specified. This is the oracle part: $f$ is provided as a black box. That means, given any $x$, the algorithm can evaluate $f(x)$, but the algorithm can't "look inside the black box" and see how $x$ is represented. So, the algorithm doesn't have a way to "look at the choice of oracle function"; all the algorithm can do is supply some value $x$ and ask for the value of $f(x)$, and do that over and over again.

Why is this useful? There are some situations where we can easily specify a function $f$ but it seems to be very hard to find a value $r$ such that $f(r)=0$. (In fact, in many of those situations, even knowing how $f$ is implemented doesn't seem to help.) For instance, $f$ might be the SHA256 cryptographic hashing function: given any string $x$, we can efficiently compute its hash $f(x)$, but there seems to be no way to invert it short of trying lots and lots of candidate strings to see if any of them work.

Another example is $f(x,y)=x \times y - 179...23$, where $179..23$ is some specific large number that is known to be a product of two primes but whose factorization is unknown (we don't know what the primes are) -- we probably wouldn't actually use Grover's algorithm on that specific example, but it illustrates an example where we know how to specify a function where it's still hard to find an input that maps to zero.

Take a look at https://en.wikipedia.org/wiki/One-way_function and https://en.wikipedia.org/wiki/Grover%27s_algorithm.

$\endgroup$
  • 1
    $\begingroup$ Ah ok, I had assumed that knowing how to implement f(x) meant that you necessarily knew what it evaluated to, this is what I needed to hear, thanks. $\endgroup$ – user53686 Jun 16 '16 at 22:23
  • $\begingroup$ Does Grover's algorithm specify where the function $f$ lives and how it is evaluated? Could it for example be a function I've implemented on a classical computer and then offload the difficult inversion problem to a "quantum accelerator" or would $f$ have to be implemented on this mythical accelerator to realize the benefit of grover's algorithm? If it's the latter case then does that place limitations on what $f$ can realistically be, since quantum computers can't necessarily compute all functions efficiently? $\endgroup$ – Reid Atcheson Aug 15 at 0:29
  • 1
    $\begingroup$ @ReidAtcheson, you have to have a quantum subroutine for $f$, i.e., it has to be implemented on a quantum computer (as Grover's algorithm will compute a superposition and then apply $f$ to it). It is known that $P$ is a subset of $BQP$. Assuming we can build quantum computers of arbitrary size, this should mean that any algorithm that can be implemented on a classical computer can also be implemented on a quantum computer, so this shouldn't be a serious restriction. $\endgroup$ – D.W. Aug 15 at 7:05
0
$\begingroup$

On re-reading I found the source of the confusion. in classical logic, an oracle function is introduced in the construction of an inverse function x=f_inv(y) when you have an efficient y=f(x). You don't know how the oracle produces the output f_inv(x), but you know that you can check y=f(oracle(y)).

In Grover's algorithm, the term quantum oracle operator is used for the function that checks if the "quantum oracle" is right, not for the actual oracle making the predictions.

$\endgroup$
  • 1
    $\begingroup$ I feel kind of lost here; I don't see how this answers my question. I am fine with the concept that we can check the probabilistic outcome of a quantum computer's calculation with a classical computer. Maybe if I give a concrete example it will help. I have an array of length 4 holding 4 boolean values. Only one of them is true, the other 3 are false. How do you find out which one it is? What is the exact set of matrix multiplications you use in what order to find it? $\endgroup$ – user53686 Jun 16 '16 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy