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.