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 on the selfishness of man’s nature—opposition to it on his love of justice. These principles are in eternal antagonism; and when brought into collision so fiercely as slavery extension brings them, shocks and throes and convulsions must ceaselessly follow.”
    —Abraham Lincoln (1809–1865)

    “True spoiling is nothing to do with what a child owns or with amount of attention he gets. he can have the major part of your income, living space and attention and not be spoiled, or he can have very little and be spoiled. It is not what he gets that is at issue. It is how and why he gets it. Spoiling is to do with the family balance of power.”
    —Penelope Leach (20th century)

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