[Solved]: How is the oracle function for Grover's Search algorithm obtained?

Problem Detail: 

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?

Asked By : Steven Grigsby

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59728

3.2K people like this

 Download Related Notes/Documents