On Blockwise Symmetric Matchgate Signatures and Higher Domain \#CSP

Abstract

For any $n\ge 3$ and $q\ge 3$, we prove that the {\sc Equality} function $({=}_n)$ on $n$ variables over a domain of size $q$ cannot be realized by matchgates under holographic transformations. This is a consequence of our theorem on the structure of blockwise symmetric matchgate signatures. %due to the rank of the matrix form of the blockwise symmetric standard signatures, %where $({=}_n)$ is an equality signature on domain $\{0,1,\cdots ,q-1\}$. This has the implication that the standard holographic algorithms based on matchgates, a methodology known to be universal for \#CSP over the Boolean domain, cannot produce P-time algorithms for planar \#CSP over any higher domain $q\ge 3$.