The Quantum Walk Characteristic Polynomial Distinguishes All Strongly Regular Graphs of Prime Orde

Quantum Physics [Submitted on 2 Apr 2026] The Quantum Walk Characteristic Polynomial Distinguishes All Strongly Regular Graphs of Prime Orde Diego Roldan Let G be a strongly regular graph of prime order p with connection degree k \geq 6. We prove that the \emph{quantum walk characteristic polynomial} \chi_q(G,\lambda) \coloneqq \det(\lambda 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_p, yielding p blocks U_G^{(j)} of size k \times k. Second, we prove an explicit formula \chi_q\!\bigl(U_G^{(j)}, \lambda\bigr) = (\lambda-1)^{(k-2)/2}(\lambda+1)^{(k-2)/2} \!\left(\lambda^2 - \tfrac{2\widehat{A}_G(j)}{k}\,\lambda + 1\right), from which the Fourier coefficient \widehat{A}_G(j) is recovered as the unique real part of an eigenvalue of U_G^{(j)} distinct from \pm 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). Subjects: Quantum Physics (quant-ph); Combinatorics (math.CO) Cite as: arXiv:2604.01507 [quant-ph]   (or arXiv:2604.01507v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2604.01507 Focus to learn more Submission history From: Diego Roldan [view email] [v1] Thu, 2 Apr 2026 00:40:31 UTC (10 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-04 Change to browse by: math math.CO References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)