Abstract 1 Introduction 2 Preliminaries 3 NPA Hierarchy and Homomorphism Tensors 4 Homomorphism Indistinguishability 5 Exact Feasibility of NPA in Randomized Polynomial Time References

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

Prem Nigam Kar ORCID Technical University of Denmark, Lyngby, Denmark David E. Roberson ORCID Technical University of Denmark, Lyngby, Denmark Tim Seppelt ORCID IT-Universitetet i København, Copenhagen, Denmark Peter Zeman ORCID Technical University of Denmark, Lyngby, Denmark
Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
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 indistinguishability
Category:
Track A: Algorithms, Complexity and Games
Funding:
Prem Nigam Kar: Carlsberg Semper Ardens Accelerate CF21-0682 Quantum Graph Theory.
David E. Roberson: Carlsberg Semper Ardens Accelerate CF21-0682 Quantum Graph Theory.
Tim Seppelt: German Research Foundation (DFG) within Research Training Group 2236/2 (UnRAVeL) and European Union (ERC, SymSim, 101054974, CountHom, 101077083)
Peter Zeman: Funded by Carlsberg Semper Ardens Accelerate CF21-0682 Quantum Graph Theory and by the European Union (ERC, POCOCOP, 101071674).
Copyright and License:
[Uncaptioned image] © Prem Nigam Kar, David E. Roberson, Tim Seppelt, and Peter Zeman; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Quantum information theory
; Mathematics of computing Graph theory
Related Version:
Full Version: https://arxiv.org/abs/2407.10635 [11]
Funding:
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 Puppis

1 Introduction

Two graphs G and H are said to be homomorphism indistinguishable over a class of graphs , written GH, if for every graph F, the number of homomorphisms from F to G is the same as the number of homomorphisms from F to H. A classic result from [12] states that two graphs G and H 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 (G,H)-isomorphism game if and only if the graphs G and H are isomorphic. Two graphs G and H are said to be quantum isomorphic, written GqH, if there is a perfect quantum strategy (G,H)-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 k, the authors of [20] constructed a class of graphs k such that the kth-level of the Lasserre hierarchy of SDP relaxations of the integer program for deciding whether G and H are isomorphic is feasible if and only if G and H are homomorphism indistinguishable over the graph class k.

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 G and H and k, the following are equivalent:

  1. 1.

    there is a solution for the kth-level of the NPA hierarchy for the (G,H)-isomorphism game;

  2. 2.

    there is a level-k quantum isomorphism map from G to H;

  3. 3.

    G and H are algebraically k-equivalent;

  4. 4.

    G and H are homomorphism indistinguishable over the family of graphs 𝒫k.

In particular, the kth-level of the NPA hierarchy is feasible for the (G,H)-isomorphism game if and only G and H are homomorphism indistinguishable over the graph class 𝒫k. Here, 𝒫k 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 𝒫k 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 k, there exists a randomized polynomial-time algorithm for deciding homomorphism indistinguishability over 𝒫k. We strengthen this result by making the dependence on the parameter k effective.

Theorem 2.

There exists a randomized algorithm which decides, given graphs G and H and an integer k1, whether the kth-level of the NPA hierarchy for the (G,H)-isomorphism game is feasible. The algorithm always runs in time nO(k)kO(1) for nmax{|V(G)|,|V(H)|}, 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 𝑭=(F,u,v) and an unlabelled graph G, one can associated the homomorphism tensor 𝑭GV(G)×V(G) such that 𝑭G(x,y) for x,yV(G) is the number of homomorphisms h:FG such that h(u)=x and h(v)=y. For example, the bilabelled graph 𝑨=(A,u,v) with V(A)={u,v} and E(A)={uv} denotes the complete 2-vertex graph each of whose vertices u and v carry one label. In the case of 𝑨, the matrix 𝑨G is just the adjacency matrix of G. 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 (𝑭1)G(𝑭2)G yields the homomorphism tensor of the series composition of 𝑭1 and 𝑭2.

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 𝒫k 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 kth-level of the NPA hierarchy for the (G,H)-isomorphism game can be interpreted as the Choi matrix of a completely positive map from MV(G)k() to MV(H)k() with certain properties. Such a completely positive map is known as a level-k quantum isomorphism map. We also show that the Choi matrix of such a level-k quantum isomorphism map (uniquely) extends to a certificate for the kth-level of the NPA hierarchy, thus showing that the existence of such a map is equivalent to the feasibility of the kth-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 𝒬k for G to homomorphism tensors of 𝒬k for H, where 𝒬k is the set of atomic graphs which form the building blocks for the graph class 𝒫k. Such an algebra homomorphism is called an algebraic k-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 k-equivalence is equivalent to homomorphism indistinguishability over 𝒫k.

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 k from [20] is trivial, while proving the same for our graph classes 𝒫k requires a creative construction.

We take a more thorough look at the graph classes 𝒫k in Section 4. We show that the set of underlying graphs of the union of the bilabelled graph classes 𝒫k 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 G and H, the following are equivalent:

  1. 1.

    for every k, there is a solution for the kth-level of the NPA hierarchy for the (G,H)-isomorphism game,

  2. 2.

    G and H are homomorphism indistinguishable over k𝒫k, the class of all planar graphs,

  3. 3.

    G and H 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 𝒫k. This is done by computing a basis for the finite-dimensional vector space spanned by the homomorphism tensors of the bilabelled graphs in 𝒫k. To that end, the algorithm utilises the inductive definition of the graph class 𝒫k 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 𝒫k 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 h:FG from a graph F to a graph G is a map V(F)V(G) such that for all uvE(F) it holds that h(u)h(v)E(G). Note that this implies that any vertex in F carrying a loop must be mapped to a vertex carrying a loop in G.

Write hom(F,G) for the number of homomorphisms from F to G. For a family of graphs  and simple graphs G and H we write GH if G and H are homomorphism indistinguishable over , i.e. hom(F,G)=hom(F,H) for all F. Since the graphs G and H 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 k,l1, a (k,l)-bilabelled graph is a tuple 𝑭=(F,𝒖,𝒗) where F is a graph and 𝒖=(𝒖1,,𝒖k)V(F)k, 𝒗=(𝒗1,,𝒗l)V(F)l. The 𝒖 are the in-labelled vertices of 𝑭 while the 𝒗 are the out-labelled vertices of 𝑭. Given a graph G, the homomorphism tensor of 𝑭 for G is 𝑭GV(G)k×V(G)l whose (𝒙,𝒚)-entry is the number of homomorphisms h:FG such that h(𝒖i)=𝒙i and h(𝒗j)=𝒚j for all i[k] and j[l].

For a (k,l)-bilabelled graph 𝑭=(F,𝒖,𝒗), write soe(𝑭)F for the underlying unlabelled graph of 𝑭. If k=l, write Tr(𝑭) for the unlabelled graph underlying the graph obtained from 𝑭 by identifying 𝒖i with 𝒗i for all i[l]. For σ𝔖k+l, write 𝑭σ(F,𝒙,𝒚) where 𝒙i(𝒖𝒗)σ(i) and 𝒚jk(𝒖𝒗)σ(j) for all 1ik<jk+l, i.e., 𝑭σ is obtained from 𝑭 by permuting the labels according to σ. We also define 𝑭(F,𝒗,𝒖) the graph obtained by swapping in- and out-labels.

Let 𝑭=(F,𝒖,𝒗) and 𝑭=(F,𝒖,𝒗) be (k,l)-bilabelled and (m,n)-bilabelled, respectively. If l=m, write 𝑭𝑭 for the (k,n)-bilabelled graph obtained from them by series composition, whose underlying unlabelled graph obtained from the disjoint union of F and F by identifying 𝒗i and 𝒖i for all i[l]. Multiple edges arising in this process are removed. The in-labels of 𝑭𝑭 lie on 𝒖, the out-labels on 𝒗.

If k=m and l=n write 𝑭𝑭 for the parallel composition of 𝑭 and 𝑭. That is, the underlying unlabelled graph of the (k,l)-bilabelled graph 𝑭𝑭 is the graph obtained from the disjoint union of F and F by identifying 𝒖i with 𝒖i and 𝒗j with 𝒗j for all i[k] and j[l]. 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 G and all (l,l)-bilabelled graphs 𝑭,𝑭, it holds that soe(𝑭G)=hom(soe𝑭,G), Tr(𝑭G)=hom(Tr𝑭,G), (𝑭G)σ=(𝑭σ)G, (𝑭𝑭)G=𝑭G𝑭G, and (𝑭𝑭)G=𝑭G𝑭G, where soe(X) denotes the sum of elements, Tr denotes the trace, denotes matrix multiplication and denotes Schur product.

Slightly abusing notation, we say that two graphs G and H are homomorphism indistinguishable over a family of bilabelled graphs 𝒮, in symbols G𝒮H if G and H are homomorphism indistinguishable over the family {soe𝑺𝑺𝒮} 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 (k,l)-bilabelled graph. Then, M 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. 1.

    edge contraction

  2. 2.

    edge deletion

  3. 3.

    deletion of unlabelled vertices.

We note that the if a bilabelled graph 𝑴 is a bilabelled minor of 𝑭, then M is a minor of F [20, Lemma 4.12].

 Note 5 (drawing bilabelled graphs).

Throughout the paper we will depict bilabelled graphs as follows. To draw a bilabelled graph 𝐅=(F,𝐮,𝐯), we draw the graph F and attach ith input “wire”, depicted in grey, to ui and jth output wire to vi. 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.

Figure 1: (a) 𝑭=(K4,(2,1,3),(1,1,4)). (b) And example of series and parallel composition.

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 G, H be two graphs with |V(G)|=|V(H)|. The (G,H)-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 g,gV(G) (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 h,hV(H), respectively.

  • The verifier decides whether Alice and Bob win or lose this round of the game based on the rule function or predicate V(h,hg,g) which is given by

    V(h,hg,g)={1if relG(g,g)=relH(h,h)0otherwise

Here relG(g,g)=relH(h,h) 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 fA,fB:V(G)V(H), where Alice and Bob respond with fA(g),fB(g) when presented with the questions g,g respectively. A perfect strategy is one that always wins the game for Alice and Bob.

The predicate necessitates that fA=fB for any perfect deterministic strategy (fA,fB). Indeed, if g=g, one sees that fA(g)=fB(g) for all gV(G). Similarly, it is not too difficult to show that fA=fB=f 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 f:V(G)V(H), then this is a perfect strategy. Hence, the perfect deterministic strategies of the (G,H)-isomorphism game are in bijective correspondence with the isomorphisms of G and H.

Alice and Bob can also make use of probabilistic strategies. A probabilistic strategy is given by joint conditional probability distributions (p(h,hg,g))g,gV(G),h,hV(H). Probabilistic strategies are often called correlations in the literature. We shall denote the set of correlations indexed by the input sets X,Y and the output sets A,B by P(X,Y,A,B). In the case where X=Y and A=B, we shall use the notation P(X,A) instead.

It is easy to see that a probabilistic strategy is a perfect strategy for the (G,H)-isomorphism game if and only if V(h,hg,g)=0 implies that p(h,hg,g)=0 for all g,gV(G) and h,hV(H). We also note that any perfect probabilistic strategy for the (G,H)-isomorphism game satisfies that p(h,hg,g)=0 for all hhV(H) and gV(H). 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 (G,H)-isomorphism game consists of a shared state, i.e. a unit vector ψ in some Hilbert space and self-adjoint projections {Eg,h}gV(G),hV(H)() and {Fg,h}gV(G),hV(H)() such that:

  • hEgh=I and hFg,h=I

  • Eg,hFg,h=Fg,hEg,h for all g,gV(G) and h,hV(H).

When Alice and Bob receive the questions g,g from the verifier, they use the PVMs {Eg,h}hV(H) and {Fg,h}hV(H) to perform a measurement on their part of the shared state ψ. In this case, the conditional probability of outputting h,h when Alice and Bob receive the questions g,g is given by p(h,hg,g)=ψ,Eg,hFg,hψ.

Two graphs G, H are said to be quantum isomorphic, written GqH if there is a perfect quantum strategy for the (G,H)-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 (G,H)-isomorphism game is characterized by the following proposition:

Proposition 8 ([3]).

Let G, H be two graphs with |V(G)|=|V(H)|. Then, the GqH if and only if there exist a Hilbert space and self-adjoint projections {Eg,h}gV(G),hV(H) such that:

  1. 1.

    hV(H)Eg,h=I for all gV(G),

  2. 2.

    gV(G)Eg,h=I for all hV(H),

  3. 3.

    Eg,hEg,h=0 if VG,H(h,hg,g)=0.

Given the first two conditions, the last condition is equivalent to:

(A(G)I)[Eg,h]gV(G),hV(H)=[Eg,h]gV(G),hV(H)(A(H)I).

Furthermore, G and H are isomorphic if and only if there exist mutually commuting self-adjoint projections {Eg,h}gV(G),hV(H) 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 kth-level of the NPA hierarchy for the (G,H)-isomorphism game is. Let Σ=V(G)×V(H).

Definition 9.

For two graphs G, H with |V(G)|=|V(H)|, a certificate for the kth level of the NPA hierarchy of the (G,H)-isomorphism game is a positive semidefinite matrix MΣk() such that:

  1. 1.

    ε,ε=1

  2. 2.

    s,t=s,t for all r,s,r,sΣk, such that sRt(s)R(t), where we define to be the coarsest equivalence relation satisfying the following two properties:

    • For each x,aX×A, s(x,a)(x,a)ts(x,a)t for all s,tΣ.

    • stts for all words s,tΣ.

  3. 3.

    For all words s,sΣk, gV(G), hV(H) such that s(g,h)sΣk, one has

    hV(H)s(g,h)s,t=ss,t for all tΣk (1)
    gV(G)s(g,h)s,t=ss,t for all tΣk (2)
  4. 4.

    For all s,tΣk, if there exist consecutive gh,ghΣ in sRt such that rel(g,g)rel(h,h) then s,t=0.

We shall say that the kth-level of the NPA hierarchy for the (G,H)-isomorphism game is feasible if there exists a certificate for the kth-level of the NPA hierarchy for the same.

Given a perfect strategy for the (G,H)-isomorphism game, where {Eg,h}gV(G),hV(H) 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-k, we consider the Gram matrix of the vectors {Eg1,h1Egl,hlψ}g1h1glhlΣk.

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 (G,H)-isomorphism if an only if GqH; 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 G, H be two graphs with |V(G)|=|V(H)|, and Σ=V(G)×V(H). Then, the (G,H)-isomorphism game has a perfect quantum strategy if and only if for each k, there exists a certificate for the kth-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 kth level of the NPA hierarchy of the graph isomorphism game. These reformulations allow us to interpret the existence of a certificate for the kth 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 kth-level of the NPA hierarchy for quantum isomorphism can be interpreted as the Choi matrix of a completely positive map from MV(G)k() to MV(G)k() satisfying certain properties. We then show that the Choi matrix of such a completely positive map uniquely extends to a certificate for the kth-level of the NPA hierarchy for quantum isomorphism. Thus feasibility of the kth-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 k1. A (k,k)-bilabelled graph 𝐅=(F,𝐮,𝐯) is atomic if all its vertices are labelled. We define two classes of atomic graphs (see Figure 2):

  • The class 𝒬kP is the class of (k,k)-bilabelled minors of the graph 𝑪k(Ck,(1,,k),(k+1,,2k)) with V(Ck)=[2k] and E(Ck)={{i,i+1(modk)}:i[2k],ik,2k}.

  • The class 𝒬kS is the class of (k,k)-bilabelled minors of the graph 𝑴k(Mk,(1,,k),(k+1,,2k)) with V(Mk)=[2k] and E(Mk)={{i,i+k}:i[k]}

Finally, we define 𝒬k:=𝒬kP𝒬kS.

We also define two specific atomic graphs 𝐉k,𝐈k𝒬k for each k.

  • 𝑱k(Jk,(1,,k),(k+1,2k)) with V(Jk)=[2k] and E(Jk)=

  • 𝑰k(Ik,(1,k),(1,k)) with V(Ik)=[k] and E(Ik)=

In other words, 𝐉k and 𝐈k are obtained from 𝐌k by deleting and contracting all the edges respectively. These atomic graphs are special in the sense that one has (𝐉k)G=J and (𝐈k)G=I for all graphs G, where I and J are the identity and all ones matrix respectively. We also note that 𝐉k𝒬kS,𝒬kP and 𝐈k𝒬kS, but 𝐈k𝒬kP.

Figure 2: Atomic graphs.

We can now define quantum isomorphism maps using homomorphism tensors of graphs in 𝒬k:

Definition 12.

Let G and H be graphs and k. A linear map Φ:V(G)k×V(G)kV(H)k×V(H)k is a level k quantum isomorphism map from G to H if the following holds:

Φ is completely positive, (3)
Φ(𝑭GX)=𝑭HΦ(X) for all 𝑭𝒬kP and XV(G)k×V(G)k, (4)
Φ(I)=I=Φ(I), (5)
Φ(J)=J=Φ(J), (6)
Φ(𝑭G)=𝑭H for all F𝒬k, (7)
Φ(𝑿σ)=Φ(𝑿)σ for all σ𝒞(1,,k,2k,,k+1). (8)
 Note 13.

Note that conditions (3) and (5) state that any level k 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 𝐈G,𝐈H,𝐉G, and 𝐉H.

We now prove some lemmas that will be useful for our proof that existence of a level k quantum isomorphism map is equivalent to the feasibility of the kth level of the NPA hierarchy.

Lemma 14.

Let G and H be graphs, k, and suppose that Φ is a level k quantum isomorphism map from G to H. If M is the Choi matrix of Φ, then Ms,t=0 if any cyclic permutation of sRt contains consecutive terms gh and gh such that rel(g,g)rel(h,h).

Lemma 15.

Let G and H be graphs and k. If Φ is a level k quantum isomorphism map from G to H, then Φ(𝐅GX)=𝐅HΦ(X) and Φ(X𝐅G)=Φ(X)𝐅H for all 𝐅𝒬k and XV(G)k×V(G)k.

For our last lemma we need to introduce some notation. For disjoint subsets RG,RH[k], and s=g1h1gkhk(V(G)×V(H))k, we denote by s(RG,RH) the set of all strings s=g1h1gkhk such that gi=gi for iRG and hi=hi for iRH. For example, if k=3 and s=g1h1g2h2g3h3, then

s({1},{3})={g1h1g2h2g3h3(V(G)×V(H))3:g1V(G),h3V(H).}

Additionally, for any subset R[k] we denote by sR the substring of s obtained by removing its ith entry for each iR.

Lemma 16.

Let G and H be graphs and suppose that Φ is a level k quantum isomorphism map from G to H. If M is the Choi matrix of Φ, then for any s,t(V(G)×V(H))k, disjoint subsets SG,SH[k], and disjoint subsets TG,TH[k], we have that

ss(SG,SH),tt(TG,TH)Ms,t (9)

depends only on the equivalence class of that (s(SGSH))R(t(TGTH)) lies in.

Theorem 17.

Let G and H be graphs and k. Then the following are equivalent:

  1. 1.

    The kth level of the NPA hierarchy is feasible for the (G,H)-isomorphism game.

  2. 2.

    There exists a level k quantum isomorphism map from G to H.

  3. 3.

    There exists a level k quantum isomorphism map from H to G.

The idea is to use a principal submatrix of a certificate for the kth level of the NPA hierarchy as the Choi matrix of a linear map and show that this map is a level k quantum isomorphism map. Conversely, one takes the Choi matrix of a level k 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 G and H.

We remark that it follows from Definition 9 2 that the extension of the Choi matrix M to the certificate is in fact unique.

It should also be noted that not all elements of 𝒬kS 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 𝒬kS 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 G to homomorphism tensors for H of graphs in 𝒬k. This brings us a step closer to interpreting a solution for the kth-level of the NPA hierarchy as a homomorphism indistinguishability relation.

A matrix algebra 𝒜Mnk() is S-partially coherent if it is unital, self-adjoint, contains J, and is closed under Schur product with any matrix in S. Further, 𝒜 is cyclically-symmetric if Aσ𝒜, for every A𝒜 and σ𝒞(1,,k,2k,,k+1).

Definition 18.

Let Sk be the set of homomorphism tensors of (k,k)-bilabelled atomic graphs for G in 𝒬kP. For a graph G, we define the algebra 𝒬^Gk as the minimal cyclically-symmetrical Sk-partially coherent algebra containing homomorphism tensors of all (k,k)-bilabelled graphs in 𝒬k for G.

Definition 19.

Two n-vertex graphs G and H are algebraically k-equivalent if there is algebraic k-equivalence, i.e., a vector space isomorphism φ:𝒬^Gk𝒬^Hk such that

  1. 1.

    φ(M)=φ(M) for all M𝒬^Gk,

  2. 2.

    φ(MN)=φ(M)φ(N) for all M,N𝒬^Gk,

  3. 3.

    φ(𝑭GM)=𝑭Hφ(M) for all 𝑭𝒬kP and any M𝒬^Gk,

  4. 4.

    φ(I)=I, φ(J)=J and φ(𝑭G)=𝑭H for all 𝑭𝒬k,

  5. 5.

    φ(Mσ)=φ(M)σ for all M𝒬^Gk and σ𝒞(1,,k,2k,,k+1),

  6. 6.

    φ is trace preserving.

Note that every algebraic k-equivalence is sum-preserving, i.e., soe(φ(X))=soe(X) for all X𝒬^k. Indeed, soe(φ(X))=Tr(Jφ(X))=Tr(φ(JX))=Tr(JX)=soe(X).

Theorem 20.

Let k1. Two graphs G and H are algebraically k-equivalent if and only if there is a level-k quantum isomorphism map from G to H.

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 𝒫k such that homomorphism indistinguishability over 𝒫k is equivalent to the feasibility of the kth-level of the NPA hierarchy.

Definition 21.

Let 𝒫k be the class of (k,k)-bilabelled graphs generated by the set of atomic graphs 𝒬k under parallel composition with graphs from 𝒬kP, series composition, and the action of the group 𝒞(1,,k,2k,,k+1) on the labels.

We remark that the action of 𝒞(1,,k,2k,,k+1) on a bilabelled graph 𝑭𝒫k corresponds to “rotating” the drawing of .

Inner-product Compatibility of 𝓟𝒌.

A class of (k,k)-bilabelled graphs 𝒯 is said to be inner-product compatible if for all 𝑹,𝑺𝒯, there is a 𝑸𝒯 such that Tr(𝑹𝑺)=soe(𝑸).

Lemma 22.

The graph classes 𝒫k are inner-product compatible for each k.

Theorem 23 ([20, Theorem 27]).

Let 𝒮 be an inner-product compatible class of (k,k)-bilabelled graphs containing J. Write 𝒮G for the homomorphism tensors {𝐅G𝐅𝒮}, and let SGMV(G)k() denote the vector space spanned by 𝒮G. Then, the following are equivalent:

  1. 1.

    G and H are homomorphism indistinguishable over 𝒮.

  2. 2.

    there exists a sum-preserving vector space isomorphism φ:𝒮G𝒮H such that φ(𝑭G)=𝑭H for all 𝑭S.

The next theorem completes the proof of Theorem 1.

Theorem 24.

Let k1. Two graphs G and H are homomorphism indistinguishable over 𝒫k if and only if they are partially k-equivalent.

Proof.

The main idea of the proof is to note that (𝒫k)G=𝒬^kG for any graph G. Now, by Theorem 23, it is clear that G and H are homomorphism indistinguishable over 𝒫k if and only if there is a sum-preserving vector space isomorphism from 𝒬^kG to 𝒬^kH. Since every algebraic k-equivalence is sum-preserving, it is clear that if G and H are algebraically k-equivalent, then G𝒫kH.

On the contrary, if we assume that G𝒫kH, then there is a sum preserving vector space isomorphism φ:𝒬^kG to 𝒬^kH such that φ(𝑭G)=𝑭H for all 𝑭𝒫k. Hence, if 𝑭1,𝑭2𝒫k, then

φ((𝑭1)G(𝑭2)G)=φ((𝑭1𝑭2)G)=(𝑭1𝑭2)H=(𝑭1)H(𝑭2)H=φ((𝑭1)G)φ((𝑭2)G).

Similarly, if 𝑭2𝒬kP, then we can show that φ((𝑭1)G(𝑭2)G)=φ((𝑭1)G)φ((𝑭2)G). 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 𝒫k being inner-product compatible.

Planarity and Minor-closedness of 𝓟𝒌.

In this subsection, we shall look at the graph classes 𝒫k in more detail. The first thing we note is that for each k, one has that 𝒫kk, 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 k it is not too difficult to see that 𝒬k𝒜k (where 𝒜k are the atomic graphs used to construct k in [20]). Moreover, the set of allowed operations while constructing 𝒫k from 𝒬k is also a subset of the set of operations allowed while constructing k from 𝒜k. In fact, for k=1, it is not too difficult to show that 𝒫k=k is the set of all outerplanar graphs. We note here that the class 𝒫k is not the set of k-outerplanar graphs for k1. For any k, one can construct a k-outerplanar graph in 𝒫2. The following lemma is immediate from [20, Lemma 28]:

Lemma 25.

Let 𝐅𝒫k be a (k,k)-bilabelled graph. Then, the treewidth of the underlying graph soe(𝐅) is at most 3k1.

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 𝒫k=1k𝒫k. Then, it follows from the main theorem (Theorem 1) and convergence of NPA hierarchy (Proposition 10) that GqH is equivalent to G𝒫H. 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 k, the graph class 𝒫k 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 (k,l)-bilabelled graph 𝐆=(G,𝐚,𝐛) we define the graph G0 as the graph obtained from G by adding a cycle C=α1,,αk,βl,,β1 and the edges aiαi and bjβj for each i[k] and j[l], and say that 𝐆 is planar if G0 has a planar embedding where the cycle C is the boundary of a face. We shall refer to C as the enveloping cycle of G0, and usually consider planar embeddings where C is the boundary of the outer face.

Lemma 27.

For each k, the class of graphs 𝒫k is contained in the set of all planar bilabelled graphs.

We will also need that the class 𝒫k is closed under taking minors (recall the notion of minors of bilabelled graphs from Section 2) and that soe(𝒫k) is closed under minors and disjoint unions. The proofs of these facts are almost identical to the analogous proofs for the class k used in [20].

Lemma 28.

For each k, the class of bilabelled graphs 𝒫k is minor-closed.

Lemma 29.

For each k, the class of graphs soe(𝒫k) is minor-closed and union-closed.

We now work towards showing that although each 𝒫k has bounded treewidth, their union contains arbitrarily large grids.

Lemma 30.

For each k, the class of graphs 𝒫k contains the k×k grid.

Proof.

Let 𝑽k𝒫k denote the graph obtained by the parallel composition of 𝑪k and 𝑴k, i.e 𝑽k𝑴k𝑪k. Note that this parallel composition is allowed as 𝑪k𝒬kP. Clearly, soe(𝑽k) is the vertical grid with 2 columns and k rows (see Figure 3). Define 𝑮k to be the graph constructed by the series composition of k1 copies of 𝑽k, i.e. 𝑮k=𝑽k(1)Vk(k1), where each 𝑽k(i) is a copy of 𝑽k. It is clear from Figure 3 that soe𝑮k is the k×k grid.

Figure 3: (a) Construction of the graphs 𝑽k. (b) Construction of the graph 𝑮k.

We now need a standard result from graph minor theory that follows from [21]:

Theorem 31.

For every planar graph G, there is a natural number nG such that G is a minor of the nG×nG grid.

The following is immediate from Lemma 27, Lemma 29, Lemma 30 and Theorem 31:

Corollary 32.

The set 𝒫=ksoe(𝒫k) 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 kth-level of the NPA hierarchy for the (G,H)-isomorphism game is feasible for two graphs G and H if and only if they are homomorphism indistinguishable over 𝒫k. By Lemmas 29 and 25, the graph class 𝒫k is minor-closed and of bounded treewidth. Hence, by [23, Theorem 1.1], the feasibility of the kth-level of the NPA hierarchy can be decided in randomized polynomial time for every fixed k. However, this result assumes k 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 G and H are homomorphism indistinguishable over 𝒫k modulo a prime p, i.e. hom(F,G)hom(F,H)modp for all F𝒫k. We work over a finite field in order to avoid memory issues with too large integers.

Algorithm 1 Modular NPA.
Theorem 33.

There exists a deterministic algorithm which decides, given graphs G and H, an integer k1, and a prime p, whether G and H are homomorphism indistinguishable over 𝒫k modulo p. The algorithm runs in time nO(k)(klogp)O(1) for nmax{|V(G)|,|V(H)|}.

The algorithm in Theorem 33 decides whether G and H are homomorphism indistinguishable over 𝒫k by computing a basis B for the 𝔽p-vector space S spanned by homomorphism matrices of bilabelled graphs in 𝒫k. More precisely,

Sspan{𝑷G𝑷H𝑷𝒫k}𝔽p(V(G)kV(H)k)×(V(G)kV(H)k)

where 𝑷G𝑷H(𝑷G00𝑷H). A basis BS can be computed iteratively as follows. We initialise B with the singleton set containing 𝑱G𝑱H. 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 B, we add it to B. Since the dimension of S is at most 2n2k, 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-O(k) sets kP and kS of bilabelled graphs generating 𝒬kP and 𝒬kS. Let kkPkS.

Lemma 34.

Let k1 and consider the following (k,k)-bilabelled graphs.

  • 𝑱(J,(1,,k),(k+1,,2k)) with V(J)=[2k] and E(J)=,

  • for i[2k] and ji+1 if i<2k and j1 otherwise, the graphs 𝑪=i and 𝑪i which are obtained from 𝑱 by, respectively, identifying or connecting the vertices i and j,

  • 𝑰(I,(1,,k),(1,,k)) with V(I)=[k] and E(I)=,

  • for i[k], the graphs 𝑴i=(Mi,(1,,k),(1,,i1,i,i+1,,k)) with V(Mi)=[k]{i}, E(Mi)= and 𝑴i=(Mi,(1,,k),(1,,i1,i,i+1,,k)) with V(Mi)=[k]{i}, E(Mi)={ii}.

Then 𝒬kP is generated by kP{𝐉}{𝐂=i,𝐂ii[2k]} under parallel composition and 𝒬kS is contained by the graph class generated by kS{𝐈}{𝐌i,𝐌ii[k]} under series composition.

Lemma 35.

Algorithm 1 is correct.

Proof.

Let B denote the set computed when Algorithm 1 terminates. We first argue that the vectors in B span S. Clearly, BS and thus span(B)S. The inclusion Sspan(B) is shown by induction on the operations used in Definition 21 to define 𝒫k. The simplest graph in that set is 𝑱. It holds that 𝑱G𝑱HB, by initialisation. By Lemma 34, it holds that the homomorphism matrices of all bilabelled graphs in 𝒬k are in span(B). For the inductive step, let 𝑷𝒫k be some graph.

If 𝑷=𝑹𝑺 for the graphs 𝑹,𝑺𝒫k to which the inductive hypothesis applies then 𝑹G𝑹H,𝑺G𝑺Hspan(B). Hence, we may write 𝑹G𝑹H=αibi and 𝑹G𝑹H=βibi for some αi,βi𝔽p and biB. Since the algorithm terminated, it holds that bibjspan(B) for all i,j. Thus, 𝑷G𝑷H=αiβjbibjspan(B). The cases when 𝑷=𝑹𝑺 for 𝑹𝒬kP and when 𝑷=𝑹σ for σ𝒞(1,,k,2k,,k+1) follow analogously.

It remains to argue that the acceptance condition 𝟏GTv𝟏G=𝟏HTv𝟏H for all vB is correct. To that end, first assume that G and H are homomorphism indistinguishable over 𝒫k. Then for every 𝑷𝒫k it holds that

𝟏GT(𝑷G𝑷H)𝟏G=soe(𝑷G)=soe(𝑷H)=𝟏HT(𝑷G𝑷H)𝟏H.

Since S is spanned by these vectors, it follows that 𝟏GTv𝟏G=𝟏HTv𝟏H for all vB.

Conversely, suppose that 𝟏GTv𝟏G=𝟏HTv𝟏H holds for all vB. Let 𝑷𝒫k be arbitrary. By the previous claim, 𝑷G𝑷Hspan(B). Hence, the assumption implies that soe(𝑷G)=soe(𝑷H), as desired.

Lemma 36.

Algorithm 1 terminates in time nO(k)(klogp)O(1), where n is the maximum of |V(G)| and |V(H)|.

Proof.

The initialisation (above Line 6) can be completed in time nO(k)kO(1)(logp)O(1) noting that the set k is of size O(k) by Lemma 34.

Throughout the execution of the algorithm, B is a set of linearly independent vectors in a 2n2k-dimensional vector space over 𝔽p. This implies that the loop in Line 6 is entered at most 2n2k many times. It further more implies that the checks for linear independence in Lines 4, 9, 13 and 17 can be carried out in nO(k)(logp)O(1).

In each iteration of in Line 6, the first inner loop is entered at most nO(k)kO(1) times. The second inner loop is entered at most nO(k) times. The third inner loops is entered at most nO(k)kO(1) times. This yields the overall runtime bound.

Reducing NPA to Modular NPA.

If G≇𝒫kH, then there exists a graph F𝒫k such that hom(F,G)hom(F,H). Since hom(F,G),hom(F,H)nV(F) for nmax{|V(G)|,|V(H)|}, it follows that G and H are also not homomorphism indistinguishable over 𝒫k modulo every prime p greater than nV(F). Unfortunately, there is a priori no bound on the size of F in terms of n. In this section, we give such a bound and thereby derive Theorem 2 from Theorem 33. For l, write (𝒫k)l{F𝒫k|V(F)|l}.

Theorem 37.

If k1, G,H are graphs on at most n vertices, and fk(n)2k4n2k, then

G𝒫kHG(𝒫k)fk(n)H.

Towards Theorem 37, we define the following complexity measure ν:𝒫k inductively. If 𝑸𝒬k, then ν(𝑸)1. For 𝑭𝒫k, define ν(𝑭) inductively as the least number n such that there exist

  1. 1.

    𝑭𝒫k and 𝑸𝒬kP such that 𝑭=𝑸𝑭 and n=ν(𝑭), or

  2. 2.

    𝑭,𝑭′′𝒫k such that 𝑭=𝑭𝑭′′ and n=max{ν(𝑭),ν(𝑭′′)}+1, or

  3. 3.

    𝑭𝒫k and σ𝒞(1,,k,2k,,k+1) such that 𝑭=(𝑭)σ and n=ν(𝑭).

By Definition 21, ν:𝒫k is well-defined.

Lemma 38.

Let k1. For every 𝐅𝒫k, it holds that 𝐅 has at most 2k2ν(𝐅) vertices.

As in Section 5, we consider a sequence of nested spaces of homomorphism matrices. For l1, write

Slspan{𝑭G𝑭H𝑭𝒫k,ν(𝑭)l}(V(G)kV(H)k)×(V(G)kV(H)k).

Clearly, S1S2Sl1Sl. The space S is of dimension at most 2n2k. The following lemma shows that S2n2k=S.

Lemma 39.

If l1 is such that Sl=Sl+1, then Sl=S.

Proof of Theorem 37.

Only the backward implication requires a justification. Suppose that G and H are homomorphism indistinguishable over all graphs in 𝒫k of size at most 2k4n2k.

Let 𝑭𝒫k be of arbitrary size. By Lemma 39, there exist 𝑭i𝒫k with ν(𝑭i)2n2k and coefficients αi such that 𝑭G𝑭H=αi𝑭Gi𝑭Hi. By Lemma 38, the 𝑭i have at most 2k4n2k many vertices. Thus, hom(soe(𝑭i),G)=hom(soe(𝑭i),H), by assumption. Hence,

hom(soe(𝑭),G) =𝟏GT(𝑭G𝑭H)𝟏G=αi𝟏GT(𝑭Gi𝑭Hi)𝟏G
=αihom(soe(𝑭i),G)=αihom(soe(𝑭i),H)
=αi𝟏HT(𝑭Gi𝑭Hi)𝟏H=hom(soe(𝑭),H).

Here, 𝟏G,𝟏HV(G)kV(H)k denote the indicator vectors on the coordinates which correspond to G and H, respectively. Hence, G and H are homomorphism indistinguishable over 𝒫k.

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 N2k4n2k be as in Theorem 37. For 4log(Nlog(n))=nO(k) times, sample an integer Nlogn<p(Nlogn)2. This integer requires nO(k) many bits. In time nO(k), deterministically check whether p is a prime [2]. If it is a prime, run Algorithm 1 for G, H, k, and p. By Lemma 36, this takes time nO(k)kO(1). If the algorithm asserts that G≇𝒫kH, reject. Otherwise, proceed. If p 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 G≇𝒫kH is less than 1/2.

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.