Grover's Algorithm - Extension To Space With Multiple Targets

Extension To Space With Multiple Targets

If, instead of 1 matching entry, there are k matching entries, the same algorithm works but the number of iterations must be π(N/k)1/2/4 instead of πN1/2/4. There are several ways to handle the case if k is unknown. For example, one could run Grover's algorithm several times, with

 \pi \frac{N^{1/2}}{4}, \pi \frac{(N/2)^{1/2}}{4},
\pi \frac{(N/4)^{1/2}}{4}, \ldots

iterations. For any k, one of iterations will find a matching entry with a sufficiently high probability. The total number of iterations is at most

which is still O(N1/2). It can be shown that this could be improved. If the number of marked items is k, where k is unknown, there is an algorithm that finds the solution in queries. This fact is used in order to solve the collision problem.

Read more about this topic:  Grover's Algorithm

Famous quotes containing the words extension, space and/or multiple:

    Where there is reverence there is fear, but there is not reverence everywhere that there is fear, because fear presumably has a wider extension than reverence.
    Socrates (469–399 B.C.)

    At first thy little being came:
    If nothing once, you nothing lose,
    For when you die you are the same;
    The space between, is but an hour,
    The frail duration of a flower.
    Philip Freneau (1752–1832)

    ... the generation of the 20’s was truly secular in that it still knew its theology and its varieties of religious experience. We are post-secular, inventing new faiths, without any sense of organizing truths. The truths we accept are so multiple that honesty becomes little more than a strategy by which you manage your tendencies toward duplicity.
    Ann Douglas (b. 1942)