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

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

Published 2005-06-14Version 1

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)$.