Tailed Grover Search on Cyclic Graphs

Quantum walks offer promising advantages for search algorithms over graphs. Among these, Grover’s quantum search provides a quadratic speedup with a time complexity of for unstructured search problems. Nevertheless, Grover search performs poorly on cyclic graphs due to the dynamics of the Grover walk. This study explores the behavior of Grover’s quantum walk on cyclic graphs , analyzing the probability distribution of finding the marked vertex. To analyze this behavior, we extend each vertex of the cycle by attaching semi-infinite-length paths (tails). We develop a direct analytical approach to obtain the transition matrix , whose elements are independent of . For small cycles , we observe success probabilities exceeding 0.5. In contrast, with large cycles, the effectiveness drops rapidly. We observe that the success probability approaches zero as the size of the graph increases , indicating the limitations of the quantum search in cyclic structures.