Grover, L.K. (1996) A Fast Quantum Mechanical Algorithm for Database Search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC ‘96), New York, 22-24 May 1996, 212-219.
https://doi.org/10.1145/237814.237866

has been cited by the following article:

• TITLE: Time Complexity of the Oracle Phase in Grover’s Algorithm

  AUTHORS: Ying Liu

  KEYWORDS: Quantum Computing, Oracle, Amplitude Amplification, Grover’s Algorithm

  JOURNAL NAME: American Journal of Computational Mathematics, Vol.14 No.1, March 25, 2024

  ABSTRACT: Since Grover’s algorithm was first introduced, it has become a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The original application was the unstructured search problems with the time complexity of O(). In Grover’s algorithm, the key is Oracle and Amplitude Amplification. In this paper, our purpose is to show through examples that, in general, the time complexity of the Oracle Phase is O(N), not O(1). As a result, the time complexity of Grover’s algorithm is O(N), not O(). As a secondary purpose, we also attempt to restore the time complexity of Grover’s algorithm to its original form, O(), by introducing an O(1) parallel algorithm for unstructured search without repeated items, which will work for most cases. In the worst-case scenarios where the number of repeated items is O(N), the time complexity of the Oracle Phase is still O(N) even after additional preprocessing.