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.)

    ... the space left to freedom is very small. ... ends are inherent in human nature and the same for all.
    Hannah Arendt (1906–1975)

    Creativity seems to emerge from multiple experiences, coupled with a well-supported development of personal resources, including a sense of freedom to venture beyond the known.
    Loris Malaguzzi (20th century)