NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
Abstract
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.
Keywords and phrases:
Quantum isomorphism, NPA hierarchy, homomorphism indistinguishabilityCategory:
Track A: Algorithms, Complexity and GamesFunding:
Prem Nigam Kar: Carlsberg Semper Ardens Accelerate CF21-0682 Quantum Graph Theory.Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Quantum information theory ; Mathematics of computing Graph theoryFunding:
Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
Two graphs and are said to be homomorphism indistinguishable over a class of graphs , written , if for every graph , the number of homomorphisms from to is the same as the number of homomorphisms from to . A classic result from [12] states that two graphs and are isomorphic if and only if they are homomorphism indistinguishable over all graphs. Since then, several relaxations of graph isomorphism from fields as diverse as finite model theory [7, 9, 8], algebraic graph theory [6], optimisation [10, 20], machine learning [25, 15, 26], and category theory [5, 1, 14] were found to be homomorphism indistinguishability relations over suitable graph classes. Recently, a coherent theory which addresses the descriptive and computational complexity of homomorphism indistinguishability relations has begun to emerge [19, 22, 17, 23].
A ground-breaking connection between quantum information and homomorphism indistinguishability was found by Mančinska and Roberson [13]: They showed that two graphs are quantum isomorphic if and only if they are homomorphism indistinguishable over all planar graphs. Quantum isomorphism, as introduced by [3], is a natural relaxation of graph isomorphism in terms of the graph isomorphism game, where two cooperating players called Alice and Bob try to convince a referee that two graphs are isomorphic. A perfect deterministic strategy exists for the -isomorphism game if and only if the graphs and are isomorphic. Two graphs and are said to be quantum isomorphic, written , if there is a perfect quantum strategy -isomorphism game, i.e., a perfect strategy making use of local quantum measurements on a shared entangled state.
The proof of Mančinska’s and Roberson’s result [13] heavily relies on certain esoteric mathematical objects called quantum groups. In more detail, the main idea of the proof is to interpret homomorphism tensors of bilabelled graphs as intertwiners of the quantum automorphism groups of the respective graphs.
Another recent result from [20] also obtained a homomorphism indistinguishability characterisation for each level of the Lasserre hierarchy of semidefinite programming (SDP) relaxations of the integer program for isomorphism between two graphs. More precisely, for each , the authors of [20] constructed a class of graphs such that the -level of the Lasserre hierarchy of SDP relaxations of the integer program for deciding whether and are isomorphic is feasible if and only if and are homomorphism indistinguishable over the graph class .
It was also shown in [3] that deciding quantum isomorphism of graphs is undecidable – contrary to deciding isomorphism of graphs, which is clearly decidable and currently known to be solvable in quasipolynomial time [4]. This motivates the study of relaxations of quantum isomorphism. The NPA hierarchy [16], which can be thought of as a noncommutative analogue of the Lasserre hierarchy, is a sequence of SDP relaxations of the problem of determining if a given joint conditional probability distribution arises from quantum mechanics. In particular, the NPA hierarchy can be used to formulate a hierarchy of SDP relaxations for the problem of deciding whether two graphs are quantum isomorphic.
In light of results from [13, 20], it is natural to ask if the feasibility of each level of these SDP relaxations of quantum isomorphism can be characterised as a homomorphism indistinguishability relation over some family of graphs. Such a characterisation would make the NPA hierarchy subject to the emerging theory of homomorphism indistinguishability. For example, a recent result [23] asserts that, over every minor-closed graph class of bounded treewidth, homomorphism indistinguishability can be decided in randomized polynomial time. The NPA relaxation, being a semidefinite program, can be solved using standard techniques such as the ellipsoid method. However, such techniques can, in polynomial time, only decide the approximate feasibility of a system. A homomorphism indistinguishability characterisation of the NPA hierarchy would imply, for each of its levels, the existence of a randomized polynomial-time algorithm for deciding exact feasibility [17, 22, 23].
Main Results.
Our main contribution is a homomorphism indistinguishability characterization of each level of the NPA hierarchy, as formalized by the following theorem.
Theorem 1.
For graphs and and , the following are equivalent:
-
1.
there is a solution for the -level of the NPA hierarchy for the -isomorphism game;
-
2.
there is a level- quantum isomorphism map from to ;
-
3.
and are algebraically -equivalent;
-
4.
and are homomorphism indistinguishable over the family of graphs .
In particular, the -level of the NPA hierarchy is feasible for the -isomorphism game if and only and are homomorphism indistinguishable over the graph class . Here, is a bounded-treewidth minor-closed class of planar graphs, which we construct by interpreting the NPA systems of equations in light of a correspondence between combinatorics (bilabelled graphs) and algebra (homomorphism tensors) which underpins many recent results regarding homomorphism indistinguishability [13, 10, 18, 20].
As a corollary of Theorem 1, we devise a randomized polynomial-time algorithm for deciding the exact feasibility of each level of the NPA hierarchy. To that end, we first show that the graph classes are minor-closed and of bounded treewidth, which is a graph parameter roughly measuring how far is a graph from a tree. Hence, a recent result from [23] implies that, for each , there exists a randomized polynomial-time algorithm for deciding homomorphism indistinguishability over . We strengthen this result by making the dependence on the parameter effective.
Theorem 2.
There exists a randomized algorithm which decides, given graphs and and an integer , whether the -level of the NPA hierarchy for the -isomorphism game is feasible. The algorithm always runs in time for , accepts all YES-instances, and accepts NO-instances with probability less than one half.
Proof Techniques.
The main algebraic-combinatorial tools we use are bilabelled graphs and their homomorphism tensors. Bilabelled graphs are graphs with distinguished vertices which are said to carry labels. To a bilabelled graph and an unlabelled graph , one can associated the homomorphism tensor such that for is the number of homomorphisms such that and . For example, the bilabelled graph with and denotes the complete -vertex graph each of whose vertices and carry one label. In the case of , the matrix is just the adjacency matrix of . The fruitfulness of this construction stems from a correspondence between combinatorial operations on bilabelled graphs and algebraic operations on homomorphism tensors. For example, the matrix product yields the homomorphism tensor of the series composition of and .
We prove Theorem 1 by interpreting the NPA relaxations as a system of equations whose constraints involve homomorphism tensors and algebraic operations. Applying the aforementioned algebro-combinatorial correspondence, the graph class is then obtained by reading the constraints as a description of a graph class via bilabelled graphs and combinatorial operations. To that end, we first give various reformulations of the NPA systems of equations as listed in Items 2 and 3 of Theorem 1. The proofs follow the outline below:
-
In Theorem 17, we first show that a principal submatrix of a certificate for the -level of the NPA hierarchy for the -isomorphism game can be interpreted as the Choi matrix of a completely positive map from to with certain properties. Such a completely positive map is known as a level- quantum isomorphism map. We also show that the Choi matrix of such a level- quantum isomorphism map (uniquely) extends to a certificate for the -level of the NPA hierarchy, thus showing that the existence of such a map is equivalent to the feasibility of the -level of the NPA hierarchy.
-
In Theorem 20, restrictions of the aforementioned completely positive maps are then shown to be algebra homomorphisms mapping homomorphism tensors of for to homomorphism tensors of for , where is the set of atomic graphs which form the building blocks for the graph class . Such an algebra homomorphism is called an algebraic -equivalence.
-
Lastly, in Theorem 1, we use the correspondence between combinatorial operations on graphs and algebraic operations on their homomorphism tensors to show that the existence of an algebraic -equivalence is equivalent to homomorphism indistinguishability over .
The overall structure of the proof of Theorem 1 is inspired by the proof of the main result of [20]. However, due to the “noncommutativity” of the NPA hierarchy, additional difficulties arise. For example, the proof of inner-product compatibility of the graph classes from [20] is trivial, while proving the same for our graph classes requires a creative construction.
We take a more thorough look at the graph classes in Section 4. We show that the set of underlying graphs of the union of the bilabelled graph classes is the set of all planar graphs. By combining this result with the convergence of the NPA hierarchy, we derive a substantially simpler proof of the homomorphism indistinguishability characterization of quantum isomorphism given in [13]. In particular, we are able to avoid the use of heavy machinery for dealing with quantum groups, which formed one of the main ingredients of the proof in [13].
Corollary 3.
For graphs and , the following are equivalent:
-
1.
for every , there is a solution for the -level of the NPA hierarchy for the -isomorphism game,
-
2.
and are homomorphism indistinguishable over , the class of all planar graphs,
-
3.
and are quantum isomorphic.
The proof of Theorem 2 relies on the characterisation of the NPA hierarchy as homomorphism indistinguishability relations from Theorem 1. That is, instead of attempting to solve the NPA systems of equations, the algorithm decides whether the input graphs are homomorphism indistinguishable over the graph class . This is done by computing a basis for the finite-dimensional vector space spanned by the homomorphism tensors of the bilabelled graphs in . To that end, the algorithm utilises the inductive definition of the graph class in terms of generators and combinatorial operations. Being linear or bilinear, their algebraic counterparts can be used to efficiently compute this basis via a fixed-point procedure, which terminates after polynomially many steps. Randomization is only necessary to deal with integers which would otherwise grow to exponential size in the course of the computation.
Outline.
We introduce bilabelled graphs and homomorphism tensors in Section 2, which are our main tools to relate the algebraic question of feasibility of the NPA hierarchy to a combinatorial problem of homomorphism indistinguishability. We then introduce the graph isomorphism game and a suitable version of the NPA hierarchy for the graph isomorphism game. The proof of Theorem 1 will be broken down into a series of simpler theorems, namely Theorems 17, 20, and 24. This is done in Section 3 and the beginning of Section 4. In Section 4 we study the graph classes in more detail and finish the proof of Corollary 3, thus providing the promised alternative proof of the result of [13]. In Section 5, we show that there is a polynomial-time randomized algorithm for each fixed level of the NPA hierarchy for quantum isomorphism.
2 Preliminaries
All graphs in this article are undirected, finite, and without multiple edges, unless stated otherwise. A graph is said to be simple if it does not contain any loops. A homomorphism from a graph to a graph is a map such that for all it holds that . Note that this implies that any vertex in carrying a loop must be mapped to a vertex carrying a loop in .
Write for the number of homomorphisms from to . For a family of graphs and simple graphs and we write if and are homomorphism indistinguishable over , i.e. for all . Since the graphs and into which homomorphisms are counted are throughout assumed to be simple, looped graphs in can generally be disregarded as they do not admit any homomorphisms into simple graphs. For background on homomorphism indistinguishability, the reader is referred to the monograph [24].
Bilabelled Graphs and Homomorphism Tensors.
We recall the following definitions from [13, 10]: For , a -bilabelled graph is a tuple where is a graph and , . The are the in-labelled vertices of while the are the out-labelled vertices of . Given a graph , the homomorphism tensor of for is whose -entry is the number of homomorphisms such that and for all and .
For a -bilabelled graph , write for the underlying unlabelled graph of . If , write for the unlabelled graph underlying the graph obtained from by identifying with for all . For , write where and for all , i.e., is obtained from by permuting the labels according to . We also define the graph obtained by swapping in- and out-labels.
Let and be -bilabelled and -bilabelled, respectively. If , write for the -bilabelled graph obtained from them by series composition, whose underlying unlabelled graph obtained from the disjoint union of and by identifying and for all . Multiple edges arising in this process are removed. The in-labels of lie on , the out-labels on .
If and write for the parallel composition of and . That is, the underlying unlabelled graph of the -bilabelled graph is the graph obtained from the disjoint union of and by identifying with and with for all and . Again, multiple edges are dropped. The in-labels of lie on , the out-labels on .
As observed in [13, 10], the benefit of these combinatorial operations is that they have algebraic counterparts. Formally, for all graphs and all -bilabelled graphs , it holds that , , , , and , where denotes the sum of elements, denotes the trace, denotes matrix multiplication and denotes Schur product.
Slightly abusing notation, we say that two graphs and are homomorphism indistinguishable over a family of bilabelled graphs , in symbols if and are homomorphism indistinguishable over the family of the underlying unlabelled graphs of .
We conclude this subsection by defining the notion of a minor of bilabelled graphs.
Definition 4 ([20]).
Let and be -bilabelled graph. Then, is said to be a bilabelled minor of , written , if it can be obtained from by applying a sequence of the following bilabelled minor operations:
-
1.
edge contraction
-
2.
edge deletion
-
3.
deletion of unlabelled vertices.
We note that the if a bilabelled graph is a bilabelled minor of , then is a minor of [20, Lemma 4.12].
Note 5 (drawing bilabelled graphs).
Throughout the paper we will depict bilabelled graphs as follows. To draw a bilabelled graph , we draw the graph and attach input “wire”, depicted in grey, to and output wire to . Vertices can have multiple input/output wires attached to them. The input and output wires extend to the far right and far left of the picture respectively. Finally, in order to indicate which input/output wire is which, we draw them so that they occur in numerical order (first at the top) at the edges of the picture. See Fig. 1(a) for an example of a bilabelled graph and Fig. 1(b) for an illustration of series and parallel composition, defined above.
The Graph Isomorphism Game.
We begin this section by defining the graph isomorphism game. We refer the reader to [3] for more details.
Definition 6.
Let , be two graphs with . The -isomorphism game is a cooperative game, involving two players Alice and Bob, and the verifier, played as follows:
-
In each round of the game, the verifier chooses two vertices (sampled uniformly and independently) and sends them to Alice and Bob, respectively.
-
Alice and Bob are not allowed to communicate during a round of the game, i.e. after receiving their question from the verifier. However, they are free to strategize before the game starts.
-
Alice and Bob respond with vertices , respectively.
-
The verifier decides whether Alice and Bob win or lose this round of the game based on the rule function or predicate which is given by
Here if both pairs of vertices are adjacent, non-adjacent, or identical.
Alice and Bob can employ a wide array of strategies to play this game. A deterministic strategy is one that involves two functions , where Alice and Bob respond with when presented with the questions respectively. A perfect strategy is one that always wins the game for Alice and Bob.
The predicate necessitates that for any perfect deterministic strategy . Indeed, if , one sees that for all . Similarly, it is not too difficult to show that is a graph isomorphism, if it is a perfect deterministic strategy. It is also clear that if Alice and Bob answer according to some isomorphism , then this is a perfect strategy. Hence, the perfect deterministic strategies of the -isomorphism game are in bijective correspondence with the isomorphisms of and .
Alice and Bob can also make use of probabilistic strategies. A probabilistic strategy is given by joint conditional probability distributions . Probabilistic strategies are often called correlations in the literature. We shall denote the set of correlations indexed by the input sets and the output sets by . In the case where and , we shall use the notation instead.
It is easy to see that a probabilistic strategy is a perfect strategy for the -isomorphism game if and only if implies that for all and . We also note that any perfect probabilistic strategy for the -isomorphism game satisfies that for all and . Such correlations are known as synchronous correlations.
Quantum Isomorphism of Graphs.
Throughout this paper, we shall be working with what is known as the commuting operator model of quantum mechanics. As discussed earlier, strategies making use of a shared state are known as quantum strategies.
Definition 7.
A quantum strategy for the -isomorphism game consists of a shared state, i.e. a unit vector in some Hilbert space and self-adjoint projections and such that:
-
and
-
for all and .
When Alice and Bob receive the questions from the verifier, they use the PVMs and to perform a measurement on their part of the shared state . In this case, the conditional probability of outputting when Alice and Bob receive the questions is given by .
Two graphs , are said to be quantum isomorphic, written if there is a perfect quantum strategy for the -isomorphism game. Two graphs that are isomorphic are also quantum isomorphic as all deterministic strategies can be realized as quantum strategies. However, the converse is not true, i.e. there exist non-isomorphic graphs that are quantum isomorphic. Once again, we refer the reader to [3] for further details.
The existence of a perfect quantum strategy for the -isomorphism game is characterized by the following proposition:
Proposition 8 ([3]).
Let , be two graphs with . Then, the if and only if there exist a Hilbert space and self-adjoint projections such that:
-
1.
for all ,
-
2.
for all ,
-
3.
if .
Given the first two conditions, the last condition is equivalent to:
Furthermore, and are isomorphic if and only if there exist mutually commuting self-adjoint projections satisfying the above conditions.
A Synchronous NPA Hierarchy for Quantum Isomorphism of Graphs.
We shall focus on the NPA hierarchy for the graph isomorphism game in this subsection. We first define what a certificate for the -level of the NPA hierarchy for the -isomorphism game is. Let .
Definition 9.
For two graphs , with , a certificate for the level of the NPA hierarchy of the -isomorphism game is a positive semidefinite matrix such that:
-
1.
-
2.
for all , such that , where we define to be the coarsest equivalence relation satisfying the following two properties:
-
For each , for all .
-
for all words .
-
-
3.
For all words , , such that , one has
(1) (2) -
4.
For all , if there exist consecutive in such that then .
We shall say that the -level of the NPA hierarchy for the -isomorphism game is feasible if there exists a certificate for the -level of the NPA hierarchy for the same.
Given a perfect strategy for the -isomorphism game, where are Alice’s measurement operators and the shared state is , we can construct a certificate for any level of the NPA hierarchy in the following way: for level-, we consider the Gram matrix of the vectors .
The following proposition shows that the NPA hierarchy for the graph isomorphism game converges, i.e there is a solution for each level of the NPA hierarchy for the -isomorphism if an only if ; see [11, Appendix B.2] for details. Proposition 10 gives two of the implications in Corollary 3, specifically it shows that items (1) and (3) are equivalent.
Proposition 10.
Let , be two graphs with , and . Then, the -isomorphism game has a perfect quantum strategy if and only if for each , there exists a certificate for the -level of the NPA hierarchy.
3 NPA Hierarchy and Homomorphism Tensors
In this section, we shall give several algebro-combinatorial reformulations of the existence of a certificate for the level of the NPA hierarchy of the graph isomorphism game. These reformulations allow us to interpret the existence of a certificate for the level of the NPA hierarchy as a homomorphism indistinguishability characterization. We shall discuss the graph-theoretic implications of our results in the next section.
Quantum Isomorphism Relaxation via Completely Positive Maps.
In this subsection, we show that a principal submatrix of a certificate for the -level of the NPA hierarchy for quantum isomorphism can be interpreted as the Choi matrix of a completely positive map from to satisfying certain properties. We then show that the Choi matrix of such a completely positive map uniquely extends to a certificate for the -level of the NPA hierarchy for quantum isomorphism. Thus feasibility of the -level of the NPA hierarchy for the graph isomorphism game is equivalent to the existence of a completely positive map satisfying certain properties. In order to make these notions precise, we now introduce the atomic bilabelled graphs, which will be the building blocks of the graph classes that we shall construct in the next section.
Definition 11.
Let . A -bilabelled graph is atomic if all its vertices are labelled. We define two classes of atomic graphs (see Figure 2):
-
The class is the class of -bilabelled minors of the graph with and
-
The class is the class of -bilabelled minors of the graph with and
Finally, we define .
We also define two specific atomic graphs for each .
-
with and
-
with and
In other words, and are obtained from by deleting and contracting all the edges respectively. These atomic graphs are special in the sense that one has and for all graphs , where and are the identity and all ones matrix respectively. We also note that and , but .
We can now define quantum isomorphism maps using homomorphism tensors of graphs in :
Definition 12.
Let and be graphs and . A linear map is a level quantum isomorphism map from to if the following holds:
(3) | |||
(4) | |||
(5) | |||
(6) | |||
(7) | |||
(8) |
Note 13.
Note that conditions (3) and (5) state that any level quantum isomorphism map is a completely positive, trace-preserving, unital map. Also note that condition (7) implies the part of conditions (5) and (6) on the map , and thus we are being a bit redundant. However, we do need to explicitly include the conditions on the adjoint . Lastly, we are being a bit imprecise since we should really write , and .
We now prove some lemmas that will be useful for our proof that existence of a level quantum isomorphism map is equivalent to the feasibility of the level of the NPA hierarchy.
Lemma 14.
Let and be graphs, , and suppose that is a level quantum isomorphism map from to . If is the Choi matrix of , then if any cyclic permutation of contains consecutive terms and such that .
Lemma 15.
Let and be graphs and . If is a level quantum isomorphism map from to , then and for all and .
For our last lemma we need to introduce some notation. For disjoint subsets , and , we denote by the set of all strings such that for and for . For example, if and , then
Additionally, for any subset we denote by the substring of obtained by removing its entry for each .
Lemma 16.
Let and be graphs and suppose that is a level quantum isomorphism map from to . If is the Choi matrix of , then for any , disjoint subsets , and disjoint subsets , we have that
(9) |
depends only on the equivalence class of that lies in.
Theorem 17.
Let and be graphs and . Then the following are equivalent:
-
1.
The level of the NPA hierarchy is feasible for the -isomorphism game.
-
2.
There exists a level quantum isomorphism map from to .
-
3.
There exists a level quantum isomorphism map from to .
The idea is to use a principal submatrix of a certificate for the level of the NPA hierarchy as the Choi matrix of a linear map and show that this map is a level quantum isomorphism map. Conversely, one takes the Choi matrix of a level quantum isomorphism map and shows that the remaining entries needed in a certificate for the NPA hierarchy can be determined by the entries from the Choi matrix alone. The equivalence of the final item follows from the fact that the first item is clearly symmetric in and .
We remark that it follows from Definition 9 2 that the extension of the Choi matrix to the certificate is in fact unique.
It should also be noted that not all elements of were needed to prove that item (2) implies item (1) above. This is related to the fact that it is in fact possible to generate these unused bilabelled graphs from those that were used in the proof. However, redefining the set to only contain those that were used does not make it any easier to prove that (1) implies (2), and we will need these extra graphs later.
Isomorphisms Between Matrix Algebras.
In this subsection, we shall see how a quantum isomorphism map restricts to a homomorphism between algebras containing homomorphism tensors for to homomorphism tensors for of graphs in . This brings us a step closer to interpreting a solution for the -level of the NPA hierarchy as a homomorphism indistinguishability relation.
A matrix algebra is -partially coherent if it is unital, self-adjoint, contains , and is closed under Schur product with any matrix in . Further, is cyclically-symmetric if , for every and .
Definition 18.
Let be the set of homomorphism tensors of -bilabelled atomic graphs for in . For a graph , we define the algebra as the minimal cyclically-symmetrical -partially coherent algebra containing homomorphism tensors of all -bilabelled graphs in for .
Definition 19.
Two -vertex graphs and are algebraically -equivalent if there is algebraic -equivalence, i.e., a vector space isomorphism such that
-
1.
for all ,
-
2.
for all ,
-
3.
for all and any ,
-
4.
, and for all ,
-
5.
for all and ,
-
6.
is trace preserving.
Note that every algebraic -equivalence is sum-preserving, i.e., for all . Indeed, .
Theorem 20.
Let . Two graphs and are algebraically -equivalent if and only if there is a level- quantum isomorphism map from to .
Proof.
The proof is similar to [20, Theorem 3.14 and Theorem 3.16].
4 Homomorphism Indistinguishability
In this section, we shall finish the proof of the main theorem by constructing the graph classes such that homomorphism indistinguishability over is equivalent to the feasibility of the -level of the NPA hierarchy.
Definition 21.
Let be the class of -bilabelled graphs generated by the set of atomic graphs under parallel composition with graphs from , series composition, and the action of the group on the labels.
We remark that the action of on a bilabelled graph corresponds to “rotating” the drawing of .
Inner-product Compatibility of .
A class of -bilabelled graphs is said to be inner-product compatible if for all , there is a such that .
Lemma 22.
The graph classes are inner-product compatible for each .
Theorem 23 ([20, Theorem 27]).
Let be an inner-product compatible class of -bilabelled graphs containing . Write for the homomorphism tensors , and let denote the vector space spanned by . Then, the following are equivalent:
-
1.
and are homomorphism indistinguishable over .
-
2.
there exists a sum-preserving vector space isomorphism such that for all .
The next theorem completes the proof of Theorem 1.
Theorem 24.
Let . Two graphs and are homomorphism indistinguishable over if and only if they are partially -equivalent.
Proof.
The main idea of the proof is to note that for any graph . Now, by Theorem 23, it is clear that and are homomorphism indistinguishable over if and only if there is a sum-preserving vector space isomorphism from to . Since every algebraic -equivalence is sum-preserving, it is clear that if and are algebraically -equivalent, then .
On the contrary, if we assume that , then there is a sum preserving vector space isomorphism to such that for all . Hence, if , then
Similarly, if , then we can show that . Other than being trace-preserving, the remaining conditions from Definition 19 can be proven in similar manners. The fact is trace-preserving follows from it being sum-preserving and being inner-product compatible.
Planarity and Minor-closedness of .
In this subsection, we shall look at the graph classes in more detail. The first thing we note is that for each , one has that , which were the classes of graphs constructed in [20] to obtain a homomorphism indistinguishability charatcterization for the Lasserre hierarchy of SDP relaxations of graph isomorphism. We refer the reader to [20] for more details.
Indeed, for each it is not too difficult to see that (where are the atomic graphs used to construct in [20]). Moreover, the set of allowed operations while constructing from is also a subset of the set of operations allowed while constructing from . In fact, for , it is not too difficult to show that is the set of all outerplanar graphs. We note here that the class is not the set of -outerplanar graphs for . For any , one can construct a -outerplanar graph in . The following lemma is immediate from [20, Lemma 28]:
Lemma 25.
Let be a -bilabelled graph. Then, the treewidth of the underlying graph is at most .
We now work towards giving an alternate proof of the main result of [13] that shows that two graphs are quantum isomorphic if and only if they are homomorphism indistinguishable over all planar graphs. Let . Then, it follows from the main theorem (Theorem 1) and convergence of NPA hierarchy (Proposition 10) that is equivalent to . This proves Corollary 3 with the exception of the claim in item (2) that is the set of all planar graphs. We now work towards completing the proof of Corollary 3.
First, we show that for each , the graph class only contains planar graphs. We begin by precisely defining what it means for a bilabelled graph to be planar. We use the definition given in [13].
Definition 26.
Given a -bilabelled graph we define the graph as the graph obtained from by adding a cycle and the edges and for each and , and say that is planar if has a planar embedding where the cycle is the boundary of a face. We shall refer to as the enveloping cycle of , and usually consider planar embeddings where is the boundary of the outer face.
Lemma 27.
For each , the class of graphs is contained in the set of all planar bilabelled graphs.
We will also need that the class is closed under taking minors (recall the notion of minors of bilabelled graphs from Section 2) and that is closed under minors and disjoint unions. The proofs of these facts are almost identical to the analogous proofs for the class used in [20].
Lemma 28.
For each , the class of bilabelled graphs is minor-closed.
Lemma 29.
For each , the class of graphs is minor-closed and union-closed.
We now work towards showing that although each has bounded treewidth, their union contains arbitrarily large grids.
Lemma 30.
For each , the class of graphs contains the grid.
Proof.
Let denote the graph obtained by the parallel composition of and , i.e . Note that this parallel composition is allowed as . Clearly, is the vertical grid with columns and rows (see Figure 3). Define to be the graph constructed by the series composition of copies of , i.e. , where each is a copy of . It is clear from Figure 3 that is the grid.
We now need a standard result from graph minor theory that follows from [21]:
Theorem 31.
For every planar graph , there is a natural number such that is a minor of the grid.
The following is immediate from Lemma 27, Lemma 29, Lemma 30 and Theorem 31:
Corollary 32.
The set is the set of all planar graphs.
Recalling the discussion preceding Lemma 27, this completes the proof of Corollary 3, and thus gives us the promised alternative proof of the result of [13].
5 Exact Feasibility of NPA in Randomized Polynomial Time
Being a semidefinite program, the NPA relaxation can be solved using standard techniques such as the ellipsoid method. However, such techniques can, in polynomial time, only decide the approximate feasibility of a system. In this section, we use homomorphism indistinguishability to give a randomized algorithm for deciding exact feasibility of each level of the NPA hierarchy. See 2
By a recent result [23, Theorem 1.1], homomorphism indistinguishability over every minor-closed graph class of bounded treewidth can be decided in randomized polynomial time. In Theorem 1, we have established that the -level of the NPA hierarchy for the -isomorphism game is feasible for two graphs and if and only if they are homomorphism indistinguishable over . By Lemmas 29 and 25, the graph class is minor-closed and of bounded treewidth. Hence, by [23, Theorem 1.1], the feasibility of the -level of the NPA hierarchy can be decided in randomized polynomial time for every fixed . However, this result assumes to be fixed and not part of the input.
Modular Homomorphism Indistinguishability.
As a first step towards Theorem 2, we show that it can be decided in deterministic polynomial time whether and are homomorphism indistinguishable over modulo a prime , i.e. for all . We work over a finite field in order to avoid memory issues with too large integers.
Theorem 33.
There exists a deterministic algorithm which decides, given graphs and , an integer , and a prime , whether and are homomorphism indistinguishable over modulo . The algorithm runs in time for .
The algorithm in Theorem 33 decides whether and are homomorphism indistinguishable over by computing a basis for the -vector space spanned by homomorphism matrices of bilabelled graphs in . More precisely,
where . A basis can be computed iteratively as follows. We initialise with the singleton set containing . Subsequently, we repeatedly apply the operations from Definition 21 to compute new vectors. Whenever a new vector is linearly independent from the vectors already in , we add it to . Since the dimension of is at most , this process takes polynomial number of steps and is formally described in Algorithm 1.
In order to achieve a better runtime in Theorem 33, we give size- sets and of bilabelled graphs generating and . Let .
Lemma 34.
Let and consider the following -bilabelled graphs.
-
with and ,
-
for and if and otherwise, the graphs and which are obtained from by, respectively, identifying or connecting the vertices and ,
-
with and ,
-
for , the graphs with , and with , .
Then is generated by under parallel composition and is contained by the graph class generated by under series composition.
Lemma 35.
Algorithm 1 is correct.
Proof.
Let denote the set computed when Algorithm 1 terminates. We first argue that the vectors in span . Clearly, and thus . The inclusion is shown by induction on the operations used in Definition 21 to define . The simplest graph in that set is . It holds that , by initialisation. By Lemma 34, it holds that the homomorphism matrices of all bilabelled graphs in are in . For the inductive step, let be some graph.
If for the graphs to which the inductive hypothesis applies then . Hence, we may write and for some and . Since the algorithm terminated, it holds that for all . Thus, . The cases when for and when for follow analogously.
It remains to argue that the acceptance condition for all is correct. To that end, first assume that and are homomorphism indistinguishable over . Then for every it holds that
Since is spanned by these vectors, it follows that for all .
Conversely, suppose that holds for all . Let be arbitrary. By the previous claim, . Hence, the assumption implies that , as desired.
Lemma 36.
Algorithm 1 terminates in time , where is the maximum of and .
Proof.
The initialisation (above Line 6) can be completed in time noting that the set is of size by Lemma 34.
Throughout the execution of the algorithm, is a set of linearly independent vectors in a -dimensional vector space over . This implies that the loop in Line 6 is entered at most many times. It further more implies that the checks for linear independence in Lines 4, 9, 13 and 17 can be carried out in .
In each iteration of in Line 6, the first inner loop is entered at most times. The second inner loop is entered at most times. The third inner loops is entered at most times. This yields the overall runtime bound.
Reducing NPA to Modular NPA.
If , then there exists a graph such that . Since for , it follows that and are also not homomorphism indistinguishable over modulo every prime greater than . Unfortunately, there is a priori no bound on the size of in terms of . In this section, we give such a bound and thereby derive Theorem 2 from Theorem 33. For , write .
Theorem 37.
If , are graphs on at most vertices, and , then
Towards Theorem 37, we define the following complexity measure inductively. If , then . For , define inductively as the least number such that there exist
-
1.
and such that and , or
-
2.
such that and , or
-
3.
and such that and .
By Definition 21, is well-defined.
Lemma 38.
Let . For every , it holds that has at most vertices.
As in Section 5, we consider a sequence of nested spaces of homomorphism matrices. For , write
Clearly, . The space is of dimension at most . The following lemma shows that .
Lemma 39.
If is such that , then .
Proof of Theorem 37.
Only the backward implication requires a justification. Suppose that and are homomorphism indistinguishable over all graphs in of size at most .
Let be of arbitrary size. By Lemma 39, there exist with and coefficients such that . By Lemma 38, the have at most many vertices. Thus, , by assumption. Hence,
Here, denote the indicator vectors on the coordinates which correspond to and , respectively. Hence, and are homomorphism indistinguishable over .
It remains to derive Theorem 2 from Theorems 33 and 37.
Proof of Theorem 2.
A randomized algorithm for the problem Theorem 2 proceeds as similar to [23, Algorithm 2]. Let be as in Theorem 37. For times, sample an integer . This integer requires many bits. In time , deterministically check whether is a prime [2]. If it is a prime, run Algorithm 1 for , , , and . By Lemma 36, this takes time . If the algorithm asserts that , reject. Otherwise, proceed. If is not a prime, proceed to the next iteration.
By the proof of [23, Theorem 1.1], the probability of incorrectly accepting an instance such that is less than .
References
- [1] Samson Abramsky, Tomáš Jakl, and Thomas Paine. Discrete Density Comonads and Graph Parameters. In Helle Hvid Hansen and Fabio Zanasi, editors, Coalgebraic Methods in Computer Science, pages 23–44, Cham, 2022. Springer International Publishing. doi:10.1007/978-3-031-10736-8_2.
- [2] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of Mathematics, 160(2):781–793, September 2004. doi:10.4007/annals.2004.160.781.
- [3] Albert Atserias, Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. Quantum and non-signalling graph isomorphisms. Journal of Combinatorial Theory, Series B, 136:289–328, 2019. doi:10.1016/j.jctb.2018.11.002.
- [4] László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684–697. ACM, 2016. doi:10.1145/2897518.2897542.
- [5] Anuj Dawar, Tomáš Jakl, and Luca Reggio. Lovász-Type Theorems and Game Comonads. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1–13. IEEE, 2021. doi:10.1109/LICS52264.2021.9470609.
- [6] Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász Meets Weisfeiler and Leman. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pages 40:1–40:14, 2018. doi:10.4230/LIPICS.ICALP.2018.40.
- [7] Zdeněk Dvořák. On recognizing graphs by numbers of homomorphisms. Journal of Graph Theory, 64(4):330–342, 2010. doi:10.1002/jgt.20461.
- [8] Eva Fluck, Tim Seppelt, and Gian Luca Spitzer. Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth. In Aniello Murano and Alexandra Silva, editors, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024), volume 288 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:17, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CSL.2024.27.
- [9] Martin Grohe. Counting Bounded Tree Depth Homomorphisms. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 507–520, New York, NY, USA, 2020. Association for Computing Machinery. doi:10.1145/3373718.3394739.
- [10] Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism Tensors and Linear Equations. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 70:1–70:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2022.70.
- [11] Prem Nigam Kar, David E Roberson, Tim Seppelt, and Peter Zeman. NPA hierarchy for quantum isomorphism and homomorphism indistinguishability. arXiv preprint arXiv:2407.10635, 2024. doi:10.48550/arXiv.2407.10635.
- [12] László Lovász. Operations with structures. Acta Mathematica Academiae Scientiarum Hungarica, 18(3):321–328, September 1967. doi:10.1007/BF02280291.
- [13] Laura Mančinska and David E. Roberson. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 661–672, 2020. doi:10.1109/FOCS46700.2020.00067.
- [14] Yoàv Montacute and Nihil Shah. The Pebble-Relation Comonad in Finite Model Theory. In Christel Baier and Dana Fisman, editors, LICS ’22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022, pages 13:1–13:11. ACM, 2022. doi:10.1145/3531130.3533335.
- [15] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33:4602–4609, 2019. doi:10.1609/aaai.v33i01.33014602.
- [16] Miguel Navascués, Stefano Pironio, and Antonio Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10(7):073013, July 2008. doi:10.1088/1367-2630/10/7/073013.
- [17] Daniel Neuen. Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width. In Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov, editors, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), volume 289 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1–53:12, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2024.53.
- [18] Gaurav Rattan and Tim Seppelt. Weisfeiler–Leman and Graph Spectra. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2268–2285. Society for Industrial and Applied Mathematics, 2023. doi:10.1137/1.9781611977554.ch87.
- [19] David E. Roberson. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree, 2022. arXiv:2206.10321v1.
- [20] David E Roberson and Tim Seppelt. Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability. TheoretiCS, 3, 2024. doi:10.46298/THEORETICS.24.20.
- [21] Neil Robertson and P.D Seymour. Graph minors. iii. planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49–64, 1984. doi:10.1016/0095-8956(84)90013-3.
- [22] Tim Seppelt. Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors. In Jérôme Leroux, Sylvain Lombardy, and David Peleg, editors, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), volume 272 of Leibniz International Proceedings in Informatics (LIPIcs), pages 82:1–82:15, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.MFCS.2023.82.
- [23] Tim Seppelt. An Algorithmic Meta Theorem for Homomorphism Indistinguishability. In Rastislav Královič and Antonín Kučera, editors, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306 of Leibniz International Proceedings in Informatics (LIPIcs), pages 82:1–82:19, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.MFCS.2024.82.
- [24] Tim Seppelt. Homomorphism Indistinguishability. Dissertation, RWTH Aachen University, Aachen, 2024. doi:10.18154/RWTH-2024-11629.
- [25] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In International Conference on Learning Representations, 2018. URL: https://openreview.net/forum?id=ryGs6iA5Km.
- [26] Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond Weisfeiler–Lehman: A Quantitative Framework for GNN Expressiveness. In The Twelfth International Conference on Learning Representations, 2024. URL: https://openreview.net/forum?id=HSKaGOi7Ar.