Tailed Grover Search on Cyclic Graphs
DOI:
https://doi.org/10.5614/j.math.fund.sci.2026.57.3.2Keywords:
complexity, cyclic graphs, quantum algorithms, quantum walks, stationary state analysisAbstract
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.
References
Portugal, R., Quantum Walks and Search Algorithms, vol. 19, Springer, 2013.
Hidary, J.D., Quantum Computing: An Applied Approach, vol. 1, Springer, 2021.
Higuchi, Y., Sabri, M. & Segawa, E., Toward Fixed Point and Pulsation Quantum Search on Graphs Driven by Quantum Walks with In- and Out-flows: A Trial to the Complete Graph, Quantum Studies: Mathematics and Foundations, 10(3), pp. 307-316, 2023.
Sabri, M. & Sahabandu, C.W., Tailed Quantum Search on Cyclic Graphs, in Proceedings of the International Research Conference of the Open University of Sri Lanka, 2024.
Tanaka, H., Sabri, M. & Portugal, R., Spatial Search on Johnson Graphs by Discrete-time Quantum Walk, Journal of Physics A: Mathematical and Theoretical, 55(25), 255304, 2022.
Higuchi, Y. & Segawa, E., A Dynamical System Induced by Quantum Walk, Journal of Physics A: Mathematical and Theoretical, 52(39), 395202, 2019.
Venegas-Andraca, S.E., Quantum Walks: A Comprehensive Review, Quantum Information Processing, 11(5), pp. 1015-1106, 2012.
Ishikawa, A., Kubota, S. & Segawa, E., A Convergence Time of Grover Walk on Regular Graph to Stationary State, arXiv preprint arXiv:2210.08420, 2022.
Mahasinghe, A., Wang, J.B. & Wijerathna, J.K., Quantum Walk-based Search and Symmetries in Graphs, Journal of Physics A: Mathematical and Theoretical, 47(50), 505301, 2014.
Hosaka, T. & Segawa, E., Pulsation of Quantum Walk on Johnson Graph, arXiv preprint arXiv:2411.01468, 2024.
Kato, T., A Short Introduction to Perturbation Theory for Linear Operators, Springer Science & Business Media, 2012.
Ambainis, A., Kempe, J. & Rivosh, A., Coins Make Quantum Walks Faster, arXiv preprint quant-ph/0402107, 2004.
Shenvi, N., Kempe, J. & Whaley, K.B., Quantum Random-walk Search Algorithm, Physical Review A, 67(5), 052307, 2003.
Adedoyin, A., Ambrosiano, J., Anisimov, P., Casper, W., Chennupati, G., Coffrin, C., Djidjev, H., Gunter, D., Karra, S., Lemons, N., et al., Quantum Algorithm Implementations for Beginners, arXiv preprint arXiv:1804.03719, 2018.
Mahasinghe, A., Izaac, J.A., Wang, J.B. & Wijerathna, J.K., Phase-modified CTQW Unable to Distinguish Strongly Regular Graphs Efficiently, Journal of Physics A: Mathematical and Theoretical, 48(26), 265301, 2015.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Journal of Mathematical and Fundamental Sciences
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
