ArXiv · 2026
The Quantum Walk Characteristic Polynomial Distinguishes All Strongly Regular Graphs of Prime Orde ↗
Let G be a strongly regular graph of prime order p with connection degree k ≥ 6. We prove that the quantum walk characteristic polynomial χ_q(G,λ) coloneqq det(λI - U_G), where U_G is the coined quantum walk operator on G, completely determines G up to isomorphism within the class of strongly regular graphs of the same order. The proof proceeds in three steps. First, we show that U_G block-diagonalizes under the discrete Fourier transform over Zₚ, yielding p blocks U_G⁽ʲ⁾ of size k × k. Second, we prove an explicit formula χ_qbigl(U_G⁽ʲ⁾, λbigr) = (λ-1)^((k-2)/2)(λ+1)^((k-2)/2) (λ² - 2widehatA_G(j)/k λ+ 1), from which the Fourier coefficient widehatA_G(j) is recovered as the unique real part of an eigenvalue of U_G⁽ʲ⁾ distinct from ± 1. Third, the inverse discrete Fourier transform recovers the connection set S of G, and Turner's theorem (1967) identifies G up to isomorphism. As a consequence, graph isomorphism is decidable in polynomial time within this class using the quantum walk spectrum, without resorting to the general quasi-polynomial algorithm of Babai (2016).
Try inveni