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:

    “Slavery is founded in the selfishness of man’s nature—opposition to it, is [in?] his love of justice.... Repeal the Missouri compromise—repeal all compromises—repeal the declaration of independence—repeal all past history, you still can not repeal human nature. It still will be the abundance of man’s heart, that slavery extension is wrong; and out of the abundance of his heart, his mouth will continue to speak.”
    —Abraham Lincoln (1809–1865)

    “If we remembered everything, we should on most occasions be as ill off as if we remembered nothing. It would take us as long to recall a space of time as it took the original time to elapse, and we should never get ahead with our thinking. All recollected times undergo, accordingly, what M. Ribot calls foreshortening; and this foreshortening is due to the omission of an enormous number of facts which filled them.”
    —William James (1842–1910)

    “Combining paid employment with marriage and motherhood creates safeguards for emotional well-being. Nothing is certain in life, but generally the chances of happiness are greater if one has multiple areas of interest and involvement. To juggle is to diminish the risk of depression, anxiety, and unhappiness.”
    —Faye J. Crosby (20th century)