Combinatorial necessary conditions for regular graphs to induce periodic quantum walks

Abstract

We derive combinatorial necessary conditions for discrete-time quantum walks defined by regular mixed graphs to be periodic. If the quantum walk is periodic, all the eigenvalues of the time evolution matrices must be algebraic integers. Focusing on this, we explore which ring the coefficients of the characteristic polynomials should belong to. On the other hand, the coefficients of the characteristic polynomials of $\eta$-Hermitian adjacency matrices have combinatorial implications. From these, we can find combinatorial implications in the coefficients of the characteristic polynomials of the time evolution matrices, and thus derive combinatorial necessary conditions for mixed graphs to be periodic. For example, if a $k$-regular mixed graph with $n$ vertices is periodic, then $2n/k$ must be an integer. As an application of this work, we determine periodicity of mixed complete graphs and mixed graphs with a prime number of vertices.

arXiv comment20 pages, 5 tables. The revised version adds Section 6 and beyond. Further discussion on strongly regular graphs and several well-known families of distance regular graphs is provided

References in corpus (7)

• Spectral Properties of Complex Unit Gain Graphs
• Quantum state revivals in quantum walks on cycles
• Spectra of Perfect State Transfer Hamiltonians on Fractal-Like Graphs
• Periodicity of quantum walks defined by mixed paths and mixed cycles
• Quantum walks defined by digraphs and generalized Hermitian adjacency matrices
• Order from chaos in quantum walks on cyclic graphs
• Periodicity for the Fourier quantum walk on regular graphs

Cited by in corpus (2)

• Periodicity and perfect state transfer of Grover walks on quadratic unitary Cayley graphs
• State transfer in Grover walks on unitary and quadratic unitary Cayley graphs over finite commutative rings