3
$\begingroup$

We know that the Grover algorithm outputs a marked item. Now we want to know the locations of all items. I can't find any paper to solve this problem.

$\endgroup$
1
5
$\begingroup$

Grover's search returns a uniform superposition of all marked items. So, yes, in your last step, you measure it and find a random sample out of that set. If you want others, just repeat and you'll get another random sample.

If you want to be a bit more directed, you can explicitly exclude any items you've previously found by unmarking them in your oracle step.

$\endgroup$
1
  • $\begingroup$ Repeat will take at least $M$ more 'experiments', so the $O(\sqrt{N/M}$ becomes $O(\sqrt{NM})$, where $M$ stands for the number of right answers and $N$ stands for the total numbers of items to be searched. So unmark might be the only choice now... I think. $\endgroup$
    – narip
    Jun 30 at 14:21

Your Answer

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

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