2005/06/14 by Anupam Gupta, A. S. Gupta, Gupta, A. S. +6
Computer Science · Physics and Astronomy · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Management and Algorithms #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0506105
6 pages, No Figure, Latex 2e
arxiv created 2005/06/14 · openalex publication_date 2005/06/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Grover's search algorithm searches a database of N unsorted items in O(√(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).