Tailed Grover Search on Cyclic Graphs

Chamod Kaushalya (Department of Mathematics, University of Colombo, Colombo 03, Sri Lanka)
Mohamed Sabri (Department of Mathematics, The Open University of Sri Lanka, Nugegoda, Sri Lanka)
Anuradha Mahasinghe (Department of Mathematics, University of Colombo, Colombo 03, Sri Lanka)
Awansika Nimuthumana (Department of Mathematics, University of Colombo, Colombo 03, Sri Lanka)
Asanka Sayakkara (University of Colombo School of Computing, Colombo 07, Sri Lanka)
Kasun De Zoysa (University of Colombo School of Computing, Colombo 07, Sri Lanka)

Journal of Mathematical and Fundamental Sciences
Vol. 57 No. 3 (2026)

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.