Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

How is the output of Grover's algorithm useful if the result is required to use the oracle? If we already know the desired state, what's the point of using the algorithm?

So can you give me a concrete example of an oracle function. For example if the indexed items in a Grover search were, for example arbitrary patterns, what would the corresponding oracle function look like? Lets make the example more concrete. Each pattern is the image of a face and we want to see if an unknown face is located within pattern set. Classically our search algorithm is a correlation algorithm (e.g. Kendall-tau, rank correlation etc.). What would the analogue of this be for a quantum search?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

There is a difference between finding a solution and recognizing a solution. Oracle can recognize the solution or solve a particular instance of the problem but cannot give you the solution for complete problem. Or in other words, oracles gives you a part of solution and you may need to consult oracle a number of times to get the complete solution. Oracle also may be thought as a library function (as in programming languages) which will give you solution for one instance of a problem, and the real cost of computation is measured by how many times you call the function and not the inherent complexity of the function itself which is taken as black box. For example, lets say we have a oracle for a function $f(x) = x^2$, on presenting this oracle with a pair $(a,b)$ it will tell whether $b^2 = a$ or not. In this case time complexity is taken as how many time you need to consult the oracle to get the desired result.

More concrete example can be taken from oracle for verifying if the number if prime. Lets say we want to find the first prime number $p: a < p <b, a < b \in Z^+$. The problem has different complexity when you are given access to the oracle and when you are not given.

Physical example of an oracle: lets say our problem is to determine the angle between the floor and the wall which may not be necessarily $90^\circ$ to it. All you can do is throw a ball which will go elastic collision on the wall and return back. You have control of the angle you throw and you can note the angle it came back. Each throwing of a ball can be compared with the calling of oracle function and the constraint on the angle of the returning ball (reflection,which gives you a hint on the orientation of the wall) can be considered an oracle. The number of times you need to repeat the throwing of ball to get the orientation with desired accuracy may be considered as the complexity of the problem relative to the oracle.

share|improve this answer

The oracle doesn't need to know the desired state in order to verify whether a given state is the desired state.

Grover's algorithm can be applied to NP-complete problems. This is the set of problems for which there is no known way to generate a solution in polynomial time, but a given solution can be in recognized in polynomial time.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.