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:
“Predatory capitalism created a complex industrial system and an advanced technology; it permitted a considerable extension of democratic practice and fostered certain liberal values, but within limits that are now being pressed and must be overcome. It is not a fit system for the mid- twentieth century.”
—Noam Chomsky (b. 1928)
“Here were poor streets where faded gentility essayed with scanty space and shipwrecked means to make its last feeble stand, but tax-gatherer and creditor came there as elsewhere, and the poverty that yet faintly struggled was hardly less squalid and manifest than that which had long ago submitted and given up the game.”
—Charles Dickens (1812–1870)
“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)