Grover's algorithm uses an oracle function $f(x) \to \{0,1\}$ to find the location of a single marked element from an unordered database of $2^n$ elements with high probability. As part of an assignment I am supposed to design a variant of the algorithm that finds all of the $t$ marked elements ($t$ is known). I want to do this by repeating the following procedure $t$-times:
- Use Grover's algorithm to find any marked element $x$.
- Delete $x$ from the data base.
I think my solution is correct, but I am still not feeling comfortable with quantum computing. In particular, I am unsure of how one could implement the removal step since it would mean to manipulate the function $f$.
Can anyone clarify?
Asked By : Michael Nett
Answered By : Michael Nett
After discussing the problem with some people from my institute that work on quantum computing, it turns out that one can augment the oracle to not provide elements that have already been found in previous iterations of the search. The trick is to modify Grover's algorithm as follows:
Say, we already know that 2 is an answer (from a previous iteration). After using the oracle to invert the phase of the marked elements within Grover's algorithm, we apply another operation that inverses the phase of the known answers again (thus cancelling the previous inversion for answers that are already known). Accordingly, the inversion about the mean in Grover's algorithm will not amplify the amplitude of these states.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13513
0 comments:
Post a Comment
Let us know your responses and feedback