Modified Grover's search algorithm for the cases where the number of solutions is known

Gupta, A. S.; Gupta, M.; Pathak, A.

Modified Grover's search algorithm for the cases where the number of solutions is known

Authors

Gupta, A. S.

Gupta, M.

Pathak, A.

Description

Grover's search algorithm searches a database of $N$ unsorted items in $O(\sqrt{N/M})$ steps where $M$ represents the number of solutions to the search problem. This paper proposes a scheme for searching a database of $N$ unsorted items in $O(logN)$ steps, provided the value of $M$ is known. It is also shown that when $M$ is unknown but if we can estimate an upper bound of possible values of $M$, then an improvement in the time complexity of conventional Grover's algorithm is possible. In that case, the present scheme reduces the time complexity to $O(MlogN)$.
6 pages, No Figure, Latex 2e