Planar #CSP Equality Corresponds to Quantum Isomorphism – A Holant Viewpoint

Recently, Mančinska and Roberson proved that two graphs G and \ (G^ \) are quantum isomorphic if and only if they admit the same number of homomorphisms from all planar graphs. We extend this result to planar #CSP with any pair of sets \ (F\) and \ (F^ \) of real-valued, arbitrary-arity constraint functions. Graph homomorphism is the special case, in which each of \ (F\) and \ (F^ \) contains a single symmetric 0-1-valued binary constraint function. Our treatment uses the framework of planar Holant problems. To prove that quantum isomorphic constraint function sets give the same value on any planar #CSP instance, we apply a novel form of holographic transformation of Valiant, using the quantum permutation matrix \ (U\) defining the quantum isomorphism. Due to the noncommutativity of \ (U\) ’s entries, it turns out that this form of holographic transformation is only applicable to planar Holant. To prove the converse, we introduce the quantum automorphism group \ (Qut (F) \) of a set \ (F\) of constraint functions/tensors and characterize the intertwiners of \ (Qut (F) \) as the signature matrices of planar \ (Holant {F\, |\, EQ) \) quantum gadgets. Then, we define a new notion of (projective) connectivity for constraint functions and reduce their arity while preserving their inclusion in the original intertwiner space. Finally, to address the challenges posed by generalizing from 0-1 valued to real-valued constraint functions, we adapt a technique of Lovász in the classical setting for isomorphisms of real-weighted graphs to the setting of quantum isomorphisms.