Mančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they are homomorphism indistinguishable over the class of planar graphs. Atserias et al. [JCTB'19] proved that quantum isomorphism is undecidable in general. The NPA hierarchy gives a sequence of semidefinite programming relaxations of quantum isomorphism. Recently, Roberson and Seppelt [ICALP'23] obtained a homomorphism indistinguishability characterization of the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism. We prove a quantum analogue of this result by showing that each level of the NPA hierarchy of SDP relaxations for quantum isomorphism of graphs is equivalent to homomorphism indistinguishability over an appropriate class of planar graphs. By combining the convergence of the NPA hierarchy with the fact that the union of these graph classes is the set of all planar graphs, we are able to give a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the use of the theory of quantum groups. This homomorphism indistinguishability characterization also allows us to give a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.
Mančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they are homomorphism indistinguishable over the class of planar graphs. Atserias et al. [JCTB'19] proved that quantum isomorphism is undecidable in general. The NPA hierarchy gives a sequence of semidefinite programming relaxations of quantum isomorphism. Recently, Roberson and Seppelt [ICALP'23] obtained a homomorphism indistinguishability characterization of the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism. We prove a quantum analogue of this result by showing that each level of the NPA hierarchy of SDP relaxations for quantum isomorphism of graphs is equivalent to homomorphism indistinguishability over an appropriate class of planar graphs. By combining the convergence of the NPA hierarchy with the fact that the union of these graph classes is the set of all planar graphs, we are able to give a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the use of the theory of quantum groups. This homomorphism indistinguishability characterization also allows us to give a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.
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 introduce a nonlocal game that captures and extends the notion of graph isomorphism. This game can be won in the classical case if and only if the two input graphs are isomorphic. Thus, by considering quantum strategies we are able to define the notion of quantum isomorphism. We also consider the case of more general non-signalling strategies, and show that such a strategy exists if and only if the graphs are fractionally isomorphic. We prove several necessary conditions for quantum isomorphism, including cospectrality, and provide a construction for producing pairs of non-isomorphic graphs that are quantum isomorphic. We then show that both classical and quantum isomorphism can be reformulated as feasibility programs over the completely positive and completely positive semidefinite cones respectively. This leads us to considering relaxations of (quantum) isomorphism arrived at by relaxing the cone to either the doubly nonnegative (DNN) or positive semidefinite (PSD) cones. We show that DNN-isomorphism is equivalent to the previous defined notion of graph equivalence, a polynomial-time decidable relation that is related to coherent algebras. We also show that PSD-isomorphism implies several types of cospectrality, and that it is equivalent to cospectrality for connected 1-walk-regular graphs. Finally, we show that all of the above mentioned relations form a strict hierarchy of weaker and weaker relations, with non-singalling/fractional isomorphism being the weakest. The techniques used are an interesting mix of algebra, combinatorics, and quantum information.
Quantum graph homomorphisms, introduced by Mančinska and Roberson, form a natural quantum relaxation of classical graph homomorphisms. Since this relaxation may create new comparabilities, it could in principle collapse antichains and other order-theoretic configurations. We prove that this does not happen: the quantum homomorphism quasi-order of finite directed graphs is countably universal, and the quantum homomorphism quasi-order of finite planar graphs of maximum degree at most 7 is also countably universal. Consequently, the same universality holds for finite undirected graphs and for the corresponding quotient partial orders. The result is constructive for finite patterns. Given any finite poset P, we explicitly construct finite planar graphs Gp, p∈P, with Δ(Gp)≤7, such that \[ p\le_P q \quad\Longleftrightarrow\quad G_p\toq G_q. \] For directed graphs, the proof uses disjoint unions of clockwise directed cycles, where quantum and classical homomorphisms coincide. For undirected graphs, the main ingredient is a finite ordered indicator whose terminals are quantum endpoint-forcing. This gives a quantum analogue of the classical ordered-indicator method: the classical endpoint-image condition is replaced by the projection-level vanishing condition Fa,pFb,q=0 for every illegal ordered terminal pair. The fixed indicator encodes directed-cycle constructions inside planar bounded-degree graphs without creating extra quantum homomorphisms.
We prove RE-completeness of the quantum homomorphism problem parameterised by families of graphs derived from the classic metric association schemes. These include Kneser graphs, q-Kneser graphs, and the complements of Johnson, Grassmann, and Hamming graphs. Our proof develops a spectral method for establishing non-contextuality of quantum polymorphisms. It combines an equality analysis of Roberson's bound on the projective packing number in terms of Schrijver's theta with a structural argument inspired by Erdős-Ko-Rado theory.
Abstract In the (G, H)-isomorphism game, a verifier interacts with two non-communicating players (called provers), by privately sending each of them a random vertex from either G or H. The goal of the players is to convince the verifier that the graphs G and H are isomorphic. In recent work along with Atserias et al. (J Comb Theory Ser B 136:89–328, 2019) we showed that a verifier can be convinced that two non-isomorphic graphs are isomorphic, if the provers are allowed to share quantum resources. In this paper we model classical and quantum graph isomorphism by linear constraints over certain complicated convex cones, which we then relax to a pair of tractable convex models (semidefinite programs). Our main result is a complete algebraic characterization of the corresponding equivalence relations on graphs in terms of appropriate matrix algebras. Our techniques are an interesting mix of algebra, combinatorics, optimization, and quantum information.
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.