Quantum Rigidity of Cayley Graphs: An Algebraic Approach via Schur Ring

Source abstract

A Cayley graph Γ=Cay(G,S) is a graphical regular representation (GRR) of G if Aut(Γ)=G acts regularly. We call Γ a quantum rigid if its quantum automorphism group also satisfies QAut(Γ)=G. We prove that a Cayley graph whose coherent (two-dimensional Weisfeiler–Leman) closure is thin is quantum rigid. For Cayley graphs this closure is exactly the S-ring generated by S. The direct in-group refinement algorithm tests thinness in polynomial time; with comparison sorting of the refinement signatures, one round costs O(|G|2log|G|) and at most |G|−1 strict refinement rounds occur, giving the explicit worst-case bound O(|G|3log|G|). Thus thinness supplies a polynomial-time sufficient test for the absence of quantum symmetry, rather than a complexity-theoretic certificate in the NP sense. We also prove that, for a GRR, thinness is equivalent to Schurity of its coherent closure. Hence non-quantum-rigidity of a GRR forces a non-Schurian coherent closure, although the converse is not asserted. Every GRR over a Schur group is therefore quantum rigid. Moreover, a WL-thin Cayley graph is determined up to ordinary isomorphism by its quantum-isomorphism class. Finally, an exact, reproducible census of 193,694 connected labelled Cayley graph instances (one for each symmetric connection set, without quotienting by graph isomorphism) in twenty-four finite groups finds no GRR that fails WL-thinness. The accompanying Python 3.14 program contains the group constructions, refinement procedure, exact GRR test and machine-readable output.