%0 Journal Article
%T Time Complexity of the Oracle Phase in Grover¡¯s Algorithm
%A Ying Liu
%J American Journal of Computational Mathematics
%P 1-10
%@ 2161-1211
%D 2024
%I Scientific Research Publishing
%R 10.4236/ajcm.2024.141001
%X <span><span style=\"font-family:Verdana;\">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(<img src=\"Edit_e91da533-173e-4aec-855a-49e9d7677b31.png\" width=\"25\" height=\"25\" alt=\"\" /></span><span><span></span></span><span><span><span style=\"font-family:;\" \"=\"\"><span style=\"font-family:Verdana;\">). 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(</span><i><span style=\"font-family:Verdana;\">N</span></i><span style=\"font-family:Verdana;\">), not
O(1). As a result, the time complexity of Grover¡¯s algorithm is O(</span><i><span style=\"font-family:Verdana;\">N</span></i><span style=\"font-family:Verdana;\">),
not O(<img src=\"Edit_2947b471-afdd-4305-a8eb-32934d7c296d.png\" width=\"25\" height=\"25\" alt=\"\" /></span></span></span></span><span style=\"font-family:Verdana;\"><span style=\"font-family:Verdana;\"><span style=\"font-family:Verdana;\">). As a secondary purpose, we also attempt to restore
the time complexity of Grover¡¯s algorithm to its original form, O(<img src=\"Edit_24bb44e2-fe75-4171-b9a5-d8e67ce42ef5.png\" width=\"25\" height=\"25\" alt=\"\" /></span></span></span><span><span><span style=\"font-family:;\" \"=\"\"><span style=\"font-family:Verdana;\">), 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(</span><i><span style=\"font-family:Verdana;\">N</span></i><span style=\"font-family:Verdana;\">), the
time complexity of the Oracle Phase is still O(</span><i><span style=\"font-family:Verdana;\">N</span></i><span style=\"font-family:Verdana;\">) even after additional
preprocessing.</span></span></span></span></span>
%K Quantum Computing
%K Oracle
%K Amplitude Amplification
%K Grover¡¯s Algorithm
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=131985