×

Periodicity of Grover walks on complete graphs with self-loops. (English) Zbl 1439.05207

Summary: We investigate periodicity of Grover walks on complete graphs with a self-loop at each vertex. We study an evolution matrix by using algebraic methods. Then we find a periodic behaviour; the probability amplitude vector at each vertex gets back to initial state after some steps. It is shown that the Grover walk on complete graphs on \(n\) vertices with a self-loop at each vertex is periodic with period \(2n\).

MSC:

05C81 Random walks on graphs
15A18 Eigenvalues, singular values, and eigenvectors
81Q99 General mathematical topics and methods in quantum theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aharonov, D.; Ambainis, A.; Kempe, J.; Vazirani, U., Quantum walks on graphs, (Proc. 33rd STOC (2001), ACM), 50-59 · Zbl 1323.81020
[2] Bednarska, M.; Grudka, A.; Kurzyński, P.; Łuczak, T.; Wójcik, A., Quantum walks on cycles, Phys. Lett. A, 317, 21, 21-25 (2003) · Zbl 1056.81049
[3] Manouchehri, K.; Wang, J., Physical Implementation of Quantum Walks (2014), Springer-Verlag · Zbl 1278.81010
[4] Kempe, J., Quantum random walks - an introductory overview, Contemp. Phys., 44, 4, 307-327 (2003)
[5] Štefaňák, M.; Jex, I.; Kiss, T., Recurrence and Pólya number of quantum walks, Phys. Rev. Lett., 100, Article 20501 pp. (2008)
[6] Chandrashekar, C. M., Fractional recurrence in discrete-time quantum walk, Cent. Eur. J. Phys., 8, 6, 979-988 (2010)
[7] Dukes, P. R., Quantum state revivals in quantum walks on cycles, Results Phys., 4, 189-197 (2014)
[8] Konno, N.; Shimizu, Y.; Takei, M., Periodicity for the Hadamard walk on cycles, Interdiscip. Inf. Sci., 23, 1, 1-8 (2017) · Zbl 1468.81030
[9] Higuchi, Y.; Konno, N.; Sato, I.; Segawa, E., Periodicity of the discrete-time quantum walk on a finite graph, Interdiscip. Inf. Sci., 23, 1, 75-86 (2017) · Zbl 1470.81043
[10] Kubota, S.; Segawa, E.; Taniguchi, T.; Yoshie, Y., Periodicity of Grover walks on generalized Bethe trees, Linear Algebra Appl., 554, 371-391 (2018) · Zbl 1392.05102
[11] Yoshie, Y., Periodicity of Grover walks on distance-regular graphs, Graphs Comb., 35, 1305-1321 (2019) · Zbl 1431.05138
[12] Saito, K., Periodicity for the Fourier quantum walk on regular graphs
[13] Godsil, C., State transfer on graphs, Discrete Math., 312, 129-147 (2012) · Zbl 1232.05123
[14] Kendon, V. M.; Tamon, C., Perfect state transfer in quantum walks on graphs, J. Comput. Theor. Nanosci., 8, 422-433 (2011)
[15] Frank, S., Principles of Random Walk (1964), Springer-Verlag · Zbl 0119.34304
[16] Knight, F. B., On the random walk and Brownian motion, Trans. Am. Math. Soc., 103, 2, 218-228 (1962) · Zbl 0279.60057
[17] Wojnar, R., Random walk, diffusion and wave equation, Acta Phys. Pol. B, 44, 1067-1084 (2013) · Zbl 1371.60078
[18] Tritt, T. M., Thermal Conductivity: Theory, Properties, and Applications (2004), Plenum Publishers
[19] Golosov, A. O., Localization of random walks in one-dimensional random environments, Commun. Math. Phys., 92, 491-506 (1984) · Zbl 0534.60065
[20] Furusawa, A.; van Loock, P., Quantum Teleportation and Entanglement: A Hybrid Approach to Optical Quantum Information Processing (2011), Wiley-VCH-Verlag
[21] Portugal, R., Quantum Walks and Search Algorithms (2013), Springer-Verlag · Zbl 1275.81004
[22] Scherer, W., Mathematics of Quantum Computing: An Introduction (2019), Springer-Verlag · Zbl 1429.81005
[23] Grover, L. K., A fast quantum mechanical algorithm for database search, (Proc. 28th STOC (1996), ACM), 212-219 · Zbl 0922.68044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.