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
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:
“The motive of science was the extension of man, on all sides, into Nature, till his hands should touch the stars, his eyes see through the earth, his ears understand the language of beast and bird, and the sense of the wind; and, through his sympathy, heaven and earth should talk with him. But that is not our science.”
—Ralph Waldo Emerson (1803–1882)
“To play is nothing but the imitative substitution of a pleasurable, superfluous and voluntary action for a serious, necessary, imperative and difficult one. At the cradle of play as well as of artistic activity there stood leisure, tedium entailed by increased spiritual mobility, a horror vacui, the need of letting forms no longer imprisoned move freely, of filling empty time with sequences of notes, empty space with sequences of form.”
—Max J. Friedländer (1867–1958)
“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)