Recently, Manč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 \(\mathcal {F}\) and \(\mathcal {F}^{\prime }\) of real-valued, arbitrary-arity constraint functions. Graph homomorphism is the special case, in which each of \(\mathcal {F}\) 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 \(\mathcal {U}\) defining the quantum isomorphism. Due to the noncommutativity of \(\mathcal {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(\mathcal {F})\) of a set \(\mathcal {F}\) of constraint functions/tensors and characterize the intertwiners of \(Qut(\mathcal {F})\) as the signature matrices of planar \(\text{Holant}{\mathcal {F}\,|\,\mathcal {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.
Recently, Manč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 (\mathcal {F}) and (\mathcal {F}^{\prime }) of real-valued, arbitrary-arity constraint functions. Graph homomorphism is the special case, in which each of (\mathcal {F}) 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 (\mathcal {U}) defining the quantum isomorphism. Due to the noncommutativity of (\mathcal {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(\mathcal {F})) of a set (\mathcal {F}) of constraint functions/tensors and characterize the intertwiners of (Qut(\mathcal {F})) as the signature matrices of planar (\text{Holant}{\mathcal {F},|,\mathcal {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.
We study the complexity of counting (weighted) planar graph homomorphism problem Pl-GH(M) parametrized by an arbitrary symmetric non-negative real valued matrix M. For matrices with pairwise distinct diagonal values, we prove a complete dichotomy theorem: Pl-GH(M) is either polynomial-time tractable, or #P-hard, according to a simple criterion. More generally, we obtain a dichotomy whenever every vertex pair of the graph represented by M can be separated using some planar edge gadget. A key question in proving complexity dichotomies in the planar setting is the expressive power of planar edge gadgets. We build on the framework of Mančinska and Roberson to establish links between \textit{planar} edge gadgets and the theory of the \textit{quantum automorphism group} Qut(M). We show that planar edge gadgets that can separate vertex pairs of M exist precisely when Qut(M) is \emph{trivial}, and prove that the problem of whether Qut(M) is trivial is undecidable. These results delineate the frontier for planar homomorphism counting problems and uncover intrinsic barriers to extending nonplanar reduction techniques to the planar setting.
Valiant's Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets F and G of tensors (a.k.a. constraint functions or signatures) are related by a \emph{holographic transformation}, then F and G are \emph{Holant-indistinguishable}, i.e., every tensor network using tensors from F, resp. from G, contracts to the same value. Xia (ICALP 2010) conjectured the converse of the Holant theorem, but a counterexample was found based on \emph{vanishing} signatures, those which are Holant-indistinguishable from 0. We prove two near-converses of the Holant theorem using techniques from invariant theory. (I) Holant-indistinguishable F and G always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their GLq-orbit closures intersect. (II) We show that vanishing signatures are the only true obstacle to a converse of the Holant theorem. As corollaries of the two theorems we obtain the first characterization of homomorphism-indistinguishability over graphs of bounded degree, a long standing open problem, and show that two graphs with invertible adjacency matrices are isomorphic if and only if they are homomorphism-indistinguishable over graphs with maximum degree at most three. We also show that Holant-indistinguishability is complete for a complexity class \textbf{TOCI} introduced by Lysikov and Walter, and hence hard for graph isomorphism.
We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant problems. Compared to counting constraint satisfaction problems (#CSP), it is a refinement with a more explicit role for the constraint functions. Both graph homomorphism and #CSP can be viewed as special cases of Holant problems. We prove complexity dichotomy theorems in this framework. Our dichotomy theorems apply to local constraint functions, which are symmetric functions on Boolean input variables and evaluate to arbitrary real or complex values. We discover surprising tractable subclasses of counting problems, which could not easily be specified in the #CSP framework. When all unary functions are assumed to be free (Holant∗ problems), the tractable ones consist of functions that are degenerate, or of arity at most two, or holographic transformations of Fibonacci gates. When only two special unary functions, the constant zero and constant one functions, are assumed to be free (Holantc problems), we further identify three special families of tractable cases. Then we prove that all other cases are #P-hard. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations.
Holant problems are a family of counting problems parameterized by sets of algebraic-complex-valued constraint functions and defined on graphs. They arise from the theory of holographic algorithms, which was originally inspired by concepts from quantum computation. Here, we employ quantum information theory to explain existing results about holant problems in a concise way and to derive two new dichotomies: one for a new family of problems, which we call Holant+, and, building on this, a full dichotomy for Holantc. These two families of holant problems assume the availability of certain unary constraint functions---the two pinning functions in the case of Holantc, and four functions in the case of Holant+---and allow arbitrary sets of algebraic-complex valued constraint functions otherwise. The dichotomy for Holant+ also applies when inputs are restricted to instances defined on planar graphs. In proving these complexity classifications, we derive an original result about entangled quantum states.
Mančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph. Atserias et al. [JCTB'19] proved that quantum isomorphism is undecidable in general, which motivates the study of its relaxations. In the classical setting, Roberson and Seppelt [ICALP'23] characterized the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism in terms of equality of homomorphism counts from an appropriate graph class. The NPA hierarchy, a noncommutative generalization of the Lasserre hierarchy, provides a sequence of semidefinite programming relaxations for quantum isomorphism. In the quantum setting, we show that the feasibility of each level of the NPA hierarchy for quantum isomorphism is equivalent to equality of homomorphism counts from an appropriate class of planar graphs. Combining this characterization with the convergence of the NPA hierarchy, and noting that the union of these classes is the set of all planar graphs, we obtain a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the use of quantum groups. Moreover, this homomorphism indistinguishability characterization also yields a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.
We investigate quantum relaxations of two key decision problems in computer science: the constraint satisfaction problem (CSP) and the structure isomorphism problem. CSP asks whether a homomorphism exists between two relational structures, while structure isomorphism seeks an isomorphism between them. In recent years, it has become increasingly apparent that many special cases of CSP can be reformulated in terms of the existence of perfect classical strategies in non-local games, a key topic of study in quantum information theory. These games have allowed us to study quantum advantage in relation to many important decision problems, such as the k-colouring problem, and the problem of solving binary constraint systems. Abramsky et al. (2017) have shown that all of these games can be seen as special instances of a non-local CSP game. Moreover, they show that perfect quantum strategies in this CSP game can be viewed as Kleisli morphisms of a graded monad on the category of relational structures, which they dub the quantum monad. In this way, the quantum monad provides a categorical characterisation of quantum advantage for the non-local CSP game. In this work we solidify and expand the results of Abramsky et al., answering several of their open questions. Firstly, we compare the definition of quantum graph homomorphisms arising from this work with an earlier definition of the concept due to Mančinska and Roberson and show that there are graphs which exhibit quantum advantage under one definition but not the other. Our second contribution is to extend the results of Abramsky et al. which only hold in the tensor product framework of quantum mechanics to the commuting operator framework. Next, we study a non-local structure isomorphism game, which generalises the well-studied graph isomorphism game. We show how the construction of the quantum monad can be refined to provide categorical semantics for quantum strategies in this game. This results in a category where morphisms coincide with quantum homomorphisms and isomorphisms coincide with quantum isomorphisms.