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:
“Where there is reverence there is fear, but there is not reverence everywhere that there is fear, because fear presumably has a wider extension than reverence.”
—Socrates (469–399 B.C.)
“The peculiarity of sculpture is that it creates a three-dimensional object in space. Painting may strive to give on a two-dimensional plane, the illusion of space, but it is space itself as a perceived quantity that becomes the peculiar concern of the sculptor. We may say that for the painter space is a luxury; for the sculptor it is a necessity.”
—Sir Herbert Read (1893–1968)
“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)