Spectral Methods for the Complexity of Planar Graph Homomorphisms

We explore the frontier beyond the recently discovered barrier represented by the \emph{quantum automorphism group} $qut(M)$ in the classification theory of planar graph homomorphisms $PlGH(M)$. We show that analyzing the spectral relations of $M$ can prove #P-hardness when traditional vertex separation and domain-reduction methods with planar edge gadgets provably fail due to the $\text{qut}(M)$ barrier. We prove two criteria of #P-hardness for $PlGH(M)$: a spectral criterion and a determinant criterion. It is known that the core problem for the classification of $PlGH(M)$ for nonnegative matrices $M$ is for positive definite entry-wise positive matrices. We use the spectral criterion to show that $PlGH(M)$ is #P-hard for all circulant matrices of prime order $q\ge 3$, while for $q=2$ it is precisely the matchgate case and is P-time computable by the FKT algorithm (for planar perfect matching). We also prove a complexity dichotomy for $\text{PlGH}$ problems defined by tensor products of 2 by 2 matrices. This gives a complete complexity classification for this class of matrices, and the FKT algorithm together with a holographic transformation is \emph{universal}—every $PlGH(M)$ is either (1) P-time computable over all graphs, or (2) #P-hard in general but P-time computable over planar graphs, or (3) #P-hard over planar graphs; furthermore, $PlGH(M)$ in (2) consists of precisely those computable by FKT with a holographic transformation.