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

arXiv2212.03335MaRDI QIDQ6419786FDOQ6419786

Authors: Jin-Yi Cai, Ben Young 

Publication date: 6 December 2022

Abstract: Recently, Manv{c}inska and Roberson proved that two graphs $G$ and $G^{\prime }$ 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 $mathcalF$ and $mathcal{F}^{\prime }$ of real-valued, arbitrary-arity constraint functions. Graph homomorphism is the special case where each of $mathcalF$ and $mathcal{F}^{\prime }$ 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 $mathcalU$ defining the quantum isomorphism. Due to the noncommutativity of $mathcalU$'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$(mathcalF)$ of a set of constraint functions $mathcalF$, and characterize the intertwiners of Qut$(mathcalF)$ as the signature matrices of planar Holant$(mathcalF,|,mathcalEQ)$ quantum gadgets. Then we define a new notion of (projective) connectivity for constraint functions and reduce arity while preserving the quantum automorphism group. Finally, to address the challenges posed by generalizing from 0-1 valued to real-valued constraint functions, we adapt a technique of Lov'asz in the classical setting for isomorphisms of real-weighted graphs to the setting of quantum isomorphisms.

This page was built for publication: Planar #CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6419786)