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.