Abstract 1 Introduction 2 Preliminaries, Background, and the Main Theorem 3 The Proof of Theorem 9 4 Consequences of Theorem 9 5 Possible Variations of Theorem 9 References

The Converse of the Real Orthogonal Holant Theorem

Ben Young111Corresponding author ORCID Department of Computer Sciences, University of Wisconsin-Madison, WI, USA
Abstract

The Holant theorem is a powerful tool for studying the computational complexity of counting problems. Due to the great expressiveness of the Holant framework, a converse to the Holant theorem would itself be a very powerful counting indistinguishability theorem. The most general converse does not hold, but we prove the following, still highly general, version: if any two sets of real-valued signatures are Holant-indistinguishable, then they are equivalent up to an orthogonal transformation. This resolves a partially open conjecture of Xia (2010). Consequences of this theorem include the well-known result that homomorphism counts from all graphs determine a graph up to isomorphism, the classical sufficient condition for simultaneous orthogonal similarity of sets of real matrices, and a combinatorial characterization of sets of simultaneosly orthogonally decomposable (odeco) symmetric tensors.

Keywords and phrases:
Holant, Counting Indistinguishability, Odeco
Category:
Track A: Algorithms, Complexity and Games
Copyright and License:
[Uncaptioned image] © Ben Young; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Mathematics of computing Combinatorics
; Mathematics of computing Graph theory ; Theory of computation Problems, reductions and completeness
Related Version:
Full Version: https://arxiv.org/abs/2409.06911 [43]
Acknowledgements:
The author thanks Jin-Yi Cai for helpful discussions and Ashwin Maran for his suggestion which improved the proof of Theorem 27. The author also thanks Guus Regts for pointing out reference [32].
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

Holant problems

Holant problems were introduced by Cai, Lu, and Xia [12] as a highly expressive framework for studying the computational complexity of counting problems. The problem Holant() is defined by a set of signatures, where a signature F of arity n on domain [q]:={0,1,,q1} is a tensor in (q)n, or equivalently a function [q]n. Given a signature grid Ω – a multigraph in which every degree-n vertex is assigned a n-ary signature from – the problem is to compute the Holant value of Ω, which is the value of the contraction of Ω as a tensor network (see Subsection 2.1 for formal definitions). For various , Holant() captures a wide variety of natural counting problems on graphs, including counting partial or perfect matchings, graph homomorphisms, proper vertex or edge-colorings, or Eulerian orientations. Major complexity dichotomies classifying Holant() as either polynomial-time tractable or #P-hard, depending on , have been proved for various combinations of restrictions on – for example, requiring that the signatures in be real- or nonnegative-real-valued, symmetric (invariant under reordering of their inputs), or on the Boolean domain q=2 [22, 9, 7, 23, 35].

Holant problems were motivated by Valiant’s technique of holographic transformations [39]. In particular, Valiant’s Holant theorem (Theorem 7 below) states roughly that two pairs of signature sets (,) and (𝒢,𝒢) equivalent up to a certain linear transformation are Holant-indistinguishable, meaning that every bipartite signature grid Ω has the same Holant value whether its vertices are assigned signatures from or from 𝒢𝒢. Many problems which do not otherwise appear tractable are in fact tractable under a Holographic transformation to a known tractable problem [38]. Xia [41] conjectured the converse of the Holant theorem: if (,) and (𝒢,𝒢) are Holant-indistinguishable, then they are equivalent up to linear transformation. Xia’s general conjecture is false (see Subsection 2.2), but one case highlighted by Xia was left open. This paper proves that case, which is as follows.

Theorem (Theorem 9, informal).

Sets and 𝒢 of real-valued signatures are equivalent under a real orthogonal transformation if and only if and 𝒢 are Holant-indistinguishable.

Vertex and edge coloring models

This work uses and generalizes ideas from the theory of vertex coloring models and edge coloring models, two well-studied classes of Holant problems. De la Harpe and Jones [14] defined vertex and edge coloring models as extensions of statistical mechanics models (e.g. the Ising model), calling them “spin models” and “vertex models”, respectively. A vertex coloring model (also called a spin system) is defined by a graph X with edge and possibly vertex weights. Given an input graph K, one aims to compute the partition function, the number of (weighted) homomorphisms from K to X. As we discuss in Subsection 2.1, computing the partition function of a vertex coloring model without vertex weights is equivalent to Holant(AX𝒬), where AX is the weighted adjacency matrix of X and 𝒬 is the set of equality signatures (we can model vertex weights by replacing 𝒬 with 𝒢𝒬, the set of weighted equalities). An edge coloring model is defined by a set of symmetric signatures containing exactly one signature of each arity, and the problem of computing its partition function is equivalent to Holant() (this restriction on ensures that edge coloring models take ordinary graphs, rather than signature grids, as input).

One thread of prior work on vertex and edge coloring models characterizes which graph parameters (scalar-valued functions defined on isomorphism classes of graphs) are expressible as vertex coloring models [20, 34] or as edge coloring models [37, 32, 16, 29]. Another, related, line of works compute the rank of connection matrices for vertex coloring models [25] and edge coloring models [28, 17]. See Regts’s thesis [30] for an overview of many of the above results. Following Freedman, Lovász, and Schrijver [20], these works all use some form of (labeled) quantum graphs, algebras of formal linear combinations of graphs equipped with labeled vertices or “half edges” incident to a single vertex. Each labeled quantum graph defines a tensor by evaluating its partition function when its labeled vertices are fixed to input values. All such constructions are special cases of our quantum gadgets below (see 12). Many of these works also apply techniques from invariant theory, either of the symmetric group in the case of vertex coloring models [34], or, as in this work, of the orthogonal group O(q) in the case of edge-coloring models [37, 32, 16, 28, 17, 29].

Counting Indistinguishability Theorems

Theorem 9 is a very general and powerful algebraic counting indistinguishability theorem. Such a theorem proves that two signatures, or sets of signatures, are indistinguishable as parameters for a counting problem if and only if they are equivalent under an algebraic transformation. These theorems exist for both vertex and edge coloring models, as well as other counting problems [15, 21, 18]. Since the Holant framework captures a wide variety of counting problems, including both vertex and edge coloring models, many such theorems are special cases of Theorem 9 (see Section 4). If the counting problem in question is a generalized vertex coloring model (Holant(𝒬) for some ), then the algebraic transformation is isomorphism, and if the counting problem is, as in this work, a generalized edge coloring model, then it is orthogonal. The first counting indistinguishability theorem, proved by Lovász [26], states that two graphs are isomorphic if and only if they admit the same number of homomorphisms from all graphs. Much later, Lovász [25] extended this theorem to vertex coloring models with nonnegative real weights, followed by extensions to complex edge weights by Schrijver [34], and to weights from any field of characteristic zero by Cai and Govorov [8]. Young [42] extended Cai and Govorov’s proof to #CSP, or Holant(𝒬) for any .

For edge coloring models, Schrijver [32] showed that and 𝒢 define indistinguishable real edge coloring models if and only if and 𝒢 are equivalent under a real orthogonal transformation. This is a special case of our Theorem 9. Schrijver’s proof exploits the specific nature of edge coloring models – that and 𝒢 consist of symmetric signatures and exactly one signature per arity – to transform input graphs into polynomials expressible in variables y1,,yq (for and 𝒢 on domain [q]), where a monomial with variable multiset {yi1,,yin} corresponds to the {i1,,in}-entry of the unique n-ary signature in . This enables the application of invariant-theoretic tools for polynomial rings. Another form of this result (allowing a complex orthogonal transformation) follows from Regts’s proof of [29, Lemma 5], which similarly encodes and 𝒢 as polynomials.

Holant-like indistinguishability theorems also arise in tensor network theory, where they are called fundamental theorems. It has been shown that two tensors are equivalent up to a gauge transformation (a concept similar to holographic transformation) if and only if they yield the same quantum state (roughly, Holant gadget signature) on every instance of certain vertex-regular tensor networks studied in quantum physics, e.g. PEPS tensor networks [1].

Mančinska and Roberson [27] introduced a new form of counting indistinguishability theorem, showing that two graphs are quantum isomorphic – an abstract relaxation of isomorphism – if and only if they admit the same number of homomorphisms from all planar graphs. Cai and Young [13] translated Mančinska and Roberson’s proof into the Holant framework and extended it to planar #CSP (or PlHolant(𝒬), where PlHolant restricts to planar signature grids), showing that real-valued and 𝒢 are planar-#CSP-indistinguishable iff they are quantum isomorphic.

Odeco signature sets

A real-valued symmetric signature (tensor) is orthogonally decomposable, or odeco [31], if it is orthogonally transformable to a signature in 𝒢𝒬, the set of generalized equality signatures, which take nonzero values only when all of their inputs are equal. Hence odeco tensors generalize diagonalizable matrices. Call a set of signatures odeco if the signatures are simultaneously odeco (there is a single orthogonal transformation mapping into 𝒢𝒬). In counting complexity, if is odeco, then Holant() is polynomial-time tractable, as maps into 𝒢𝒬, a trivially tractable set, under an orthogonal holographic transformation. Indeed, the tractability of Fibonacci signature sets [11] can, with one exception, be explained by such sets being simultaneously odeco (see e.g. [4, Section 2.2]). Fibonacci sets constitute almost all nontrivial tractable cases of Holant problems (an important variant of Holant which assumes the presence of all unary signatures) for symmetric signatures on the Boolean domain [12]. Odeco sets are a natural starting point for extending Fibonacci signatures to higher domains [24, 10], where no full complexity dichotomy for Holant is known.

Boralevi, Draisma, Horobeţ, and Robeva [2], resolving a conjecture of Robeva [31], showed using techniques from algebraic geometry that a single tensor F is odeco if and only if the signature of a certain F-gadget is symmetric. Using Theorem 9, we in Theorem 27 extend this characterization to sets of simultaneously odeco signatures: is odeco if and only if every connected -gadget has a symmetric signature. The latter condition is equivalent to the symmetry of the signatures of all gadgets in a set of small gadgets constructed from every pair of signatures in . Therefore, if is finite, our characterization yields a simple O(q2n2||2)-time algorithm (for on domain [q] with maximum arity n) for deciding whether is odeco. This algorithm, and other potential bounded-time combinatorial algorithms using Theorem 9 to check whether there exists an orthogonal holographic transformation between two signature sets, could prove useful in making the tractability or intractability conditions of future higher-domain dichotomy theorems decidable. Our characterization also deepens the connection between Fibonacci and odeco signatures, as the original proof of tractability of any Fibonacci signature set [11] relied on the fact that every connected -gadget has a signature which is itself Fibonacci (in particular, is symmetric). One can view the (iii) (ii) result in Theorem 27 as a general-domain version of this proof.

Overview

The proof of Theorem 9 begins with a combinatorial-algebraic duality (Theorem 15) showing that combinatorial quantum -gadgets exactly capture all tensors invariant under the algebraic action of the group of orthogonal transformations stabilizing . The proof of Theorem 15 uses an invariant-theoretic result of Schrijver [33], and generalizes a proof of a similar result of Regts [28] for edge coloring models. Unifying the perspective of Regts with that of Mančinska and Roberson and Cai and Young [27, 13, 42], we find our proof of Theorem 15 analogous to proofs of similar results in the latter line of work (see [43, Remark 3.1]). However, Mančinska and Roberson and Cai and Young’s proofs of their counting indistinguishability theorems use orbits of the (quantum) symmetric group on the domain set [q], which do not exist for the orthogonal group. Instead, we apply a novel method: induction on the domain size q. We show in 19 that, if and 𝒢 contain a nontrivial diagonal matrix (binary signature) D, then we can separate [q] into smaller subdomains and apply induction to complete the proof. Then we use Theorem 15 to show that, unless and 𝒢 are trivially transformable, we can add such a D to and 𝒢.

In Section 4 we show that Theorem 9 encompasses a range of existing counting indistinguishability theorems, and yields some novel variations of these theorems. In Section 5 we show that Theorem 9 does not extend to complex-valued signatures, and conjecture an extension of the results of Mančinska and Roberson [27] and Cai and Young [13] to planar-Holant-indistinguishability and quantum orthogonal transformations. Our proof of Theorem 9, particularly the connections developed in [43, Section 3], is designed to be transformable into a proof of this conjecture; in Subsection 5.2, we discuss the remaining roadblocks to completing the proof.

2 Preliminaries, Background, and the Main Theorem

2.1 Holant Problems, Gadgets, and Signature Matrices

Let be the set of natural numbers, including 0. A signature F of finite arity n on finite domain V(F) is function V(F)n. We will often take V(F)=[q]:={0,1,,q1}, in which case we also view F as a tensor in (q)n. For 𝐱=(x1,,xn)V(F)n, abbreviate F𝐱:=F(x1,,xn). Signature F is symmetric if its value depends only on the multiset of inputs, not on their order. Signatures in a set have a common domain, denoted V().

For a signature set , a signature grid (or -grid) Ω consists of an underlying multigraph with vertex set V and edge set E, and an assignment of a deg(v)-ary signature Fv to each vV, along with an ordering e1,,edeg(v) of δ(v) (the edges incident to v) such that, if σ:EV() is an assignment of a value in V() to each edge of Ω, then Fv evaluates to Fv(σ|δ(v)):=Fv(σ(e1),,σ(edeg(v))). The problem Holant() is to compute the Holant value

HolantΩ=HolantΩ():=σ:EV()vVFv(σ|δ(v)). (1)

The Holant value of a disconnected signature grid is the product of the Holant values of its connected components. For signature sets and , define the problem Holant() on bipartite ()-grids Ω, with the vertices in the two bipartitions assigned signatures in and , respectively.

For example, if is on the Boolean domain {0,1} and consists of, for each arity n, a symmetric signature which evaluates to 1 on input strings of Hamming weight 1 and 0 on all other input strings, then HolantΩ() equals the number of perfect matchings in the multigraph underlying Ω. For another example, let AXq×q be the adjacency matrix of weighted graph X, and define the set 𝒬={=nn1} of equality signatures, where =n(x1,,xn) is 1 if x1==xn, and is 0 otherwise. For an (AX𝒬)-grid Ω, let K be the graph resulting from ignoring (treating as edges) the degree-two vertices assigned AX in the underlying graph of Ω. Then the vertex coloring model HolantΩ(AX𝒬) equals the number of graph homomorphisms from K to X. See Figure 1.

Figure 1: The grid Ω such that HolantΩ(AX𝒬) counts homomorphisms from K to X.

Instead of viewing a signature F as a tensor in (q)n or function in [q]n, we can partition its inputs in two to view it naturally as a matrix.

Definition 1 (Fm,d,f).

For F(q)n and m,d with m+d=n, define the (m,d)-signature matrix, or flattening, Fm,dqm×qd of F by, for 𝐱[q]m and 𝐲[q]d,

(Fm,d)𝐱,𝐲=F(x0,,xm1,yd1,,y0),

where we use [qn][q]n to index Fm,d. Write f=Fn,0qn – the signature vector of F.

We will often identify binary signatures in (q)2 with their 1,1 signature matrices in q×q.

Definition 2 (𝔊,𝔊(m,d)).

For a signature set , an -gadget is a -grid equipped with an ordered set of dangling edges with zero or one endpoints. Define 𝔊 to be the set of all -gadgets, and 𝔊(m,d)𝔊 to be the set of gadgets with m+d dangling edges 0,,m1,rd1,,r0 drawn with dangling ends in counterclockwise cyclic order around the gadget, with 0,,m1 and r0,,rd1 on the left and right, respectively, from top to bottom.

See Figure 2 for examples of gadgets. A gadget in 𝔊(m,d) defines an (m+d)-ary signature in flattened form, with dangling edges representing inputs, as follows (cf. (1)):

Definition 3 (M(𝐊)).

Define the signature matrix M(𝐊)qm×qd of 𝐊𝔊(m,d) by

M(𝐊)𝐱,𝐲=σ:E(𝐊)[q]i:σ(i)=xij:σ(rj)=yjvVFv(σ|δ(v)) for 𝐱[q]m and 𝐲[q]d.

In other words, M(𝐊)𝐱,𝐲 equals the Holant value of 𝐊 when the left and right dangling edges are fixed to the domain elements in 𝐱 and 𝐲, respectively. For 𝐊𝔊(m,d), there is a unique F(q)m+d, the signature of 𝐊, such that M(𝐊)=Fm,d. Note that F does not depend on the particular left/right partition (i.e. choice of m and d) of a fixed cyclic order of 𝐊’s dangling edges.

Define gadget operations ,,, illustrated in Figure 2 (see [43, Definition 2.4] for formal definitions). The three gadget operations induce the respective operations – composition, Kronecker product, transpose – on their signature matrices. See e.g. [4, Section 1.3].




Figure 2: Operations on gadgets 𝐊𝔊(4,2) and 𝐋𝔊(2,1). Dangling edges are drawn thinner.
Definition 4 (,,).

For real-valued and n-ary -gadgets 𝐊 and 𝐋, construct the signature grid 𝐊,𝐋 by connecting the ith dangling edges of 𝐊 and 𝐋, for i[n]. If 𝐊 and 𝐋 have signatures K and L, then define K,L:=Holant𝐊,𝐋=Kn,0,Ln,0 (the standard inner product on qn).

Define F:=F,F=𝐱F𝐱2.

2.2 The Holant Theorem

Definition 5 (HF,H).

For invertible HGLq() and F(q)n, let HF(q)n be the signature with vector Hnf – that is, (HF)n,0=Hnf (see Figure 3).

For set , define H:={HFF}.

Figure 3: Illustrating Hnf=(HF)n,0, or equivalently HmFm,d(H)d=(HF)m,d.

We usually have HO(q), the q×q (real) orthogonal group. Throughout this work, we assume pairs and 𝒢 of signature sets are similar, meaning they have the same domain size q and there is a bijection 𝒢 such that, for n-ary F, the image G𝒢 of F, called the signature corresponding to F and denoted by FG, has the same arity n.

Definition 6 (𝐊𝒢,Ω𝒢).

For (similar) sets and 𝒢 and gadget 𝐊𝔊, define the gadget 𝐊𝒢𝔊𝒢 by replacing every F assigned to a vertex in 𝐊 by the corresponding G𝒢. If 𝐊 has zero dangling edges then it is an -grid Ω, and is transformed to a 𝒢-grid Ω𝒢.

The following theorem of Valiant [39] is a powerful reduction tool and the original motivation for Holant. For F(q)n and AGLq(), define FA similarly to AF, by (FA)0,n=F0,nAn.

Theorem 7 (The Holant Theorem).

For any ()-grid Ω and matrix AGLq(),

HolantΩ()=HolantΩ(AA1),where Ω=Ω(|)(A|A1).

Xia [41] conjectured that the converse of Theorem 7 holds as long as one of or contain a signature with arity greater than one: if HolantΩ()=HolantΩ(|)(𝒢|𝒢)(𝒢𝒢) for every ()-grid Ω, then there is an AGLq() such that 𝒢=A and 𝒢=A1. However, Cai, Guo, and Williams [9, Section 4.3] observe that this conjecture is false. They consider

Holant([0,1,0][a,b,1,0,0])andHolant([0,1,0][0,0,1,0,0])

for any a,b not both 0, where [0,1,0] and [a,b,1,0,0] are symmetric signatures on the Boolean domain {0,1} of arity n=2,4, respectively, specified by their values on input strings of Hamming weight 0 through n. These signature sets satisfy the hypothesis of Xia’s conjecture, as they differ by the vanishing (Holant-indistinguishable from 0) signature set ([0,1,0][a,b,0,0,0]), but there is no AGL2() satisfying [0,1,0]A=[0,1,0] and A1[a,b,1,0,0]=[0,0,1,0,0].

Cai, Guo, and Williams’ counterexample exists due to the bipartiteness of Holant(𝒢), as [0,0,1,0,0],[0,0,1,0,0]=[0,0,1,0,0]2[a,b,1,0,0]2=[a,b,1,0,0],[a,b,1,0,0], so [a,b,1,0,0] and [0,0,1,0,0] are not indistinguishable on general (non-bipartite) signature grids. To avoid such counterexamples, we consider the following well-known form of Theorem 7 that applies to non-bipartite grids Ω. Replace each edge in Ω by a path of length two, with central vertex assigned (=2). This does not change the Holant value of Ω, which is now a Holant((=2))-grid. Any HO(q) satisfies H1(=2)=(=2), so Theorem 7 gives:

Corollary 8 (The Orthogonal Holant Theorem).

If 𝒢=H for orthogonal matrix H, then HolantΩ()=HolantΩ𝒢(𝒢) for every -grid Ω.

Xia also considers the converse of 8, and proves that it holds for specific and 𝒢 consisting of symmetric signatures with small domain and/or arity. The main result of this work is the converse of 8 for any sets and 𝒢 of real-valued signatures, with no restrictions.

Theorem 9 (Main Result).

The following are equivalent for sets , 𝒢 of real-valued signatures:

  1. (i)

    HolantΩ()=HolantΩ𝒢(𝒢) for every -grid Ω (, 𝒢 are Holant-indistinguishable).

  2. (ii)

    There is a real orthogonal matrix H such that H=𝒢 (, 𝒢 are ortho-equivalent).

3 The Proof of Theorem 9

Henceforth, assume all signatures are real-valued.

Definition 10 (T(q)).

Let T(q):=n(q)n be the set of all domain-[q] signatures.

We will use the following notations from invariant theory [33, 28].

Definition 11 (T(q)Q, Stab()).

For a subgroup QO(q) and T(q), define

T(q)Q:={FT(q)HF=F for every HQ}T(q) and, dually,
Stab():={HO(q)HF=F for every F}O(q).

The following objects generalize the (labeled) quantum graphs originally introduced by Freedman, Lovász, and Schrijver [20], so-called because they are “superpositions” of graphs.

Definition 12 (𝔔, ¯).

An (m,d)-quantum -gadget is a formal (finite) -linear combination of gadgets in 𝔊(m,d). Extend the signature matrix function M linearly to the set 𝔔 of quantum -gadgets and define the quantum gadget closure ¯ of as the set of quantum -gadget signatures:

¯:=Fm,dM(𝔔)F.

If sets and 𝒢 are similar, then ¯ and 𝒢¯ are similar, with the signature of 𝐊𝔔 corresponding to the signature of 𝐊𝒢𝔔𝒢.

The next two lemmas are nonplanar, orthogonal versions of [13, Lemmas 31 and 32].

Lemma 13.

and 𝒢 are Holant-indistinguishable iff ¯ and 𝒢¯ are Holant-indistinguishable.

Proof.

Any -grid or 𝒢-grid is also a ¯-grid or 𝒢¯-grid, respectively, giving the () direction. For (), we can express any ¯-grid Ω as a quantum -grid by, for every vertex v in Ω assigned a signature Fv¯, replacing the subgadget of Ω induced by v by the quantum -gadget with signature Fv, then linearly expanding to obtain a quantum -grid. Do the same for Ω¯𝒢¯. By assumption, the resulting corresponding quantum and 𝒢-grids have the same values, so HolantΩ=HolantΩ¯𝒢¯.

Lemma 14.

For any orthogonal H, H=𝒢 iff H¯=𝒢¯ (in particular, H¯=H¯).

14, proved in the full version [43, Lemma 4.1.2], follows from the fact that orthogonal transformations respect the operations ,,,+ used to construct quantum gadgets.

The following key theorem, also proved in the full version [43, Theorem 3.2], extends an edge coloring model result of Regts [28, Theorem 3].

Theorem 15.

Let be a set of signatures on domain [q]. Then T(q)Stab()=¯.

The inclusion of Theorem 15 again follows from the fact that orthogonal transformations respect the operations used to construct quantum gadgets, so any orthogonal matrix stabilizing stabilizes any quantum -gadget signature. The proof of the much deeper inclusion, which shows that every tensor in T(q)Stab() is concretely realizable as a quantum gadget signature, uses an invariant-theoretic result of Schrijver [33].

Definition 16 ().

Let F,G be n-ary signatures on domains V(F), V(G), both of size q. The direct sum FG of F and G is an n-ary signature on domain V(F)V(G) defined by

(FG)𝐱={F𝐱𝐱V(F)nG𝐱𝐱V(G)n0otherwisefor 𝐱(V(F)V(G))n.

For signature sets and 𝒢, define 𝒢={FGFG𝒢}.

View HStab(𝒢)(V()V(𝒢))×(V()V(𝒢)) as a block matrix indexed by V() and V(𝒢). The next lemma is the only nonconstructive step in the proof of Theorem 9.

Lemma 17.

If and 𝒢 are Holant-indistinguishable, then Stab(𝒢) contains a matrix which is not block-diagonal.

Proof.

Suppose every HStab(𝒢) is block-diagonal. Then the block-diagonal matrix A=I2I satisfies HA=AH, or equivalently H2A2,0=A2,0 (see Figure 3), for every HStab(𝒢). Thus AT(2q)Stab(𝒢), so, by Theorem 15, A is realizable as the signature of a quantum gadget: there exist binary (𝒢)-gadgets 𝐊1,𝐊p and c1,,cp such that

A=i=1pciM(𝐊i). (2)

Any connected component of a gadget 𝐊i disconnected from the component(s) of 𝐊i containing the two dangling edges contributes only an overall multiplicative factor; by absorbing this factor into ci, we may assume each 𝐊i has no components without a dangling edge. By definition of , inputting an xV() along a dangling edge of 𝐊i forces any edge assignment with nonzero value to assign an element of V() to every edge in that dangling edge’s connected component. So, for any x,yV(), we have M(𝐊i)x,y=M(𝐊(𝒢)i)x,y. Similar reasoning applies to 𝒢, so the V(),V() and V(𝒢),V(𝒢) blocks of (2) are

I=i=1pciM(𝐊(𝒢)i) and 2I=i=1pciM(𝐊(𝒢)𝒢i), (3)

respectively. Let Ωi be the -grid resulting from connecting the two dangling edges of 𝐊(𝒢)i. Then taking the trace of the equations in (3) gives

i=1pciHolantΩi()=q2q=i=1pciHolantΩ𝒢i(𝒢),

so there is some i for which HolantΩi()HolantΩ𝒢i(𝒢).

The next definition and its applications use a simple but powerful idea of Shao and Cai [35, Section 8.2]: isolating all vertices of an {F}-grid Ω assigned F, the rest of Ω is an -gadget.

Definition 18 (Subgadget, 𝐊¯).

Let 𝐉 be a gadget. A subgadget 𝐊𝐉 induced by a subset UV(𝐉) of vertices of 𝐉 is a gadget composed of the vertices in U and all of their incident edges: internal edges of 𝐉 incident to exactly one vertex in U become new dangling edges of 𝐊. For any 𝐊𝐉, there is a unique 𝐊¯𝐉 (induced by V(𝐉)U), called the complement of 𝐊, such that, upon reconnecting the new dangling edges of 𝐊 and 𝐊¯, we recover 𝐉.

We often take 𝐉 to be a signature grid (0-ary gadget) Ω, in which case Ω=𝐊,𝐊¯.

We next state the main inductive lemma.

Lemma 19.

Let and 𝒢 be signature sets on domain [q], and suppose Theorem 9 holds for all , 𝒢 on domain smaller than q. If and 𝒢 are Holant-indistinguishable and contain corresponding copies of a diagonal matrix (binary signature) Dspan(I), then and 𝒢 are ortho-equivalent.

The proof of 19 in the full version [43, Lemma 4.3] proceeds roughly as follows. The quantum gadget closure {D}¯ of {D} is a vector space closed under both entrywise sum and entrywise product (the latter equivalent to composition, as D is diagonal). Therefore, by a standard Vandermonde interpolation argument, Dspan(I) implies that {D}¯ contains the binary signatures 𝟙X and 𝟙Y for a nontrivial partition [q]=XY of the domain, where e.g. 𝟙X acts as =2 on X and 0 on Y. Replacing, say, each edge of an - or 𝒢-grid by 𝟙X, we effectively obtain an |X- or 𝒢|X-grid, respectively (where |X is the restriction of to the subdomain X). Thus |X and 𝒢|X are Holant-indistinguishable, so, inductively, |X and 𝒢|X are ortho-equivalent. Similarly, |Y and 𝒢|Y are ortho-equivalent. These two subdomain transformations alone do not necessarily transform the “off-diagonal blocks” of into the corresponding blocks of 𝒢, so some more work is required. We add some useful auxiliary signatures to and 𝒢 between the successive X and Y subdomain transformations, using subgadgets to show Holant-indistinguishability is preserved, and finally obtain a full transformation from to 𝒢.

The final step is to realize the diagonal matrix D in the statement of 19 and apply induction. Say is quantum-gadget-closed if =¯.

Proof of Theorem 9.

(ii)(i) is 8. We show (i)(ii). Let ,𝒢 be Holant-indistinguishable. We proceed by induction on the domain size q. The full version shows the case q=1 in the proof of [43, Theorem 2.3], so assume q>1. Lemmas 13 and 14 show that replacing and 𝒢 by ¯ and 𝒢¯ does not affect their Holant-indistinguishability or ortho-equivalence, so we may assume and 𝒢 are quantum-gadget-closed. By 17, there is an HStab(𝒢) with, WLOG, nonzero block (V(𝒢),V()). Let UDV be the singular value decomposition of this block, with U,V orthogonal and D0 diagonal. Replace with V and 𝒢 with U𝒢 (this does not change whether and 𝒢 are Holant-indistinguishable or ortho-equivalent). This replaces 𝒢 with (V)(U𝒢)=(VU)(𝒢) (by [43, Equation A.1]), which, by [43, Proposition 4.2], replaces Stab(𝒢) with (VU)Stab(𝒢)(VU). In particular, H is replaced with

[V00U][UDV][V00U]=[U(UDV)V]=[D].

To summarize, after transforming by V and 𝒢 by U, we have H=[D]Stab(𝒢) for nonzero diagonal D. We consider two cases for D: either Dspan(I) or Dspan(I). First, suppose Dspan(I), so D=cI for c0. Let FG be nonzero n-ary signatures with n2. By part 3 of [43, Proposition 3.1] (see Figure 3), HStab(𝒢) gives

Hn1(FG)n1,1=(FG)n1,1H. (4)

By [43, Proposition A.1] (with K:=FG) and [43, Equation 2.2], we can write (4) as a block matrix equation

[Dn1][Fn1,1000000Gn1,1]=[Fn1,1000000Gn1,1][D]. (5)

The bottom-left block of (5) is Dn1Fn1,1=Gn1,1D; using D=cI, this is equivalent to

cn2F=G. (6)

Then

F2=F,F=G,G=c2(n2)F2. (7)

As and 𝒢 are quantum-gadget-closed, there are some FG𝒢 with arity n3, so (7) gives c=±1. Now applying (6) to any n-ary pair FG with n2 gives cnF=cn2F=G, so (cI)F=G, with cIO(q).

For unary (n=1) F and G, since and 𝒢 are quantum-gadget-closed, they contain the ternary signatures F3 and G3, respectively. So, by the previous paragraph, (cI)F3=G3, or equivalently (cF)3=G3, which implies cF=G. Combining the non-unary and unary cases, we have (cI)=𝒢.

Otherwise, Dspan(I). We will show {D} and 𝒢{D} are Holant-indistinguishable, then apply 19.

Figure 4: The Holant-value-preserving transformation from Ω to Ω{D}𝒢{D}.

Consider an {D}-grid Ω with at least one vertex assigned D (if Ω has no such vertex then we are done, as and 𝒢 are Holant-indistinguishable). Let 𝐊Ω be the subgadget induced by all vertices assigned D. Any connected component of 𝐊 is either a cycle or a binary path gadget with signature Dm for some m. The multiplicative factors from corresponding D-cycles in Ω and Ω{D}𝒢{D} cancel, so assume 𝐊 consists of p disconnected path gadgets. By rearranging the dangling edges of 𝐊 and 𝐊¯, we may assume 𝐊𝔊{D}(p,p) with M(𝐊)=i=1pDmi for m1,,mp1, and furthermore that 𝐊¯𝔊(p,p), and that connecting the ith left input and ith right input of 𝐊𝐊¯, for i[p], reconstructs Ω (see Figure 4). Since 𝐊¯ is an -gadget and is quantum-gadget-closed, 𝐊¯ has signature F for some F. Then, with GF,

HolantΩ=tr((i=1pDmi)Fp,p) and HolantΩ{D}𝒢{D}=tr((i=1pDmi)Gp,p). (8)

As in (4), part 3 of [43, Proposition 3.1] gives Hp(FG)p,p=(FG)p,pHp. As in (5), the bottom left block of this equation is DpFp,p=Gp,pDp. Now applying (8), we have

HolantΩ =tr((i=1pDmi)Fp,p)=tr((i=1pDmi1)DpFp,p)
=tr((i=1pDmi1)Gp,pDp)=tr((i=1pDmi)Gp,p)
=HolantΩ{D}𝒢{D}.

Thus {D} and 𝒢{D} are Holant-indistinguishable. By induction, 19 gives that {D} and 𝒢{D} are ortho-equivalent. Therefore and 𝒢 are ortho-equivalent.

4 Consequences of Theorem 9

In this section, we exploit the expressiveness of the Holant framework to show that Theorem 9 encompasses a variety of existing results, and derive a few novel consequences.

4.1 Counting CSP and graph homomorphisms

For a signature set , define the counting constraint satisfaction problem #CSP() with constraint function set to be the problem Holant(𝒬). Vertices assigned signatures in and 𝒬 are constraints and variables, respectively, and an (𝒬)-grid Ω is a constraint-variable incidence graph, where a variable appears in all of its incident constraints. Then HolantΩ(𝒬) is the sum over all variable assignments of the product of the constraint evaluations. Like Holant, #CSP is a well-studied problem in counting complexity, with broad dichotomy theorems classifying #CSP() as either tractable or #P-hard [3, 19, 6, 5].

By inserting a dummy degree-2 constraint vertex assigned (=2)𝒬 between adjacent variable vertices and combining adjacent constraint vertices assigned =a and =b into a single constraint vertex assigned =a+b2, we see that Holant(𝒬) is equivalent to Holant(𝒬). Say and 𝒢 are isomorphic if there exists a permutation matrix H satisfying H=𝒢 – in other words, and 𝒢 are the same up to relabeling of their domains. Using a standard Vandermonde interpolation argument, Xia [41] shows that H satisfies H𝒬=𝒬 if and only H is a permutation matrix. Say that and 𝒢 are #CSP-indistinguishable if 𝒬 and 𝒢𝒬 are Holant-indistinguishable (in other words, every #CSP instance has the same value whether we use constraint functions from or from 𝒢). Applying Theorem 9 to 𝒬 and 𝒢𝒬, we obtain the main result of Young [42] for real-valued constraint functions.

Corollary 20.

Let and 𝒢 be sets of real-valued constraint functions. Then and 𝒢 are isomorphic if and only if and 𝒢 are #CSP-indistinguishable.

As discussed in Subsection 2.1, Holant(AX𝒬)#CSP(AX) counts the number of homomorphisms to the graph X. Therefore 20 is a generalization of the classical theorem of Lovász [26] that two graphs are isomorphic if and only if they admit the same number of homomorphisms from every graph.

Let 𝒬2𝒬 be the set of equality signatures of even arity. Schrijver [33] shows222The First Fundamental Theorem for Sq±O(q) (the group of signed permutation matrices) states that T(q)Sq±=𝒬2¯. It follows as in the proof of Theorem 15 that Stab(𝒬2)=Sq±. The fact that Stab(𝒬)=SqO(q) (the group of permutation matrices) similarly follows from the First Fundamental Theorem for Sq, which states that T(q)Sq=𝒬¯. that H satisfies H𝒬2=𝒬2 if and only if H is a signed permutation matrix (a matrix with entries in {0,±1} and exactly one nonzero entry in each row and column). As above, Holant(𝒬2) is equivalent to Holant(𝒬2) (critically, if =a𝒬2 and =b𝒬2, then =a+b2𝒬2). Then, defining #CSP2():=Holant(𝒬2) as #CSP() restricted to instances in which every variable appears an even number of times [7, 22], we have

Corollary 21.

Let and 𝒢 be sets of real-valued constraint functions. Then there is a signed permutation matrix P satisfying 𝒢=P if and only if and 𝒢 are #CSP2-indistinguishable.

In particular, since (unweighted) graph adjacency matrices AX and AY have entries in {0,1}, we have P2(AX)2,0=(AY)2,0(P)2(AX)2,0=(AY)2,0, where P is the permutation matrix created by flipping every 1 entry of P to 1. Therefore we have the following novel (to our knowledge) sharpening of Lovász’s theorem.

Corollary 22.

Graphs X and Y are isomorphic if and only if they admit the same number of homomorphisms from those graphs in which all vertices have even degree.

4.2 Simultaneous matrix similarity

Let and 𝒢 be sets of binary signatures, thought of as matrices. Any connected -grid Ω is a cycle. Breaking an edge of the cycle, we obtain a binary path gadget with signature matrix i=1cFi, where, depending on its orientation, each Fi or Fi. Connecting the path’s two dangling edges, we reform Ω, which thus has Holant value tr(i=1cFi). Let Γ be the set of all finite products of matrices in and :={FF}. Define Γ𝒢 similarly and, for a word wΓ, construct w𝒢Γ𝒢 by replacing every character F or F in w by the corresponding G or G, respectively. For orthogonal H, we have H=𝒢HF1,1=G1,1H for every FG (see Figure 3), so, in this setting, Theorem 9 is equivalent to the following real-valued case of a classical theorem from representation theory, due to Specht [36] and Wiegmann [40]. Grohe, Rattan, and Seppelt [21] also give a combinatorial proof.

Corollary 23.

Let ,𝒢q×q. Then there is an HO(q) such that HF=GH for every FG𝒢 if and only if tr(w)=tr(w𝒢) for every wΓ.

Suppose ={AX} and 𝒢={AY} for graphs X and Y. Transform an AX-grid Ω to a (AX𝒬)-grid Ω by inserting a dummy degree-2 vertex assigned (=2)𝒬 between every consecutive pair of vertices in the cycle. Recall from Subsection 2.1 that HolantΩ(AX𝒬) counts the number of homomorphisms from graph K to X, where K is the graph obtained from Ω by ignoring the vertices assigned AX. Here K is a cycle, so we have the following well-known result, an alternate formulation of this case of 23.

Corollary 24.

Let X and Y be graphs. Then there is an orthogonal matrix H satisfying HAX=AYH if and only if X and Y admit the same number of homomorphisms from all cycles.

A matrix H is pseudo-stochastic if all of its rows and columns sum to 1. Dell, Grohe, and Rattan [15] proved that graphs X and Y admit the same number of homomorphisms from all paths if and only if there is a pseudo-stochastic matrix H such that HAX=AYH. Theorem 9 gives a novel combination of this result with 24, and reproduces a combinatorial explanation for the connection between pseudo-stochastic matrices and homomorphisms from paths [21].

Corollary 25.

Let X and Y be graphs. Then there is a pseudo-stochastic orthogonal matrix H satisfying HAX=AYH if and only if X and Y admit the same number of homomorphisms from all cycles and paths.

Proof.

Consider Holant(AX{=1}). Any AX{=1}-grid is a disjoint union of cycles composed of signatures assigned AX and paths with degree-2 internal vertices assigned AX and degree-1 endpoints assigned (=1)𝒬. As discussed before 24, every cycle AX-grid Ω has the same Holant value as ΩAXAY iff X and Y admit the same number of homomorphisms from every cycle. Similarly, the Holant value of each path component is the number of homomorphisms to X from the underlying path. Thus X and Y admit the same number of homomorphisms from all cycles and all paths iff AX{=1} and AY{=1} are Holant-indistinguishable. By Theorem 9, this is equivalent to the existence of an orthogonal H satisfying HAX=AYH and H(=1)=(=1). The vector form of =1 is the all-ones vector, so H(=1)=(=1) if and only if the rows of H sum to 1 and (since H(=1)=(=1)H(=1)=(=1)) the columns of H sum to 1.

4.3 Odeco signature sets

Definition 26 (𝒢𝒬, odeco).

Define the set of general equalities (or weighted equalities) on domain [q] as 𝒢𝒬={=n𝐚n1,𝐚[q]}, where =n𝐚 is the symmetric n-ary signature defined by (=n𝐚)𝐱=aq if x1==xn=q, and (=n𝐚)𝐱=0 otherwise. A set of symmetric signatures is orthogonally decomposable, or odeco, if there is an HO(q) such that H𝒢𝒬.

Robeva [31] coined the term “odeco” for individual symmetric tensors (signatures). A binary 𝒢𝒬 signature has a diagonal signature matrix, so the spectral theorem states that every (real) symmetric binary signature is odeco. Any nonzero edge assignment for a connected 𝒢𝒬-gadget 𝐊 must assign all edges, including dangling edges, the same value, so, if 𝐊 has arity n and is composed of vertices assigned signatures with weights 𝐚1,,𝐚p, then 𝐊 has signature =n𝐚1𝐚p𝒢𝒬, where denotes entrywise product. Thus, if 𝒢𝒬, then Holant() is polynomial-time tractable.

For symmetric signatures F1,F2, construct the signature F1F2¯ from F1F2 by connecting an input of F1 and an input of F2 (see Figure 5).

Figure 5: Illustrating (the gadgets with signatures) F1F2 and F1~ for 6-ary F1 and 3-ary F2.

For 𝐱[q]n11 and 𝐲[q]n21, we have (with vectors viewed as input lists)

(F1F2)(𝐱,𝐲)=z[q]F1(𝐱,z)F2(𝐲,z).
Theorem 27.

Let be a set of real-valued symmetric tensors. The following are equivalent.

  1. (i)

    is odeco.

  2. (ii)

    Every connected -gadget has a symmetric signature.

  3. (iii)

    For every F1,F2, F1F2 is symmetric.

Robeva [31] conjectured the equivalence of items (i) and (iii) when contains a single signature. Boralevi, Draisma, Horobeţ, and Robeva [2] confirmed this conjecture using techniques from algebraic geometry. Using Theorem 9, we give a combinatorial proof for any set of symmetric signatures.

 Remark 28.

If is a set of symmetric binary signatures (matrices), then F1F2=F1F2=F1F2 (a matrix product). Symmetric matrices commute iff their product is symmetric, so Theorem 27 encompasses the fact that commuting symmetric matrices are simultaneously diagonalizable.

Proof of Theorem 27.

(i) (ii),(iii): Suppose H𝒢𝒬 for some HO(q). Let K¯ be the signature of a connected -gadget (e.g. K=F1F2). By 14, HK=J, where J is the signature of a connected 𝒢𝒬-gadget. Then J𝒢𝒬, so J, and thus K=H1J, are symmetric.

(ii) (i): By [43, Proposition 5.1], we may replace every F by FF to assume all signatures in have even arity. For F, let F~ be the matrix of the binary signature constructed by connecting all but one pair of inputs of F (see Figure 5). Every F~, and every F1~F2~ for F1,F2, is symmetric by assumption. Thus, as in 28, the F~ for F all commute.

Claim 29.

If 𝐊 is a connected binary -gadget with p vertices, assigned signatures F1,,Fp, then M(𝐊)=i=1pFi~.

We prove 29 by induction on p. For p=1, by the symmetry of F1, every connected binary F1-gadget with a single vertex has signature F1~. Now suppose p2. Then 𝐊 contains a vertex v whose removal does not disconnect 𝐊. Assume WLOG that v is assigned signature Fp. Construct 𝐊 from 𝐊 by breaking all but one edge between v and other vertices (see Figure 6). Since 𝐊 remains connected, its signature is symmetric by assumption. Create a binary gadget 𝐊′′ from 𝐊 by arbitrarily pairing up and connecting all but one dangling edge incident to v, and similarly pairing up and connecting all but one dangling edge incident to the other vertices of 𝐊. We may also recover 𝐊 from 𝐊 by connecting possibly different pairs of dangling edges (reforming the edges broken to create 𝐊) and, since the signature of 𝐊 is symmetric, the signature of a gadget produced by connecting dangling edges of 𝐊 does not depend on which pairs of dangling edges we connect (although the underlying graphs of the gadgets differ). Therefore M(𝐊′′)=M(𝐊).

Let 𝐊v′′ be the subgadget of 𝐊′′ induced by v. Then M(𝐊v′′)=Fp~ (see Figure 6), and 𝐊′′=𝐊v′′𝐊v′′¯. So, applying induction to 𝐊v′′¯, which has p1 vertices, gives M(𝐊)=M(𝐊′′)=M(𝐊v′′)M(𝐊v′′¯)=Fp~i=1p1Fi~=i=1pFi~ (recall that the Fi~ commute). This proves 29.

Figure 6: Illustrating the proof of 29 when v has a single incident dangling edge in 𝐊. The cases where v has zero or two incident dangling edges are similar.

The matrices F~ for F are symmetric and commute, so they are simultaneously diagonalizable: there is an HO(q) such that, for every F, HF~H=(=2𝐚F) for some 𝐚Fq. Replace with H to assume each F~=(=2𝐚F) (this does not change whether is odeco). Define 𝒢={=arity(F)𝐚FF}𝒢𝒬, a set similar to . Let Ω be an -grid, containing signatures F1,,Fp. Break some edge of Ω to produce a connected binary -gadget 𝐊. By 29,

M(𝐊)=i=1pFi~=i=1p(=2𝐚Fi)=(=2𝐚F1𝐚Fp)=M(𝐊𝒢).

Reconnecting the dangling edges of 𝐊, we find HolantΩ=HolantΩ𝒢. Thus and 𝒢 are Holant-indistinguishable, so, by Theorem 9, and 𝒢 are ortho-equivalent. Hence is odeco.

(iii) (ii): Let K be the n-ary signature of a connected -gadget 𝐊. Every unary signature is trivially symmetric, so assume n2. It suffices to show that, for any fixed partial input 𝐳[q]n2 to K and any x,y[q], we have K(x,y,𝐳)=K(y,x,𝐳) (where we assume WLOG that x and y are the first two inputs to K by reordering the dangling edges of 𝐊). Let u and w be the vertices of 𝐊 incident to the first and second dangling edges of 𝐊 (after reordering). If u=w then we are done, as every F is symmetric. Otherwise, since 𝐊 is connected, it contains a path P=(u=v0,v1,,vp2,vp1=w) from u to w, where vi is assigned signature Fi, for i[p]. Let E(P):={e0,e1,,ep1,ep} be the edges of P, including the dangling edges e0 and ep incident to u and w, respectively. Then ei and ei+1 are inputs to Fi for all i[p]. For any fixed assignment σ:E(𝐊)E(P)[q], define the matrix Fiσq×q by (Fiσ)a,b:=Fi(σ|δ(vi),a,b) (that is, fix the inputs to Fi from edges outside of E(P)). Then

K(x,y,𝐳)=σ:E(𝐊)E(P)[q]σ(D)=𝐳(vV(𝐊)PFv(σ|δ(v)))FPσ(x,y), (9)

where D is the ordered list of the last n2 dangling edges of 𝐊 and

FPσ(x,y) =ϕ:E(P)[q]ϕ(e0)=x,ϕ(ep)=yi=0p1Fi(σ|δ(vi),ϕ(ei),ϕ(ei+1))
=ϕ:E(P)[q]ϕ(e0)=x,ϕ(ep)=yi=0p1(Fiσ)ϕ(ei),ϕ(ei+1)=(i=0p1Fiσ)x,y.

On the RHS of (9), x and y appear only in FPσ(x,y). Thus it suffices to show that, for any fixed σ, FPσ(x,y)=FPσ(y,x). For any i,j[p] and a,b[q],

(FiσFjσ)a,b=z[q](Fiσ)a,z(Fjσ)z,b=z[q]Fi(σ|δ(vi),a,z)Fj(σ|δ(vj),b,z)
=(FiFj)(σ|δ(vi),a,σ|δ(vj),b)=(FiFj)(σ|δ(vi),b,σ|δ(vj),a)
=z[q]Fi(σ|δ(vi),b,z)Fj(σ|δ(vj),a,z)=z[q](Fiσ)b,z(Fjσ)z,a=(FiσFjσ)b,a,

where the fourth equality uses the assumption that FiFj is symmetric. Thus FiσFjσ is symmetric. Both Fiσ and Fjσ are symmetric, as Fi and Fj are symmetric, so, as in 28, Fiσ and Fjσ commute. Therefore

FPσ(x,y)=(i=0p1Fiσ)x,y=(i=0p1Fiσ)y,x=(i=0p1Fp1iσ)y,x=(i=0p1Fiσ)y,x=FPσ(y,x).

5 Possible Variations of Theorem 9

5.1 Complex-valued signatures

Although we have focused on real-valued signatures and matrices, the general and orthogonal Holant Theorems hold for complex-valued signatures and matrices. However, Theorem 9 does not hold for general sets and 𝒢 of complex-valued signatures, even when we allow H to be complex. Cai, Guo, and Williams [9] and Draisma and Regts [17] consider another counterexample involving vanishing signatures, namely the unary signature F[2]1 defined by F0=1 and F1=i. Any F-grid Ω with at least one vertex satisfies HolantΩ(F)=0, as Ω is a disjoint union of K2 complete graphs, each with value [1,i][1,i]=0. Thus F is Holant-indistinguishable from 0, but there is no orthogonal matrix H, real or complex, satisfying H[1,i]=[0,0].

Cai and Young [13] and Young [42] prove their counting indistinguishability theorems for complex-valued signature sets with the assumption that the sets are conjugate-closed, meaning they must contain the entrywise conjugate of each of their complex signatures. It is feasible that Theorem 9 could similarly hold for complex-valued conjugate-closed and 𝒢 and complex orthogonal H (this invalidates the above counterexample, as [1,i][1,i]0).

5.2 Quantum orthogonal matrices and planar signature grids

A quantum orthogonal matrix U is, roughly, a matrix whose entries are self-adjoint elements of an abstract, not necessarily commutative, C-algebra, satisfying the relation UU=UU=I𝟏, where 𝟏 is the identity element of the C-algebra. Just as a permutation matrix is an orthogonal matrix that stabilizes 𝒬, a quantum permutation matrix is a quantum orthogonal matrix that stabilizes 𝒬 (see e.g. [13, Equation 27]). The main theorem of Cai and Young [13], extending the result of Mančinska and Roberson [27], is a planar, quantum version of 20: and 𝒢 are PlHolant(𝒬)-indistinguishable (planar-#CSP-indistinguishable) if and only if there is a quantum permutation matrix U satisfying U=𝒢 ( and 𝒢 are quantum isomorphic). Removing 𝒬, we should obtain the following planar, quantum version of Theorem 9.

Conjecture 30.

Let , 𝒢 be sets of real-valued signatures. Then the following are equivalent.

  1. (i)

    PlHolantΩ()=PlHolantΩ𝒢(𝒢) for every planar -grid Ω.

  2. (ii)

    There is a quantum orthogonal matrix U such that U=𝒢.

Cai and Young [13, Theorem 5] prove (ii) (i) when U is a quantum permutation matrix; however, their proof only relies on U being a quantum orthogonal matrix. Therefore, to prove 30, it suffices to show (i) (ii). The Tannaka-Krein duality for the quantum symmetric group used by Mančinska and Roberson and Cai and Young [13, Theorem 3] has a more general version for the quantum orthogonal group Oq+ [27, Theorem 2.13]. This version is analogous to the theorem of Schrijver used to prove Theorem 15, but concerning quantum stabilizer subgroups of Oq+ and planar gadgets. Then, following the proof of [13, Theorem 4], but ommitting the gadgets E1,0 and E1,2 used to construct 𝒬, we will obtain a quantum analogue of our Theorem 15 for planar quantum -gadgets, giving a quantum analogue of 17. The rest of the proof of Theorem 9, however, involves nonplanar signature grid manipulations (e.g. in Figure 4 it is in general impossible to embed Ω such that every instance of D lies on the outer face) and, more critically, relies on the existence of the singular value decomposition of a submatrix of a real orthogonal matrix, then on viewing the resulting diagonal matrix as a signature. It is yet unclear whether the same or similar reasoning applies to a submatrix of a quantum orthogonal matrix.

References

  • [1] Arturo Acuaviva, Visu Makam, Harold Nieuwboer, David Pérez-García, Friedrich Sittner, Michael Walter, and Freek Witteveen. The minimal canonical form of a tensor network. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 328–362, Los Alamitos, CA, USA, November 2023. IEEE. doi:10.1109/FOCS57990.2023.00027.
  • [2] Ada Boralevi, Jan Draisma, Emil Horobeţ, and Elina Robeva. Orthogonal and unitary tensor decomposition from an algebraic perspective. Israel Journal of Mathematics, 222(1):223–260, October 2017. doi:10.1007/s11856-017-1588-6.
  • [3] Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34:1–34:41, October 2013. doi:10.1145/2528400.
  • [4] Jin-Yi Cai and Xi Chen. Complexity Dichotomies for Counting Problems, volume 1. Cambridge University Press, 2017. doi:10.1017/9781107477063.002.
  • [5] Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. J. ACM, 64(3):19:1–19:39, June 2017. doi:10.1145/2822891.
  • [6] Jin-Yi Cai, Xi Chen, and Pinyan Lu. Nonnegative weighted #csp: An effective complexity dichotomy. SIAM J. Comput., 45(6):2177–2198, 2016. doi:10.1137/15M1032314.
  • [7] Jin-Yi Cai, Zhiguo Fu, Heng Guo, and Tyson Williams. A holant dichotomy: Is the FKT algorithm universal? In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1259–1276. IEEE, IEEE Computer Society, 2015. doi:10.1109/FOCS.2015.81.
  • [8] Jin-yi Cai and Artem Govorov. On a theorem of lovász that (&sdot, H) determines the isomorphism type of H. ACM Trans. Comput. Theory, 13(2):11:1–11:25, 2021. doi:10.1145/3448641.
  • [9] Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. SIAM J. Comput., 45(5):1671–1728, 2016. doi:10.1137/15M1049798.
  • [10] Jin-Yi Cai and Jin Soo Ihm. Holant* dichotomy on domain size 3: A geometric perspective, 2025. doi:10.48550/arXiv.2504.14074.
  • [11] Jin-yi Cai, Pinyan Lu, and Mingji Xia. Holographic algorithms by fibonacci gates and holographic reductions for hardness. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 644–653. IEEE, IEEE Computer Society, 2008. doi:10.1109/FOCS.2008.34.
  • [12] Jin-yi Cai, Pinyan Lu, and Mingji Xia. Computational complexity of holant problems. SIAM J. Comput., 40(4):1101–1132, 2011. doi:10.1137/100814585.
  • [13] Jin-Yi Cai and Ben Young. Planar #csp equality corresponds to quantum isomorphism - A holant viewpoint. ACM Trans. Comput. Theory, 16(3):18:1–18:41, September 2024. doi:10.1145/3689486.
  • [14] Pierre de la Harpe and Vaughan F. R. Jones. Graph invariants related to statistical mechanical models: Examples and problems. J. Comb. Theory B, 57(2):207–227, March 1993. doi:10.1006/jctb.1993.1017.
  • [15] Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets weisfeiler and leman. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 40:1–40:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2018.40.
  • [16] Jan Draisma, Dion C. Gijswijt, László Lovász, Guus Regts, and Alexander Schrijver. Characterizing partition functions of the vertex model. Journal of Algebra, 350(1):197–206, January 2012. doi:10.1016/j.jalgebra.2011.10.030.
  • [17] Jan Draisma and Guus Regts. Tensor invariants for certain subgroups of the orthogonal group. Journal of Algebraic Combinatorics, 38(2):393–405, September 2013. doi:10.1007/s10801-012-0408-7.
  • [18] Zdenek Dvorák. On recognizing graphs by numbers of homomorphisms. J. Graph Theory, 64(4):330–342, 2010. doi:10.1002/jgt.20461.
  • [19] Martin E. Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM J. Comput., 42(3):1245–1274, 2013. doi:10.1137/100811258.
  • [20] Michael Freedman, László Lovász, and Alexander Schrijver. Reflection positivity, rank connectivity, and homomorphism of graphs. Journal of the American Mathematical Society, 20(1):37–51, 2007.
  • [21] Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism tensors and linear equations. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 70:1–70:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ICALP.2022.70.
  • [22] Sangxia Huang and Pinyan Lu. A dichotomy for real weighted holant problems. Comput. Complex., 25(1):255–304, 2016. doi:10.1007/s00037-015-0118-3.
  • [23] Jiabao Lin and Hanpin Wang. The complexity of boolean holant problems with nonnegative weights. SIAM J. Comput., 47(3):798–828, 2018. doi:10.1137/17M113304X.
  • [24] Yin Liu. A combinatorial view of holant problems on higher domains. In Computing and Combinatorics: 30th International Conference, COCOON 2024, Shanghai, China, August 23–25, 2024, Proceedings, Part II, pages 368–380, Berlin, Heidelberg, 2025. Springer-Verlag. doi:10.1007/978-981-96-1093-8_31.
  • [25] László Lovász. The rank of connection matrices and the dimension of graph algebras. Eur. J. Comb., 27(6):962–970, 2006. doi:10.1016/j.ejc.2005.04.012.
  • [26] László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):321–328, 1967.
  • [27] Laura Mancinska and David E. Roberson. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 661–672. IEEE, 2020. doi:10.1109/FOCS46700.2020.00067.
  • [28] Guus Regts. The rank of edge connection matrices and the dimension of algebras of invariant tensors. Eur. J. Comb., 33(6):1167–1173, August 2012. doi:10.1016/j.ejc.2012.01.014.
  • [29] Guus Regts. A characterization of edge-reflection positive partition functions of vertex-coloring models. In The Seventh European Conference on Combinatorics, Graph Theory and Applications, CRM Series, pages 305–311, Pisa, 2013. Scuola Normale Superiore. doi:10.1007/978-88-7642-475-5_49.
  • [30] Guus Regts. Graph parameters and invariants of the orthogonal group. PhD thesis, Universiteit van Amsterdam, 2013.
  • [31] Elina Robeva. Orthogonal decomposition of symmetric tensors. SIAM J. Matrix Anal. Appl., 37(1):86–102, January 2016. doi:10.1137/140989340.
  • [32] Alexander Schrijver. Graph Invariants in the Edge Model. In Martin Grötschel, Gyula O. H. Katona, and Gábor Sági, editors, Building Bridges: Between Mathematics and Computer Science, pages 487–498. Springer, Berlin, Heidelberg, 2008. doi:10.1007/978-3-540-85221-6_16.
  • [33] Alexander Schrijver. Tensor subalgebras and first fundamental theorems in invariant theory. Journal of Algebra, 319(3):1305–1319, February 2008. doi:10.1016/j.jalgebra.2007.10.039.
  • [34] Alexander Schrijver. Graph invariants in the spin model. J. Comb. Theory B, 99(2):502–511, 2009. doi:10.1016/j.jctb.2008.10.003.
  • [35] Shuai Shao and Jin-Yi Cai. A dichotomy for real boolean holant problems. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1091–1102. IEEE, 2020. doi:10.1109/FOCS46700.2020.00105.
  • [36] Wilhelm Specht. Zur theorie der matrizen. ii. Jahresbericht der Deutschen Mathematiker-Vereinigung, 50:19–23, 1940.
  • [37] Balázs Szegedy. Edge coloring models and reflection positivity. Journal of the American Mathematical Society, 20(4):969–988, May 2007. doi:10.1090/S0894-0347-07-00568-1.
  • [38] Leslie G. Valiant. Accidental algorithms. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 509–517. IEEE, IEEE Computer Society, 2006. doi:10.1109/FOCS.2006.7.
  • [39] Leslie G. Valiant. Holographic algorithms. SIAM J. Comput., 37(5):1565–1594, 2008. doi:10.1137/070682575.
  • [40] NA Wiegmann. Necessary and sufficient conditions for unitary similarity. Journal of the Australian Mathematical Society, 2(1):122–126, 1961.
  • [41] Mingji Xia. Holographic reduction: A domain changed application and its partial converse theorems. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, volume 6198 of Lecture Notes in Computer Science, pages 666–677. Springer, Springer, 2010. doi:10.1007/978-3-642-14165-2_56.
  • [42] Ben Young. Equality on all #csp instances yields constraint function isomorphism via interpolation and intertwiners, 2022. doi:10.48550/arXiv.2211.13688.
  • [43] Ben Young. The converse of the real orthogonal holant theorem, 2024. doi:10.48550/arXiv.2409.06911.