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:
“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)
“I would have broke mine eye-strings, cracked them, but
To look upon him, till the diminution
Of space had pointed him sharp as my needle;
Nay, followed him till he had melted from
The smallness of a gnat to air, and then
Have turned mine eye and wept.”
—William Shakespeare (1564–1616)
“... 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)