Abstract
Let G be a strongly regular graph of prime order p with connection degree k ≥ 6. We prove that the \emph{quantum walk characteristic polynomial} χ_q(G,λ) 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 _p, yielding p blocks U_G^(j) of size k × k. Second, we prove an explicit formula χ_q(U_G^(j), λ) = (λ-1)^(k-2)/2(λ+1)^(k-2)/2 (λ² - 2A_G(j)/kλ + 1), from which the Fourier coefficient A_G(j) is recovered as the unique real part of an eigenvalue of U_G^(j) 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).