Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem

Cai, Jin-Yi; Young, Ben

doi:10.4230/LIPIcs.ITCS.2026.32

Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem

Jin-Yi Cai

Department of Computer Sciences, University of Wisconsin-Madison, WI, USA Ben Young

Department of Computer Sciences, University of Wisconsin-Madison, WI, USA

Abstract

Valiant’s Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ of tensors (a.k.a. constraint functions or signatures) are related by a holographic transformation, then $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are Holant-indistinguishable, i.e., every tensor network using tensors from $\operatorname{\mathcal{F}}$ , respectively from $\operatorname{\mathcal{G}}$ , contracts to the same value. Xia (ICALP 2010) conjectured the converse of the Holant theorem, but a counterexample was found based on vanishing signatures, those which are Holant-indistinguishable from 0.

We prove two near-converses of the Holant theorem using techniques from invariant theory. (I) Holant-indistinguishable $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their $\operatorname{GL}_{q}$ -orbit closures intersect. (II) We show that vanishing signatures are the only true obstacle to a converse of the Holant theorem. As corollaries of the two theorems we obtain the first characterization of homomorphism-indistinguishability over graphs of bounded degree, a long standing open problem, and show that two graphs with invertible adjacency matrices are isomorphic if and only if they are homomorphism-indistinguishable over graphs with maximum degree at most three. We also show that Holant-indistinguishability is complete for a complexity class TOCI introduced by Lysikov and Walter [41], and hence hard for graph isomorphism.

Keywords and phrases:

Holant, Orbit Closure Intersection, Homomorphism Indistinguishability, Tensor Network

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Combinatorics ; Mathematics of computing

\rightarrow

Graph theory ; Theory of computation

\rightarrow

Algebraic complexity theory

Related Version:

Full Version: https://arxiv.org/abs/2509.10991 [16]

Acknowledgements:

The authors thank Tim Seppelt for helpful discussions on homomorphism indistinguishability, and thank the referees for suggestions that improved the presentation of the paper.

DOI:

10.4230/LIPIcs.ITCS.2026.32

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Let $F,G\in\operatorname{\mathbb{C}}^{q\times q}$ be two matrices. If $F$ and $G$ are similar, then $\operatorname{tr}(F^{k})=\operatorname{tr}(G^{k})$ for every $k$ – that is, $F$ and $G$ are indistinguishable by the function $\operatorname{tr}((\cdot)^{k})$ . Conversely, if $\operatorname{tr}(F^{k})=\operatorname{tr}(G^{k})$ for every $k$ , then we may only conclude that $F$ and $G$ have the same multiset of eigenvalues; $F$ and $G$ are not necessarily similar. In addition, what other assumptions on $F$ and $G$ suffice to obtain similarity? The Holant theorem and questions about its converse are vast generalizations of this example.

Holant Problems and the Holant Theorem

Holant problems [12] are a framework for expressing counting problems on graphs. Let $\operatorname{\mathcal{F}}$ be a set of tensors over a finite-dimensional vector space $\operatorname{\mathbb{K}}^{q}$ (typically $\operatorname{\mathbb{K}}=\operatorname{\mathbb{C}}$ ). A signature grid, or a tensor network (see Table 1 for a translation between Holant and tensor network terminology), is a (multi)graph $\Omega$ with vertices assigned tensors from $\operatorname{\mathcal{F}}$ and edges acting as variables. Depending on the choice of $\operatorname{\mathcal{F}}$ , one can express many counting problems as the Holant value $\operatorname{Holant}_{\operatorname{\mathcal{F}}}(\Omega)$ , the contraction of $\Omega$ as a tensor network. These include the number of matchings, proper edge or vertex-colorings, and Eulerian orientations of $\Omega$ and the number of homomorphisms from $\Omega$ to a possibly weighted and directed graph $G$ . While Holant is very expressive, it is also restrictive enough to prove sweeping complexity dichotomy theorems. These classify $\operatorname{Holant}_{\operatorname{\mathcal{F}}}$ as either P-time tractable or #P-hard for any set $\operatorname{\mathcal{F}}$ [12, 11, 34, 9, 7, 38, 50, 13, 10]. While most existing work focuses on domain size $q=2$ or 3, the current work is for all $q$ .

Valiant’s Holant theorem [53, 52], the genesis for Holant problems, applies to bipartite signature grids $\Omega$ whose two bipartitions are assigned contravariant tensors from $\operatorname{\mathcal{F}}$ and covariant tensors from $\operatorname{\mathcal{F}}^{\prime}$ , respectively. The problem is denoted $\operatorname{Holant}_{\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}}$ . The theorem states that, if $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ are related by a holographic transformation then $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ are Holant-indistinguishable, meaning that every signature grid $\Omega$ has the same Holant value whether its vertices are assigned tensors from $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ or the corresponding transformed tensors in $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ . This implies that $\operatorname{Holant}_{\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}}$ and $\operatorname{Holant}_{\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{% \prime}}$ have the same complexity, leading to the notions of holographic reductions between Holant problems and holographic algorithms. Xia [55] conjectured the converse of the Holant theorem: if $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ are Holant-indistinguishable, then there is a holographic transformation between them. But a counterexample was found in [9] based on vanishing signatures, those $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ which are Holant-indistinguishable from the set of all-0 tensors.

Homomorphism Indistinguishability

The Holant framework is broader than graph homomorphism [39, 32]. The results in this paper encompass a long list of other results in this area of research. Most prominently this includes homomorphism indistinguishability of graphs. Lovász [39] showed that two graphs $F$ and $G$ are isomorphic if and only if they admit the same number of homomorphisms from all graphs. This result was later improved to weighted $F$ and $G$ [40, 49, 8]. Another line of work aims to determine the relaxations of isomorphism which must relate any $F$ and $G$ indistinguishable under homomorphism counts from restricted classes $\mathfrak{G}$ of graphs [24, 18, 42, 36, 44, 31, 47]. One notable graph class $\mathfrak{G}$ whose homomorphism indistinguishability relation had, since the seminal 2010 work of Dvořák [24], eluded any full characterization is the graphs of bounded degree. Roberson [46] showed that homomorphism indistinguishability from graphs of degree at most $d$ define distinct relations strictly weaker than isomorphism on the set of graphs for distinct $d$ , but did not characterize them further. By expressing bounded-degree graph homomorphism as a bipartite Holant problem, we obtain as a corollary of our first main theorem the first characterization of its indistinguishability relation.

Indistinguishability theorems also exist for other subclasses of Holant, including #CSP and vertex and edge-coloring models [51, 48, 45, 15, 57]. The novel connections developed in this work demonstrate the advantage of expressing, via Holant, counting problems such as graph homomorphism and #CSP as tensor networks, which appear in a host of other areas and are subject to powerful theorems from invariant theory.

Orbit Equality and Orbit Closure Intersection

The $\operatorname{GL}_{q}$ -orbit of a finite set $\operatorname{\mathcal{F}}$ of tensors is the set $\{T\cdot\operatorname{\mathcal{F}}\mid T\in\operatorname{GL}_{q}\}$ , where $T$ acts simultaneously on the tensors in $\operatorname{\mathcal{F}}$ , in our setting by holographic transformation. Therefore the converse of the Holant theorem would state that, if $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ are Holant-indistinguishable, then the $\operatorname{GL}_{q}$ -orbits of $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ intersect and hence are equal. A weaker and often better-behaved notion is that of orbit closure intersection (Euclidean closure, for $\operatorname{\mathbb{K}}=\operatorname{\mathbb{C}}$ ). There has been much research in recent years on the computational complexity of orbit intersection and orbit closure intersection [29, 17, 30, 35, 21, 2, 27, 1, 41], with connections to geometric complexity theory [37], including border rank with applications to matrix multiplication [4], and polynomial identity testing.

Several such works [21, 27, 35, 1, 41] apply a theorem (Theorem 16 below) from geometric invariant theory which states that the $H$ -orbit closures of $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ intersect if and only if $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are indistinguishable by all $H$ -invariant polynomials (i.e. every such polynomial takes the same value on inputs $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ ). The authors of [1] study a family of vertex-regular tensor networks from quantum physics called PEPS networks, which admit a variant of holographic transformation called a gauge transformation. A PEPS signature set $\operatorname{\mathcal{F}}$ has common arity $2n$ , with inputs paired into $n$ dimensions (with possibly distinct domains) and only allows contractions between inputs in the same dimension. Since every $\operatorname{GL}_{q}$ -invariant polynomial is a linear combination of contractions of PEPS networks, $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are indistinguishable by all PEPS networks if and only if the $\operatorname{GL}_{q}$ -orbit closures of $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ intersect [1, Theorem 4.11]. Lysikov and Walter [41] define the complexity class TOCI of orbit closure intersection problems, showing that it contains GI (all problems reducible to graph isomorphism).

Our Results

We develop new connections between invariant theory and counting problems to prove two near-converses of the Holant theorem. First, we show that the converse of the Holant theorem holds for orbit closure intersection instead of orbit intersection as conjectured in [55].

Theorem (Theorem 19).

Finite $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ are Holant-indistinguishable if and only if the $\operatorname{GL}_{q}$ -orbit closures of $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ intersect.

The latter condition means there are two sequences of holographic transformations taking $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ arbitrarily close to each other. The key idea in the proof is to show that every $\operatorname{GL}_{q}$ -invariant polynomial is realizable as a sum of the Holant values of indeterminate-valued signature grids. A special case is a characterization of vanishing sets which applies to any set on any domain. This greatly generalizes the symmetric Boolean-domain characterization of [9]. It also follows that the problem of testing whether $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ are Holant-indistinguishable is decidable.

Our second near-converse of the Holant theorem does give a true holographic transformation between $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ , but requires that $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ be quantum-nonvanishing. This means that $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ cannot produce a quantum gadget (a linear combination of contractions of tensors in $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ ) that causes every $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ -grid containing it to have Holant value 0.

Theorem (Theorem 23).

If $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ are Holant-indistinguishable and quantum-nonvanishing, then there is a holographic transformation between $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ .

The proof of this theorem uses an invariant-theoretic characterization due to Derksen and Makam [23] of quantum $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ -gadgets for quantum-nonvanishing $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ , analogous to the duality theorems used to prove existing indistinguishability results [42, 56, 15, 57]. However, the other proof techniques used in these works do not apply in our setting; in particular, the domain-induction approach of Young [57] fails because subsignatures of $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ do not necessarily inherit the quantum-nonvanishing property. Instead, we use Derksen and Makam’s theorem to initially split the problem into two subdomains, then gradually refine these subdomains by holographic transformations until quantum-nonvanishing forces $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}=\operatorname{% \mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ . We use similar techniques to prove Theorem 24, a variant of the second main theorem for quantum-nonvanishing sets $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ of matrices: every product of matrices in $\operatorname{\mathcal{F}}$ has the same trace as the corresponding product in $\operatorname{\mathcal{G}}$ if and only if $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are simultaneously similar. The proof of this result is “constructive” in the sense that the recovered transformation between $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ is composed of Jordan decompositions of quantum- $\operatorname{\mathcal{F}}$ -gadget-realizable matrices, and of these matrices themselves (although the gadgets are obtained nonconstructively). The proof of the second main theorem is similarly “constructive” except for the application of Derksen and Makam’s theorem.

We use Theorem 23 to show that, while homomorphism indistinguishability of graphs $F$ and $G$ over graphs of any bounded degree is not in general equivalent to isomorphism, homomorphism indistinguishability over graphs of maximum degree at most three is equivalent to isomorphism for $F$ and $G$ with invertible adjacency matrices. We also apply Theorem 19 and results of [41] to show that the problem of Holant-indistinguishability is TOCI-complete and GI-hard.

2 Background and Preliminaries

Throughout, let $\operatorname{\mathbb{K}}$ be an algebraically closed field of characteristic 0. We work with the finite-dimensional vector space $\operatorname{\mathbb{K}}^{q}$ and its dual $(\operatorname{\mathbb{K}}^{q})^{*}$ . The mixed tensor algebra over $\operatorname{\mathbb{K}}^{q}$ is

\operatorname{\mathcal{V}}=\operatorname{\mathcal{V}}(\operatorname{\mathbb{K}% }^{q}):=\bigcup_{\ell,r\geq 0}\mathchoice{\mathop{}\kern 3.84726pt\mathopen{% \vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}% \kern 3.84726pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[% 0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen% {\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}% \operatorname{\mathcal{V}}_{r},\text{ where }\mathchoice{\mathop{}\kern 3.8472% 6pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell% }}}{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.48% 613pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{% \ell}}}\operatorname{\mathcal{V}}_{r}=(\operatorname{\mathbb{K}}^{q})^{\otimes% \ell}\otimes((\operatorname{\mathbb{K}}^{q})^{*})^{\otimes r}.

$\operatorname{\mathcal{V}}(\operatorname{\mathbb{K}}^{q})$ is bigraded $\operatorname{\mathbb{K}}$ -vector space (each grade $\mathchoice{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\operatorname{\mathcal% {V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.84726pt\mathopen{% \vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}% \kern 3.48613pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[% 0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}\operatorname{\mathcal{V}}_{r}$ is a $\operatorname{\mathbb{K}}$ -vector space) and admits the usual tensor product $\otimes:\mathchoice{\mathop{}\kern 7.75009pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{1}}}}{\mathop{}\kern 7.75009pt% \mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{1% }}}}{\mathop{}\kern 7.38896pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_% {\mathmakebox[0pt][r]{\ell_{1}}}}{\mathop{}\kern 7.38896pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{1}}}}\operatorname{% \mathcal{V}}_{r_{1}}\times\mathchoice{\mathop{}\kern 7.75009pt\mathopen{% \vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{2}}}}{% \mathop{}\kern 7.75009pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{\ell_{2}}}}{\mathop{}\kern 7.38896pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{2}}}}{\mathop{}\kern 7% .38896pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]% {\ell_{2}}}}\operatorname{\mathcal{V}}_{r_{2}}\to\mathchoice{\mathop{}\kern 21% .1391pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{% \ell_{1}+\ell_{2}}}}{\mathop{}\kern 21.1391pt\mathopen{\vphantom{\operatorname% {\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{1}+\ell_{2}}}}{\mathop{}\kern 19.4% 169pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{% \ell_{1}+\ell_{2}}}}{\mathop{}\kern 19.4169pt\mathopen{\vphantom{\operatorname% {\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{1}+\ell_{2}}}}\operatorname{% \mathcal{V}}_{r_{1}+r_{2}}$ . Tensors in $\bigcup_{n\geq 1}\mathchoice{\mathop{}\kern 5.44333pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 5.44333% pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{n}}}{% \mathop{}\kern 4.90399pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4.90399pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{n}}}\operatorname{\mathcal{% V}}_{0}\subset\operatorname{\mathcal{V}}(\operatorname{\mathbb{K}}^{q})$ are called contravariant, and tensors in $\bigcup_{n\geq 1}\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4.48613% pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{0}}}{% \mathop{}\kern 3.90283pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{0}}}\operatorname{\mathcal{% V}}_{n}$ are called covariant. Tensors in $\mathchoice{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\operatorname{\mathcal% {V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.84726pt\mathopen{% \vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}% \kern 3.48613pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[% 0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}\operatorname{\mathcal{V}}_{r}$ are said to have arity $\ell+r$ , with left arity $\ell$ and right arity $r$ . Note that $\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\operatorname{\mathcal% {V}}}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4.48613pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283% pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{0}}}{% \mathop{}\kern 3.90283pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{0}}}\operatorname{\mathcal{V}}_{0}=\operatorname{\mathbb{% K}}$ . Given $A=\sum_{i,j=1}^{q}a_{i,j}e_{i}\otimes e_{j}\in\mathchoice{\mathop{}\kern 4.486% 13pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{2}}% }{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{2}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{2}}}{\mathop{}\kern 3.90283% pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{2}}}% \operatorname{\mathcal{V}}_{0}$ , define $A^{1,1}=\sum_{i,j=1}^{q}a_{i,j}e_{i}\otimes e_{j}^{*}\in\mathchoice{\mathop{}% \kern 4.48613pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[% 0pt][r]{1}}}{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}% \kern 3.90283pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[% 0pt][r]{1}}}\operatorname{\mathcal{V}}_{1}$ . View $A^{1,1}$ as a matrix $(a_{i,j})_{i,j=1}^{q}\in\operatorname{\mathbb{K}}^{q\times q}$ ; in general, identify

\sum_{i_{1},\ldots,i_{\ell}=1}^{q}\sum_{j_{1},\ldots,j_{r}=1}^{q}a_{i_{1},% \ldots,i_{\ell},j_{1},\ldots,j_{r}}e_{i_{1}}\otimes\ldots\otimes e_{i_{\ell}}% \otimes e_{j_{1}}^{*}\otimes\ldots\otimes e_{j_{r}}^{*}\in(\operatorname{% \mathbb{K}}^{q})^{\otimes\ell}\otimes((\operatorname{\mathbb{K}}^{q})^{*})^{% \otimes r}

with a matrix in $\operatorname{\mathbb{K}}^{q^{\ell}\times q^{r}}$ (indexed by $[q]^{\ell}\times[q]^{r}$ lexicographically) whose $i_{1}\ldots i_{\ell},j_{1}\ldots j_{r}$ -entry is $a_{i_{1},\ldots,i_{\ell},j_{1},\ldots,j_{r}}$ . In particular, contravariant and covariant tensors are column and row vectors, respectively.

2.1 Holant and Bi-Holant

A signature is a function $F:[q]^{n}\to\operatorname{\mathbb{K}}$ on $n=\operatorname{arity}(F)$ inputs from a finite domain $[q]$ . Use $\operatorname{\mathcal{F}}$ to denote a set of signatures sharing a common domain $[q]$ , but possibly with different arities. Given $\operatorname{\mathcal{F}}$ , a signature grid (or $\operatorname{\mathcal{F}}$ -grid) $\Omega$ is a multigraph along with an assignment of an $n$ -ary $F_{v}\in\operatorname{\mathcal{F}}$ to each degree- $n$ vertex $v$ in $\Omega$ , with an ordering of the $n$ edges $\delta(v)$ incident to $v$ to serve as the $n$ inputs to $F$ . $\operatorname{Holant}_{\operatorname{\mathcal{F}}}$ is the computational problem: Given $\Omega$ , compute the Holant value

\operatorname{Holant}_{\operatorname{\mathcal{F}}}(\Omega)=\sum_{\sigma:E(% \Omega)\to[q]}\prod_{v\in V(\Omega)}F_{v}(\sigma(\delta(v)))

of $\Omega$ , where $F_{v}(\sigma(\delta(v)))$ is the evaluation of $F_{v}$ on the $n$ domain elements assigned to the incident edges of $v$ . For example, suppose $\operatorname{\mathcal{F}}$ consists of, for each $n\geq 1$ , the $n$ -ary $\{0,1\}$ -valued signature on the Boolean domain $\{0,1\}$ ( $q=2$ ) that evaluates to 1 if at most one (resp. exactly one) of its inputs is 1, and evaluates to 0 otherwise. For any $\Omega$ , let $\sigma$ have a nonzero evaluation. The edges assigned 1 form a matching (resp. perfect matching) in $\Omega$ , so $\operatorname{Holant}_{\operatorname{\mathcal{F}}}(\Omega)$ equals the number of matchings (resp. perfect matchings) in $\Omega$ .

The coefficients of a tensor $F\in\mathchoice{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.84726pt\mathopen% {\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{% }\kern 3.48613pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox% [0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}\operatorname{\mathcal{V}}_{r}$ define an $(\ell+r)$ -arity signature on domain $[q]$ . In this work, we will think of signatures as tensors in this way. We view a single $n$ -ary signature as taking different shapes (i.e. different choices of $(\ell,r)$ : $\ell+r=n$ ), or as in the case of unrestricted Holant above, ignore this covariant/contravariant input distinction, depending on the context. Viewing signatures as fully contravariant or covariant gives the following well-studied bipartite setting.

Definition 1 ( $\operatorname{Holant}_{\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}}$ ).

Let $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{F}}^{\prime}$ be sets of contravariant and covariant tensors, respectively. An $(\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime})$ -grid $\Omega$ is a bipartite $(\operatorname{\mathcal{F}}\sqcup\operatorname{\mathcal{F}}^{\prime})$ -grid $\Omega$ in which the vertices in the two bipartitions are assigned signatures from $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{F}}^{\prime}$ , respectively.

We will abbreviate $(F|F^{\prime}):=(\{F\}|\{F^{\prime}\})$ for individual signatures $F,F^{\prime}$ .

Definition 2 ( $\operatorname{\mathcal{EQ}},=_{n}$ ).

Define the set of equality signatures $\operatorname{\mathcal{EQ}}=\{=_{n}\mid n\geq 1\}$ , where $=_{n}$ is the $n$ -ary signature defined by $(=_{n})(x_{1},\ldots,x_{n})=1$ if $x_{1}=\ldots=x_{n}$ , and 0 otherwise.

Proposition 3.

For any $\operatorname{\mathcal{F}}\subset\operatorname{\mathcal{V}}$ , $\operatorname{Holant}_{\operatorname{\mathcal{F}}}$ , $\operatorname{Holant}_{=_{2}|\operatorname{\mathcal{F}}}$ , and $\operatorname{Holant}_{=_{2}|\operatorname{\mathcal{F}},=_{2}}$ are equivalent.

Proof.

Convert an $\operatorname{\mathcal{F}}$ -grid $\Omega$ into a $(=_{2}|\operatorname{\mathcal{F}})$ -grid (which is also a $(=_{2}|\operatorname{\mathcal{F}},=_{2})$ -grid) by placing a degree-2 vertex assigned $=_{2}$ on each edge. The resulting grid is bipartite and has the same Holant value. Conversely, given an $(=_{2}|\operatorname{\mathcal{F}},=_{2})$ -grid $\Omega$ , merge two incident edges of any $=_{2}$ into one. $\hfill\blacktriangleleft$

For a problem (only easily) expressible in the bipartite setting, consider the problem of counting homomorphisms from graphs of bounded degree. A graph homomorphism from graph $X$ to graph $G$ is a map $\varphi:V(X)\to V(G)$ such that, for every edge $u v$ of $X$ , $\varphi(u)\varphi(v)$ is an edge of $G$ . Let $V(G)=[q]$ and $A_{G}\in\{0,1\}^{q\times q}$ be the adjacency matrix of $G$ , thought of as a binary signature. Construct the bijection between graphs $X$ and $\operatorname{\mathcal{EQ}}|A_{G}$ -grids $\Omega_{X}$ shown in Figure 1 satisfying $\operatorname{Holant}_{\operatorname{\mathcal{EQ}}|A_{G}}(\Omega_{X})=\hom(X,G)$ , the number of homomorphisms from $X$ to $G$ .

Figure 1: A graph

X

and

\operatorname{\mathcal{EQ}}|A_{G}

-grid

\Omega_{X}

such that

\operatorname{Holant}(\Omega_{X})=\hom(X,G)

.

By the same construction, defining $\operatorname{\mathcal{EQ}}_{\leq d}\subset\operatorname{\mathcal{EQ}}$ to be the set of equality signatures of arity at most $d$ , $\operatorname{Holant}_{\operatorname{\mathcal{EQ}}_{\leq d}|A_{G}}$ captures the problem of counting homomorphisms from graphs $X$ of maximum degree at most $d$ to $G$ . $\operatorname{Holant}_{\operatorname{\mathcal{EQ}}|A_{G}}$ is equivalent to the non-bipartite $\operatorname{Holant}_{\operatorname{\mathcal{EQ}}\cup\{A_{G}\}}$ because we can, without affecting the Holant value, insert a dummy $=_{2}$ between any two adjacent $A_{G}$ vertices and combine adjacent $=_{a}$ and $=_{b}$ vertices into a single vertex assigned $=_{a+b-2}$ . However, expressing homomorphisms from bounded-degree graphs does require bipartiteness, because merging two equality signatures of arity $\leq d$ could produce an equality signature of arity $>d$ .

Definition 4 (Bi-Holant).

For $\operatorname{\mathcal{F}}\subset\operatorname{\mathcal{V}}(\operatorname{% \mathbb{K}}^{q})$ , a Bi-Holant $\operatorname{\mathcal{F}}$ -grid $\Omega$ is a Holant $\operatorname{\mathcal{F}}$ -grid respecting the shapes of its signatures – that is, the edge between any adjacent $u$ and $v$ must be a contravariant input to $F_{u}$ and a covariant input to $F_{v}$ , or vice-versa.

If $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{F}}^{\prime}$ are sets of contravariant and covariant tensors, respectively, then $\operatorname{Bi-Holant}_{\operatorname{\mathcal{F}}\cup\operatorname{\mathcal% {F}}^{\prime}}$ is equivalent to $\operatorname{Holant}_{\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}}$ . Thus, by Proposition 3, Bi-Holant generalizes Holant.

Definition 5 ((Bi-Holant) $\operatorname{\mathcal{F}}$ -gadget).

For $\operatorname{\mathcal{F}}\subset\operatorname{\mathcal{V}}(\operatorname{% \mathbb{K}}^{q})$ , an $\operatorname{\mathcal{F}}$ -gadget is Bi-Holant $\operatorname{\mathcal{F}}$ -grid in which zero or more edges are dangling, with zero or one endpoints not incident to any vertex. In an $(\ell,r)$ - $\operatorname{\mathcal{F}}$ -gadget, $\ell$ dangling edges are contravariant inputs to their incident signatures, and $r$ are covariant, drawn with left-facing and right-facing dangling ends, respectively. The dangling ends are ordered from top to bottom on both the left and right. A two-sided dangling edge (called a wire) always has one contravariant and one covariant dangling end.

Define the signature $K\in\mathchoice{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.84726pt\mathopen% {\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{% }\kern 3.48613pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox% [0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}\operatorname{\mathcal{V}}_{r}$ of an $(\ell,r)$ - $\operatorname{\mathcal{F}}$ -gadget $\operatorname{\mathbf{K}}$ by letting $K(a_{1},\ldots,a_{\ell},b_{1},\ldots,b_{r})$ be the Holant value of $\operatorname{\mathbf{K}}$ when the $\ell$ left and $r$ right dangling edges are fixed to values $a_{1},\ldots,a_{\ell}$ and $b_{1},\ldots,b_{r}$ (summing only over assignments $\sigma$ to the internal edges). The signature of a wire is $(=_{2})=I\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 4.48613% pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{1}}}{% \mathop{}\kern 3.90283pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{1}}}\operatorname{\mathcal{% V}}_{1}$ , as the inputs to its two ends must match.

Gadgets are defined so that, if $F$ is the signature of an $\operatorname{\mathcal{F}}$ -gadget $\operatorname{\mathbf{K}}_{F}$ , then any $(\operatorname{\mathcal{F}}\cup\{F\})$ -grid corresponds to an $\operatorname{\mathcal{F}}$ -grid with the same Holant value constructed by replacing every vertex assigned $F$ with $\operatorname{\mathbf{K}}_{F}$ (with appropriately ordered dangling edges). $\operatorname{Bi-Holant}_{\operatorname{\mathcal{F}}}(\Omega)$ is the value of the contraction of $\Omega$ as a tensor network via the standard bilinear form $\langle\cdot,\cdot\rangle:\mathchoice{\mathop{}\kern 3.84726pt\mathopen{% \vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}% \kern 3.84726pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[% 0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen% {\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}% \operatorname{\mathcal{V}}_{r}\times\mathchoice{\mathop{}\kern 4.42825pt% \mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{r}}}{% \mathop{}\kern 4.42825pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{r}}}{\mathop{}\kern 4.03014pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{r}}}{\mathop{}\kern 4.03014% pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{r}}}% \operatorname{\mathcal{V}}_{\ell}\to\operatorname{\mathbb{K}}$ that contracts covariant inputs with contravariant inputs and vice-versa. For example, slicing the $n$ edges of an $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ -grid $\Omega$ yields two gadgets with signatures $F_{1}\in\mathchoice{\mathop{}\kern 5.44333pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 5.44333pt\mathopen{% \vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}% \kern 4.90399pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[% 0pt][r]{n}}}{\mathop{}\kern 4.90399pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{n}}}\operatorname{\mathcal{V}}_{0}$ and $F_{2}^{*}\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4.48613% pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{0}}}{% \mathop{}\kern 3.90283pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{0}}}\operatorname{\mathcal{% V}}_{n}$ such that $\operatorname{Holant}_{\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}}(\Omega)=\langle F_{1},F_{2}\rangle=F_{2}^{*}(F_{1})$ . More generally, if $F_{1}\in\mathchoice{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.84726pt\mathopen% {\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{% }\kern 3.48613pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox% [0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}\operatorname{\mathcal{V}}_{m}$ and $F_{2}\in\mathchoice{\mathop{}\kern 7.59612pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{m}}}{\mathop{}\kern 7.59612pt\mathopen{% \vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{m}}}{\mathop{}% \kern 6.64014pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[% 0pt][r]{m}}}{\mathop{}\kern 6.64014pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{m}}}\operatorname{\mathcal{V}}_{r}$ are the signatures of $\operatorname{\mathcal{F}}$ -gadgets $\operatorname{\mathbf{K}}_{1}$ and $\operatorname{\mathbf{K}}_{2}$ , then the signature of the $\operatorname{\mathcal{F}}$ -gadget constructed by connecting the $m$ right dangling edges of $\operatorname{\mathbf{K}}_{1}$ with the $m$ left dangling edges of $\operatorname{\mathbf{K}}_{2}$ (equivalently, contracting the $m$ covariant inputs of $F_{1}$ with the $m$ contravariant inputs of $F_{2}$ ) has matrix form $F_{1}F_{2}$ , the matrix composition of $F_{1}$ and $F_{2}$ . If $r=\ell$ , then $\langle F_{1},F_{2}\rangle=\operatorname{tr}(F_{1}F_{2})=\operatorname{Bi-% Holant}(\Omega)$ , where $\Omega$ is constructed by also connecting the $\ell$ left dangling edges of $\operatorname{\mathbf{K}}_{1}$ with the $\ell$ right dangling edges of $\operatorname{\mathbf{K}}_{2}$ .

Definition 6 ( $\operatorname{\mathfrak{Q}}_{\operatorname{\mathcal{F}}},\left\langle% \operatorname{\mathcal{F}}\right\rangle$ ).

An $(\ell,r)$ -quantum- $\operatorname{\mathcal{F}}$ -gadget $\operatorname{\mathbf{K}}$ is a formal $\operatorname{\mathbb{K}}$ -linear combination of $(\ell,r)$ - $\operatorname{\mathcal{F}}$ -gadgets. Define $\operatorname{\mathfrak{Q}}_{\operatorname{\mathcal{F}}}$ and $\left\langle\operatorname{\mathcal{F}}\right\rangle$ to be the spaces of all quantum- $\operatorname{\mathcal{F}}$ -gadgets and quantum- $\operatorname{\mathcal{F}}$ -gadget signatures, respectively (extending the signature function linearly), and $\mathchoice{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{\ell}}}{% \mathop{}\kern 3.84726pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {F}}\right\rangle}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}\right\rangle}}_{% \mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{\ell}}}% \left\langle\operatorname{\mathcal{F}}\right\rangle_{r}:=\left\langle% \operatorname{\mathcal{F}}\right\rangle\cap\mathchoice{\mathop{}\kern 3.84726% pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}% }}{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.48% 613pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{% \ell}}}\operatorname{\mathcal{V}}_{r}$ .

(a)

=_{2}

in

\mathchoice{\mathop{}\kern 4.34995pt\mathopen{\vphantom{\operatorname{\mathcal% {V}}}}_{\mathmakebox[0pt][r]{2}}}{\mathop{}\kern 4.34995pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{2}}}{\mathop{}\kern 2.75pt% \mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{2}}}{% \mathop{}\kern 2.75pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{2}}}\operatorname{\mathcal{V}}_{0}

(top left),

\mathchoice{\mathop{}\kern 4.34995pt\mathopen{\vphantom{\operatorname{\mathcal% {V}}}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4.34995pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 2.75pt% \mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{0}}}{% \mathop{}\kern 2.75pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{0}}}\operatorname{\mathcal{V}}_{2}

(top right) and

\mathchoice{\mathop{}\kern 4.34995pt\mathopen{\vphantom{\operatorname{\mathcal% {V}}}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 4.34995pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 2.75pt% \mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{1}}}{% \mathop{}\kern 2.75pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{1}}}\operatorname{\mathcal{V}}_{1}

(bottom), respectively.

(b) A

(3,1)

-quantum-

\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}

-gadget. Note that left/right dangling edges are incident to vertices in

\operatorname{\mathcal{F}}

/

\operatorname{\mathcal{F}}^{\prime}

, respectively.

Figure 2: Examples of (quantum) gadgets.

See 2(b). Quantum gadgets get their name from quantum labeled graphs [26], of which they are a broad generalization. While $\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}% \kern 4.48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}% \right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[% 0pt][r]{1}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}\left% \langle\operatorname{\mathcal{F}}\right\rangle_{1}$ always contains $I=(=_{2})^{1,1}$ as the signature of a wire, we do not always have $(=_{2})\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}% \kern 4.48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}% \right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[% 0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}\left% \langle\operatorname{\mathcal{F}}\right\rangle_{2}$ or $(=_{2})\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{2}}}{\mathop{}% \kern 4.48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}% \right\rangle}}_{\mathmakebox[0pt][r]{2}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[% 0pt][r]{2}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{2}}}\left% \langle\operatorname{\mathcal{F}}\right\rangle_{0}$ (see 2(a)); such a co/contravariant $(=_{2})$ is quite powerful, as it allows connecting two left or two right dangling edges with each other, circumventing bipartiteness, and allows reshaping tensors – e.g. construct $A^{1,1}$ from $A\in(\operatorname{\mathbb{K}}^{q})^{\otimes 2}$ by connecting a right-facing $(=_{2})$ to the second input of $A$ .

2.2 Transformations, Indistinguishability, and the Holant Theorem

Throughout, we treat pairs $\operatorname{\mathcal{F}},\operatorname{\mathcal{G}}\subset\operatorname{% \mathcal{V}}$ of signature sets that are bijective, meaning there is a left- and right-arity-preserving bijection $\leftrightsquigarrow$ between $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ . Call $\operatorname{\mathcal{F}}\ni F\leftrightsquigarrow G\in\operatorname{\mathcal% {G}}$ corresponding signatures.

Definition 7 ( $(\cdot)_{\operatorname{\mathcal{F}}\to\operatorname{\mathcal{G}}}$ , (Bi-)Holant-indistinguishable).

Given a $\operatorname{\mathbf{K}}\in\operatorname{\mathfrak{Q}}_{\operatorname{% \mathcal{F}}}$ (possibly with no dangling edges, in which case $\operatorname{\mathbf{K}}=\Omega$ is a quantum $\operatorname{\mathcal{F}}$ -grid), construct $\operatorname{\mathbf{K}}_{\operatorname{\mathcal{F}}\to\operatorname{\mathcal% {G}}}\in\operatorname{\mathfrak{Q}}_{\operatorname{\mathcal{G}}}$ by replacing every $F\in\operatorname{\mathcal{F}}$ in every term of $\operatorname{\mathbf{K}}$ with the corresponding $G\in\operatorname{\mathcal{G}}$ .

Say that $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are Holant-indistinguishable if $\operatorname{Holant}_{\operatorname{\mathcal{F}}}(\Omega)=\operatorname{% Holant}_{\operatorname{\mathcal{G}}}(\Omega_{\operatorname{\mathcal{F}}\to% \operatorname{\mathcal{G}}})$ for every $\operatorname{\mathcal{F}}$ -grid $\Omega$ . Define Bi-Holant-indistinguishable similarly.

Viewing $\left\langle\operatorname{\mathcal{F}}\right\rangle$ and $\left\langle\operatorname{\mathcal{G}}\right\rangle$ as multisets in bijection with $\operatorname{\mathfrak{Q}}_{\operatorname{\mathcal{F}}}$ and $\operatorname{\mathfrak{Q}}_{\operatorname{\mathcal{G}}}$ , the $(\cdot)_{\operatorname{\mathcal{F}}\to\operatorname{\mathcal{G}}}$ operation induces a (multiset) bijection $\leftrightsquigarrow$ between $\left\langle\operatorname{\mathcal{F}}\right\rangle$ and $\left\langle\operatorname{\mathcal{G}}\right\rangle$ , where $K\leftrightsquigarrow\widetilde{K}$ if $K$ and $\widetilde{K}$ are the signatures of $\operatorname{\mathbf{K}}$ and $\operatorname{\mathbf{K}}_{\operatorname{\mathcal{F}}\to\operatorname{\mathcal% {G}}}$ . Under this bijection, if $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are (Bi-)Holant-indistinguishable, then so are $\left\langle\operatorname{\mathcal{F}}\right\rangle$ and $\left\langle\operatorname{\mathcal{G}}\right\rangle$ , as a $\left\langle\operatorname{\mathcal{F}}\right\rangle$ -grid expands linearly into a quantum $\operatorname{\mathcal{F}}$ -grid.

Definition 8 ( $T\cdot F$ , $T\operatorname{\mathcal{F}}$ ).

For $T\in\operatorname{GL}_{q}$ and $F\in\mathchoice{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.84726pt\mathopen% {\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{% }\kern 3.48613pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox% [0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}\operatorname{\mathcal{V}}_{r}$ , define $T\cdot F:=T^{\otimes\ell}F(T^{-1})^{\otimes r}$ . Then for $\operatorname{\mathcal{F}}\subset\operatorname{\mathcal{V}}$ , define $T\operatorname{\mathcal{F}}=\{T\cdot F\mid F\in\operatorname{\mathcal{F}}\}$ , a set bijective to $\operatorname{\mathcal{F}}$ via $T\cdot F\leftrightsquigarrow F$ .

Theorem 9 (The Holant Theorem [53]).

If $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}=T(\operatorname% {\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime})$ for $T\in\operatorname{GL}_{q}$ , then $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ are Holant-indistinguishable.

Figure 3: Illustrating the proof of Theorem 9, with

F^{\prime}_{i}=G^{\prime}_{i}(T^{-1})^{\otimes n_{i}}

and

F_{i}=T^{\otimes n_{i}}G_{i}

.

Theorem 9 follows from the fact that left/right contractions are $\operatorname{GL}_{q}$ -equivariant for the action of $\operatorname{GL}_{q}$ in Definition 8. See Figure 3. A similar argument gives the following generalization.

Proposition 10.

For $T\in\operatorname{GL}_{q}$ and $\operatorname{\mathcal{F}}\subset\operatorname{\mathcal{V}}$ , we have $T\left\langle\operatorname{\mathcal{F}}\right\rangle=\left\langle T% \operatorname{\mathcal{F}}\right\rangle$ .

Proof.

Let $\operatorname{\mathbf{K}}$ be an $\operatorname{\mathcal{F}}$ -gadget with signature $K$ and consider $\operatorname{\mathbf{K}}_{\operatorname{\mathcal{F}}\to T\operatorname{% \mathcal{F}}}$ . The $T$ transformations cancel on every internal edge of $\operatorname{\mathbf{K}}_{\operatorname{\mathcal{F}}\to T\operatorname{% \mathcal{F}}}$ , (recall Figure 3 – in other words, covariant/contravariant edge contractions are $\operatorname{GL}_{q}$ -equivariant), and only survive on the dangling edges. Therefore $\operatorname{\mathbf{K}}_{\operatorname{\mathcal{F}}\to T\operatorname{% \mathcal{F}}}$ has signature $T\cdot K$ . The extension to quantum gadgets follows from the linearity of $T$ . $\hfill\blacktriangleleft$ Specializing to $0$ -ary gadgets in $\left\langle\operatorname{\mathcal{F}}\right\rangle$ – that is, (quantum) Bi-Holant $\operatorname{\mathcal{F}}$ -grids – gives an extension of Theorem 9 to Bi-Holant.

Theorem 11 (The Bi-Holant Theorem).

If $\operatorname{\mathcal{F}},\operatorname{\mathcal{G}}\subset\operatorname{% \mathcal{V}}$ satisfy $\operatorname{\mathcal{F}}=T\operatorname{\mathcal{G}}$ for $T\in\operatorname{GL}_{q}$ , then $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are Bi-Holant-indistinguishable.

Xia [55] conjectured the converse of the Holant Theorem: if $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ are Holant-indistinguishable, then there is a holographic transformation between them. Cai, Guo, and Williams [9, Section 4.3] discovered the following Boolean-domain counterexample.

Example 12.

Let $F^{\prime}=[f_{0},f_{1},f_{2},f_{3},f_{4}]=[a,b,1,0,0]$ , where $f_{i}$ is the value of $F^{\prime}$ on inputs of Hamming weight $i$ and $a$ and $b$ are not both 0. Define $G^{\prime}=[0,0,1,0,0]$ and $(\neq_{2})=[0,1,0]$ similarly (so $\neq_{2}$ evaluates to 1 if its two inputs are unequal and 0 otherwise). Define $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}=(\neq_{2})|F^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}=(\neq_{2})|G^{\prime}$ . In an $(\neq_{2})|F^{\prime}$ -grid $\Omega$ , the $\neq_{2}$ signatures in the left bipartition force any nonzero edge assignment $\sigma$ to assign 0 to exactly half of the edges and 1 to the other half. Also, $\sigma$ must provide every $[a,b,1,0,0]$ in the right bipartition no more 1 than 0 inputs. If $\sigma$ provides any $[a,b,1,0,0]$ strictly fewer 1 than 0 inputs (to obtain $a$ or $b$ ), it must provide a different $[a,b,1,0,0]$ strictly more 1 than 0 inputs to preserve the 0/1 balance, and becomes zero. Hence $(\neq_{2})|F^{\prime}$ is indistinguishable from $(\neq_{2})|G^{\prime}$ . However, there is no $T\in\operatorname{GL}_{2}$ transforming $(\neq_{2})|F^{\prime}$ to $(\neq_{2})|G^{\prime}$ .

While there is no invertible matrix transforming $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ to $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ in Example 12, observe that

{\begin{bmatrix}\epsilon^{-1}&0\\ 0&\epsilon\end{bmatrix}}^{\otimes 2}(\neq_{2})=(\neq_{2})\quad\text{and}\quad[% a,b,1,0,0]{\begin{bmatrix}\epsilon&0\\ 0&\epsilon^{-1}\end{bmatrix}}^{\otimes 4}=[a\epsilon^{4},b\epsilon^{2},1,0,0]% \xrightarrow[\epsilon\to 0]{}[0,0,1,0,0],

so $\left[\begin{smallmatrix}\epsilon^{-1}&0\\ 0&\epsilon\end{smallmatrix}\right]\in\operatorname{GL}_{2}$ take $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ arbitrarily close to $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ as $\epsilon\to 0$ . Theorem 19 below extends this to any Bi-Holant-indistinguishable $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ : the converse of Theorem 11 holds up to orbit closure.

3 The Approximate Converse

In this section, let $\operatorname{\mathbb{K}}=\operatorname{\mathbb{C}}$ and assume all signature sets are finite. We prove our first main theorem, Theorem 19. For $H\subset\operatorname{GL}_{q}$ , define $\operatorname{\mathcal{V}}^{H}=\{F\in\operatorname{\mathcal{V}}\mid T\cdot F=F% \text{ for every }T\in H\}$ to be the set of tensors invariant under $H$ . The following restatement of the Tensor First Fundamental Theorem for $\operatorname{GL}_{q}$ , originally due to Weyl [54] (see also [28, Theorem 5.3.1]), says that the only tensors invariant under all of $\operatorname{GL}_{q}$ are the signatures of “braid” quantum gadgets composed only of wires.

Theorem 13 (Tensor First Fundamental Theorem for $\operatorname{GL}_{q}$ ).

$\operatorname{\mathcal{V}}^{\operatorname{GL}_{q}}=\left\langle\varnothing\right\rangle$ .

Definition 14 ( $\operatorname{GL}_{q}\operatorname{\mathcal{F}}$ , $\overline{\operatorname{GL}_{q}\operatorname{\mathcal{F}}}$ ).

The $\operatorname{GL}_{q}$ -orbit $\operatorname{GL}_{q}\operatorname{\mathcal{F}}$ of $\operatorname{\mathcal{F}}\subset\operatorname{\mathcal{V}}$ is $\{T\operatorname{\mathcal{F}}\mid T\in\operatorname{GL}_{q}\}$ . If $\operatorname{\mathcal{F}}=\{F_{1},\ldots,F_{m}\}$ with $F_{i}\in\mathchoice{\mathop{}\kern 7.0151pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{i}}}}{\mathop{}\kern 7.0151pt% \mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{i% }}}}{\mathop{}\kern 6.65398pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_% {\mathmakebox[0pt][r]{\ell_{i}}}}{\mathop{}\kern 6.65398pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{i}}}}\operatorname{% \mathcal{V}}_{r_{i}}$ , then view $\operatorname{\mathcal{F}}$ as an element of the finite-dimensional $\operatorname{\mathbb{C}}$ -vector space $V:=\bigoplus_{i=1}^{m}\mathchoice{\mathop{}\kern 7.0151pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{i}}}}{\mathop{}\kern 7% .0151pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{% \ell_{i}}}}{\mathop{}\kern 6.65398pt\mathopen{\vphantom{\operatorname{\mathcal% {V}}}}_{\mathmakebox[0pt][r]{\ell_{i}}}}{\mathop{}\kern 6.65398pt\mathopen{% \vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{i}}}}% \operatorname{\mathcal{V}}_{r_{i}}$ . Then $\operatorname{GL}_{q}\operatorname{\mathcal{F}}\subset V$ , so define the $\operatorname{GL}_{q}$ -orbit closure $\overline{\operatorname{GL}_{q}\operatorname{\mathcal{F}}}$ of $\operatorname{\mathcal{F}}$ as the closure of $\operatorname{GL}_{q}\operatorname{\mathcal{F}}$ in the standard Euclidean topology. Equivalently $\operatorname{\mathcal{G}}\in V$ is in $\overline{\operatorname{GL}_{q}\operatorname{\mathcal{F}}}$ if, for every $\epsilon>0$ , there is a $T_{\epsilon}\in\operatorname{GL}_{q}$ such that $\|T_{\epsilon}\operatorname{\mathcal{F}}-\operatorname{\mathcal{G}}\|<\epsilon$ (using the standard Euclidean norm on $V$ ).

Definition 15 ( $\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]$ ).

Let $\operatorname{\mathcal{X}}$ be a finite set of domain- $q$ variable-valued signatures. For every $X\in\operatorname{\mathcal{X}}$ of left arity $\ell$ and right arity $r$ (corresponding to a complex-valued signature in $\mathchoice{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\operatorname{\mathcal% {V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.84726pt\mathopen{% \vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}% \kern 3.48613pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[% 0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell}}}\operatorname{\mathcal{V}}_{r}$ ) and $\operatorname{\mathbf{a}}\in[q]^{\ell},\operatorname{\mathbf{b}}\in[q]^{r}$ we introduce a variable $x_{\operatorname{\mathbf{a}},\operatorname{\mathbf{b}}}$ . Define $\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]$ to be the ring of polynomials $\operatorname{\mathbb{C}}[\{x_{\operatorname{\mathbf{a}},\operatorname{\mathbf% {b}}}:X\in\operatorname{\mathcal{X}},\operatorname{\mathbf{a}}\in[q]^{\ell(X)}% ,\operatorname{\mathbf{b}}\in[q]^{r(X)}\}]$ .

Equivalently, $\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]\cong\operatorname{% \mathbb{C}}[V]$ is the coordinate ring of the vector space $V$ from Definition 14 (where $\operatorname{\mathcal{X}}$ is bijective with $\operatorname{\mathcal{F}}$ ). For variable-valued $\operatorname{\mathcal{X}}$ and $\operatorname{\mathcal{X}}$ -grid $\Omega$ , $\operatorname{Bi-Holant}_{\operatorname{\mathcal{X}}}(\Omega)$ is a polynomial in the entries of $\operatorname{\mathcal{X}}$ . Evaluating this polynomial at $\operatorname{\mathcal{F}}$ for $\operatorname{\mathbb{C}}$ -valued $\operatorname{\mathcal{F}}$ bijective with $\operatorname{\mathcal{X}}$ (by substituting $F(\operatorname{\mathbf{a}},\operatorname{\mathbf{b}})$ for $x_{\operatorname{\mathbf{a}},\operatorname{\mathbf{b}}}$ with $\operatorname{\mathcal{F}}\ni F\leftrightsquigarrow X\in\operatorname{\mathcal% {X}}$ ) yields $\operatorname{Bi-Holant}_{\operatorname{\mathcal{F}}}(\Omega)\in\operatorname{% \mathbb{C}}$ . Figure 4 shows an example on the Boolean domain with $\operatorname{\mathcal{X}}=\{X,Y\}$ for binary covariant $X$ and unary contravariant $Y$ .

Figure 4:

\operatorname{Holant}(\Omega)=x_{(\cdot,00)}y_{(0,\cdot)}^{2}+x_{(\cdot,01)}y_% {(0,\cdot)}y_{(1,\cdot)}+x_{(\cdot,10)}y_{(1,\cdot)}y_{(0,\cdot)}+x_{(\cdot,11% )}y_{(1,\cdot)}^{2}

, with the four monomials corresponding to the edge assignments

00,01,10,11

, respectively.

Define an action of $\operatorname{GL}_{q}$ on $\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]$ as follows. For $T\in\operatorname{GL}_{q}$ and $p\in\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]$ , construct $Tp\in\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]$ by substituting every variable $x_{\operatorname{\mathbf{a}},\operatorname{\mathbf{b}}}$ with the $(\operatorname{\mathbf{a}},\operatorname{\mathbf{b}})$ -entry of $T^{-1}\cdot X$ . Equivalently,

(Tp)(\operatorname{\mathcal{F}})=p(T^{-1}\operatorname{\mathcal{F}})

(1)

for $\operatorname{\mathcal{F}}\subset\operatorname{\mathcal{V}}(\operatorname{% \mathbb{C}}^{q})$ bijective with $\operatorname{\mathcal{X}}$ . Then define

\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]^{\operatorname{GL}_{q}}:% =\{p\in\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]\mid Tp=p\text{ % for every }T\in\operatorname{GL}_{q}\}

to be the set of polynomials invariant under this action. The following theorem from geometric invariant theory, stated in this form in [22, Theorem 2.3], [20, Corollary 2.3.8], shows that the $\operatorname{GL}_{q}$ -orbit closures of $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ intersect if and only if $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are indistinguishable by all $\operatorname{GL}_{q}$ -invariant polynomials.

Theorem 16 (Mumford, Fogarty, and Kirwan [43]).

Let $\operatorname{\mathcal{F}},\operatorname{\mathcal{G}}\subset\operatorname{% \mathcal{V}}(\operatorname{\mathbb{C}}^{q})$ be bijective with $\operatorname{\mathcal{X}}$ . Then $\overline{\operatorname{GL}_{q}\operatorname{\mathcal{F}}}\cap\overline{% \operatorname{GL}_{q}\operatorname{\mathcal{G}}}\neq\varnothing$ if and only if $p(\operatorname{\mathcal{F}})=p(\operatorname{\mathcal{G}})$ for every $p\in\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]^{\operatorname{GL}_{% q}}$ .

Accompanying Theorem 16 is a result of Hilbert (see [19]), which implies that it suffices to check finitely many (with the exact number depending on the arity profile of $\operatorname{\mathcal{X}}$ ) polynomial invariants to ensure orbit closure intersection.

Theorem 17 (Hilbert [33]).

The $\operatorname{\mathbb{C}}$ -algebra $\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]^{\operatorname{GL}_{q}}$ is finitely generated.

To convert the condition in Theorem 16 from polynomial indistinguishability to Bi-Holant indistinguishability, we apply the following minor generalization of Weyl’s Polynomial First Fundamental Theorem for $\operatorname{GL}_{q}$ [54, 28] more suited to our purpose. The proof applies an argument similar to [41, Theorem 4.23 and Lemma 4.26] (see also [1, Proposition 4.13]).

Theorem 18.

For variable-valued signature set $\operatorname{\mathcal{X}}=\{X_{1},\ldots,X_{m}\}$ on domain $[q]$ ,

\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]^{\operatorname{GL}_{q}}=% \operatorname{span}\{\operatorname{Bi-Holant}_{\operatorname{\mathcal{X}}}(% \Omega):\mathcal{X}\text{-grid }\Omega\}

Proof.

The $\supset$ inclusion follows from (1), Theorem 11, and the fact that two polynomials which take the same value on every point must be identical.

For the $\subset$ inclusion, let $p\in\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]^{\operatorname{GL}_{% q}}$ . Split $p$ into a sum $p=\sum_{d_{1},\ldots,d_{m}\geq 0}p_{\operatorname{\mathbf{d}}}$ of multihomogeneous polynomials, where $d_{i}$ is the total degree of the entries of $X_{i}$ in $p_{\operatorname{\mathbf{d}}}$ (and only finitely many $p_{\operatorname{\mathbf{d}}}$ are nonzero). Since the action of $\operatorname{GL}_{q}$ replaces each variable $(x_{i})_{\operatorname{\mathbf{a}},\operatorname{\mathbf{b}}}$ with a linear polynomial in the entries of the same signature $X_{i}$ , it preserves the multihomogeneous degree of each $p_{\operatorname{\mathbf{d}}}$ . Therefore each $p_{\operatorname{\mathbf{d}}}\in\operatorname{\mathbb{C}}[\operatorname{% \mathcal{X}}]^{\operatorname{GL}_{q}}$ , and it suffices to find an $\Omega$ such that $\operatorname{Bi-Holant}_{\operatorname{\mathcal{X}}}(\Omega)=p_{\operatorname% {\mathbf{d}}}$ . Let $X_{i}$ have left arity $\ell_{i}$ and right arity $r_{i}$ . Each $p_{\operatorname{\mathbf{d}}}$ corresponds to a tensor $A_{\operatorname{\mathbf{d}}}\in W^{*}$ , where, up to reordering of factors,

W:=\bigotimes_{i=1}^{m}\operatorname{Sym}^{d_{i}}\big(\mathchoice{\mathop{}% \kern 7.0151pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0% pt][r]{\ell_{i}}}}{\mathop{}\kern 7.0151pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{i}}}}{\mathop{}\kern 6.65398pt% \mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{\ell_{i% }}}}{\mathop{}\kern 6.65398pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_% {\mathmakebox[0pt][r]{\ell_{i}}}}\operatorname{\mathcal{V}}_{r_{i}}\big)% \subset(\operatorname{\mathbb{C}}^{q})^{\otimes\sum_{i}\ell_{i}d_{i}}\otimes((% \operatorname{\mathbb{C}}^{q})^{*})^{\otimes\sum_{i}r_{i}d_{i}}

(2)

(here $\operatorname{Sym}^{n}(V)$ denotes the space of symmetric tensors in $V^{\otimes n}$ ) such that, for every complex-valued $\operatorname{\mathcal{F}}=\{F_{1},\ldots,F_{m}\}$ bijective with $\operatorname{\mathcal{X}}$ and $\bigotimes_{i=1}^{m}F_{i}^{\otimes d_{i}}\in W$ , we have

p_{\operatorname{\mathbf{d}}}(\operatorname{\mathcal{F}})=\left\langle A_{% \operatorname{\mathbf{d}}},\nobreak\ \bigotimes_{i=1}^{m}F_{i}^{\otimes d_{i}}% \right\rangle.

(3)

For example, if $q=5$ , $\operatorname{\mathcal{X}}=\{X,Y,Z\}$ , $(\ell_{1},\ell_{2},\ell_{3})=(0,3,1)$ , $(r_{1},r_{2},r_{3})=(2,0,1)$ , and $p_{1,2,1}=x_{(\cdot,45)}y_{(124,\cdot)}y_{(555,\cdot)}z_{(3,4)}=x_{(\cdot,45)}% y_{(555,\cdot)}y_{(124,\cdot)}z_{(3,4)}$ , then

	$\displaystyle A_{1,2,1}=\frac{1}{2}$	$\displaystyle\big((e_{4}\otimes e_{5})\otimes(e_{1}^{}\otimes e_{2}^{}% \otimes e_{4}^{})\otimes(e_{5}^{}\otimes e_{5}^{}\otimes e_{5}^{})\otimes(% e_{3}^{*}\otimes e_{4})$
		$\displaystyle+(e_{4}\otimes e_{5})\otimes(e_{5}^{}\otimes e_{5}^{}\otimes e_% {5}^{})\otimes(e_{1}^{}\otimes e_{2}^{}\otimes e_{4}^{})\otimes(e_{3}^{*}% \otimes e_{4})\big).$

Now with $\bigotimes_{i=1}^{m}(X_{i})^{\otimes d_{i}}$ having left arity $\sum_{i}\ell_{i}d_{i}$ and right arity $\sum_{i}r_{i}d_{i}$ , (3) is equivalent to

p_{\operatorname{\mathbf{d}}}=\Big\langle A_{\operatorname{\mathbf{d}}},% \nobreak\ \bigotimes_{i=1}^{m}X_{i}^{\otimes d_{i}}\Big\rangle.

(4)

Furthermore, for any $T\in\operatorname{GL}_{q}$ ,

Tp_{\operatorname{\mathbf{d}}}=p_{\operatorname{\mathbf{d}}}(T^{-1}% \operatorname{\mathcal{X}})=\Big\langle A_{\operatorname{\mathbf{d}}},\nobreak% \ \bigotimes_{i=1}^{m}(T^{-1}\cdot X_{i})^{\otimes d_{i}}\Big\rangle=\Big% \langle T\cdot A_{\operatorname{\mathbf{d}}},\nobreak\ \bigotimes_{i=1}^{m}(X_% {i})^{\otimes d_{i}}\Big\rangle

so the map $p_{\operatorname{\mathbf{d}}}\mapsto A_{\operatorname{\mathbf{d}}}$ is $\operatorname{GL}_{q}$ -equivariant. With $p_{\operatorname{\mathbf{d}}}\in\operatorname{\mathbb{C}}[\operatorname{% \mathcal{X}}]^{\operatorname{GL}_{q}}$ , it follows that $A_{\operatorname{\mathbf{d}}}\in\operatorname{\mathcal{V}}(\operatorname{% \mathbb{C}}^{q})^{\operatorname{GL}_{q}}$ (up to the reordering of factors in (2), which doesn’t affect this invariance), so, by Theorem 13, $A_{\operatorname{\mathbf{d}}}\in\left\langle\varnothing\right\rangle$ is the signature of a wire gadget. Now (4) says that $p_{\operatorname{\mathbf{d}}}$ is a full contraction consisting only of wires and signatures in $\operatorname{\mathcal{X}}$ , which is $\operatorname{Bi-Holant}_{\operatorname{\mathcal{X}}}(\Omega)$ for some $\operatorname{\mathcal{X}}$ -grid $\Omega$ . $\hfill\blacktriangleleft$

Theorem 19 (first main theorem).

Finite $\operatorname{\mathcal{F}},\operatorname{\mathcal{G}}\subset\operatorname{% \mathcal{V}}(\operatorname{\mathbb{C}}^{q})$ are Bi-Holant-indistinguishable if and only if $\overline{\operatorname{GL}_{q}\operatorname{\mathcal{F}}}\cap\overline{% \operatorname{GL}_{q}\operatorname{\mathcal{G}}}\neq\varnothing$ .

Proof.

The $(\Rightarrow)$ direction follows from Theorem 16 and Theorem 18. $(\Leftarrow)$ follows from Theorem 11 (the $\operatorname{GL}_{q}$ -equivariance of Bi-Holant) and the fact that $\operatorname{Bi-Holant}_{\operatorname{\mathcal{F}}}(\Omega)$ is a polynomial, hence continuous, function in $\operatorname{\mathcal{F}}$ . $\hfill\blacktriangleleft$

Combining Theorem 19, Theorem 16, and Theorem 17 gives the following.

Corollary 20.

The problem of determining whether two finite $\operatorname{\mathcal{F}},\operatorname{\mathcal{G}}\subset\operatorname{% \mathcal{V}}(\operatorname{\mathbb{C}}^{q})$ are Bi-Holant-indistinguishable is decidable.

Say $\operatorname{\mathcal{F}}\subset\operatorname{\mathcal{V}}(\operatorname{% \mathbb{C}}^{q})$ is Bi-Holant-vanishing if it is Bi-Holant-indistinguishable from the set of all-0 signatures. By Proposition 3, this notion captures both bipartite and general Holant vanishing.

Corollary 21.

Finite $\operatorname{\mathcal{F}}\subset\operatorname{\mathcal{V}}(\operatorname{% \mathbb{C}}^{q})$ is Bi-Holant-vanishing if and only if $0\in\overline{\operatorname{GL}_{q}\operatorname{\mathcal{F}}}$ .

4 The Conditional Converse

Definition 22 (Quantum-nonvanishing, $\operatorname{\mathcal{F}}$ -nonvanishing).

Signature set $\operatorname{\mathcal{F}}\subset\operatorname{\mathcal{V}}$ is quantum-nonvanishing if every nonzero $K\in\left\langle\operatorname{\mathcal{F}}\right\rangle$ is $\operatorname{\mathcal{F}}$ -nonvanishing, meaning there is an $\operatorname{\mathcal{F}}\cup\{K\}$ -grid $\Omega$ containing $K$ with nonzero value.

Our second main result is that the converse of the Holant theorem holds if $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ are quantum-nonvanishing.

Theorem 23 (second main theorem).

Let $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ be quantum-nonvanishing. Then $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ are Holant-indistinguishable if and only if there is a $T\in\operatorname{GL}_{q}$ such that $T(\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime})=% \operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ .

Using similar techniques, we show the same result for sets of mixed binary signatures.

Theorem 24.

Let $\operatorname{\mathcal{F}},\operatorname{\mathcal{G}}\subset\operatorname{% \mathbb{K}}^{q\times q}$ be quantum-nonvanishing (when viewed as subsets of $\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\operatorname{\mathcal% {V}}}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 4.48613pt\mathopen{\vphantom{% \operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283% pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{1}}}{% \mathop{}\kern 3.90283pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{% \mathmakebox[0pt][r]{1}}}\operatorname{\mathcal{V}}_{1}$ ). Then the trace of every product of matrices in $\operatorname{\mathcal{F}}$ equals the trace of the corresponding product in $\operatorname{\mathcal{G}}$ if and only if $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are simultaneously similar.

Theorem 23 implies that any $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ serving as a counterexample to the converse of the Holant theorem cannot both be quantum-nonvanishing. In Example 12, $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ is quantum-vanishing. To see this, consider the quantum $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ -gadget $4\operatorname{\mathbf{K}}_{1}-\operatorname{\mathbf{K}}_{2}$ shown in Figure 5.

Figure 5: A quantum gadget

4\operatorname{\mathbf{K}}_{1}-\operatorname{\mathbf{K}}_{2}

with signature

K=[4a-p_{1}(a,b),4b-p_{2}(b),0,0,0]

.

Reasoning as in Example 12, $\operatorname{\mathbf{K}}_{2}$ has signature $[p_{1}(a,b),p_{2}(b),4,0,0]$ for polynomials $p_{1}$ in $a$ and $b$ and $p_{2}$ in $b$ . Therefore the signature of $4\operatorname{\mathbf{K}}_{1}-\operatorname{\mathbf{K}}_{2}$ is $K:=[4a-p_{1}(a,b),4b-p_{2}(b),0,0,0]\in\mathchoice{\mathop{}\kern 4.48613pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4% .48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|% \operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{% \mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% 0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle\operatorname{% \mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[% 0pt][r]{0}}}\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^% {\prime}\right\rangle_{4}$ . But, in any $(\neq_{2})\mid F^{\prime},K$ -grid $\Omega$ containing $K$ , every nonzero assignment is forced to assign $K$ strictly fewer 1s than 0s, so must assign strictly more 1s than 0s to another $[a,b,1,0,0]$ or $K$ , which then evaluates to 0. Therefore $K$ is $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ -vanishing (if $a, b$ happen to be such that $K=0$ , Theorem 23 asserts that some nonzero quantum gadget must be $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ -vanishing).

The proof of Theorems 23 and 24 can be found in the full version [16]. We present an overview of the proof of Theorem 23 here. The key result underlying Theorem 23 is the following theorem of Derksen and Makam [23], which implies that, if $\operatorname{\mathcal{F}}$ is quantum-nonvanishing, then there is a subgroup $\operatorname{Stab}(\operatorname{\mathcal{F}})\subset\operatorname{GL}_{q}$ such that every tensor in $\operatorname{\mathcal{V}}$ invariant under the action of $\operatorname{Stab}(\operatorname{\mathcal{F}})$ is realizable as a quantum- $\operatorname{\mathcal{F}}$ -gadget signature.

Theorem 25 ([23, Theorem 6.2, Proposition 6.5]).

Signature set $\operatorname{\mathcal{F}}$ is quantum-nonvanishing if and only if $\left\langle\operatorname{\mathcal{F}}\right\rangle=\operatorname{\mathcal{V}}% ^{\operatorname{Stab}(\operatorname{\mathcal{F}})}$ for some reductive subgroup $\operatorname{Stab}(\operatorname{\mathcal{F}})\subset\operatorname{GL}_{q}$ .

Definition 26 ( $\oplus$ ).

Let $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ be bijective sets on domains $V(\operatorname{\mathcal{F}})$ and $V(\operatorname{\mathcal{G}})$ , respectively. Define a set $\operatorname{\mathcal{F}}\oplus\operatorname{\mathcal{G}}=\{F\oplus G\mid% \operatorname{\mathcal{F}}\ni F\leftrightsquigarrow G\in\operatorname{\mathcal% {G}}\}$ on domain $V(\operatorname{\mathcal{F}})\sqcup V(\operatorname{\mathcal{G}})$ and bijective with $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ , where

(F\oplus G)(\operatorname{\mathbf{a}})=\begin{cases}F(\operatorname{\mathbf{a}% })&\operatorname{\mathbf{a}}\in V(\operatorname{\mathcal{F}})^{n}\\ G(\operatorname{\mathbf{a}})&\operatorname{\mathbf{a}}\in V(\operatorname{% \mathcal{G}})^{n}\\ 0&\text{otherwise}\end{cases}

for $n$ -ary $F$ and $G$ and $\operatorname{\mathbf{a}}\in(V(\operatorname{\mathcal{F}})\sqcup V(% \operatorname{\mathcal{G}}))^{n}$ .

The point of $\oplus$ is that providing any input from $V(\operatorname{\mathcal{F}})$ to a connected component of a $\left\langle\operatorname{\mathcal{F}}\right\rangle\oplus\left\langle% \operatorname{\mathcal{G}}\right\rangle$ -gadget forces all edges in that component to take values in $V(\operatorname{\mathcal{F}})$ (all other edge assignments give 0). For $K\in\left\langle\left\langle\operatorname{\mathcal{F}}\right\rangle\oplus\left% \langle\operatorname{\mathcal{G}}\right\rangle\right\rangle$ , use $K|_{\operatorname{\mathcal{F}}}$ as shorthand for $K|_{V(\operatorname{\mathcal{F}})}$ (the subsignature of $K$ induced by $V(\operatorname{\mathcal{F}})$ ).

Proposition 27.

If $K\in\left\langle\left\langle\operatorname{\mathcal{F}}\right\rangle\oplus\left% \langle\operatorname{\mathcal{G}}\right\rangle\right\rangle$ , then $\left\langle\operatorname{\mathcal{F}}\right\rangle\ni K|_{\operatorname{% \mathcal{F}}}\leftrightsquigarrow K|_{\operatorname{\mathcal{G}}}\in\left% \langle\operatorname{\mathcal{G}}\right\rangle$ .

Proof.

By definition, $K$ is the signature of some quantum $\left\langle\operatorname{\mathcal{F}}\right\rangle\oplus\left\langle% \operatorname{\mathcal{G}}\right\rangle$ -gadget $\operatorname{\mathbf{K}}$ . Any connected component of a term of $\operatorname{\mathbf{K}}$ without a dangling edge contributes only a constant factor; by absorbing this factor into the term’s coefficient, we may assume no term of $\operatorname{\mathbf{K}}$ has such a component. To construct $K|_{\operatorname{\mathcal{F}}}$ , restrict all inputs to $\operatorname{\mathbf{K}}$ to $V(\operatorname{\mathcal{F}})$ . As discussed above, this restricts all edges of all gadgets composing $\operatorname{\mathbf{K}}$ to $V(\operatorname{\mathcal{F}})$ . Thus $K|_{\operatorname{\mathcal{F}}}$ is the signature of $\operatorname{\mathbf{K}}_{\left\langle\operatorname{\mathcal{F}}\right\rangle% \oplus\left\langle\operatorname{\mathcal{G}}\right\rangle\to\left\langle% \operatorname{\mathcal{F}}\right\rangle}$ . Similarly, $\operatorname{\mathbf{K}}_{\left\langle\operatorname{\mathcal{F}}\right\rangle% \oplus\left\langle\operatorname{\mathcal{G}}\right\rangle\to\left\langle% \operatorname{\mathcal{G}}\right\rangle}$ has signature $K|_{\operatorname{\mathcal{G}}}$ , and the result follows. $\hfill\blacktriangleleft$ More involved reasoning along the same lines also gives the following.

Lemma 28 ([16, Lemma 5.2]).

Suppose $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are Bi-Holant-indistinguishable. Then $\left\langle\operatorname{\mathcal{F}}\right\rangle\oplus\left\langle% \operatorname{\mathcal{G}}\right\rangle$ is quantum-nonvanishing if and only if $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are both quantum-nonvanishing.

Now we obtain the following analogue of [57, Lemma 3.2], with a similar proof.

Lemma 29.

If $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are Bi-Holant-indistinguishable and quantum-nonvanishing, then there exists an $H\in\operatorname{Stab}(\left\langle\operatorname{\mathcal{F}}\right\rangle% \oplus\left\langle\operatorname{\mathcal{G}}\right\rangle)$ with $H|_{\operatorname{\mathcal{F}},\operatorname{\mathcal{G}}}\neq 0$ or $H|_{\operatorname{\mathcal{G}},\operatorname{\mathcal{F}}}\neq 0$ .

Proof.

By Lemma 28, Theorem 25 applies to $\left\langle\operatorname{\mathcal{F}}\right\rangle\oplus\left\langle% \operatorname{\mathcal{G}}\right\rangle$ . Assume every $H\in\operatorname{Stab}(\left\langle\operatorname{\mathcal{F}}\right\rangle% \oplus\left\langle\operatorname{\mathcal{G}}\right\rangle)$ satisfies $H|_{\operatorname{\mathcal{F}},\operatorname{\mathcal{G}}}=H|_{\operatorname{% \mathcal{G}},\operatorname{\mathcal{F}}}=0$ (i.e. is block-diagonal). Then

I_{\operatorname{\mathcal{F}}}\oplus 2I_{\operatorname{\mathcal{G}}}=\begin{% bmatrix}I&0\\ 0&2I\end{bmatrix}\in\operatorname{\mathcal{V}}(\operatorname{\mathbb{K}}^{2q})

satisfies $H(I_{\operatorname{\mathcal{F}}}\oplus 2I_{\operatorname{\mathcal{G}}})H^{-1}=% I_{\operatorname{\mathcal{F}}}\oplus 2I_{\operatorname{\mathcal{G}}}$ for every $H\in\operatorname{Stab}(\left\langle\operatorname{\mathcal{F}}\right\rangle% \oplus\left\langle\operatorname{\mathcal{G}}\right\rangle)$ , so, by Theorem 25, $I_{\operatorname{\mathcal{F}}}\oplus 2I_{\operatorname{\mathcal{G}}}\in% \mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle\left% \langle\operatorname{\mathcal{F}}\right\rangle\oplus\left\langle\operatorname{% \mathcal{G}}\right\rangle\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}% \kern 4.48613pt\mathopen{\vphantom{\left\langle\left\langle\operatorname{% \mathcal{F}}\right\rangle\oplus\left\langle\operatorname{\mathcal{G}}\right% \rangle\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt% \mathopen{\vphantom{\left\langle\left\langle\operatorname{\mathcal{F}}\right% \rangle\oplus\left\langle\operatorname{\mathcal{G}}\right\rangle\right\rangle}% }_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left% \langle\left\langle\operatorname{\mathcal{F}}\right\rangle\oplus\left\langle% \operatorname{\mathcal{G}}\right\rangle\right\rangle}}_{\mathmakebox[0pt][r]{1% }}}\left\langle\left\langle\operatorname{\mathcal{F}}\right\rangle\oplus\left% \langle\operatorname{\mathcal{G}}\right\rangle\right\rangle_{1}$ . But Proposition 27 gives

\left\langle\operatorname{\mathcal{F}}\right\rangle\ni I_{\operatorname{% \mathcal{F}}}=(I_{\operatorname{\mathcal{F}}}\oplus 2I_{\operatorname{\mathcal% {G}}})|_{\operatorname{\mathcal{F}}}\leftrightsquigarrow(I_{\operatorname{% \mathcal{F}}}\oplus 2I_{\operatorname{\mathcal{G}}})|_{\operatorname{\mathcal{% G}}}=2I_{\operatorname{\mathcal{G}}}\in\left\langle\operatorname{\mathcal{G}}% \right\rangle,

violating indistinguishability, as $\operatorname{tr}(I_{\operatorname{\mathcal{F}}})=q\neq 2q=\operatorname{tr}(2% I_{\operatorname{\mathcal{G}}})$ . $\hfill\blacktriangleleft$

For $Z\subset[q]$ , define the subdomain restrictor $I_{Z}^{\shortuparrow}\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{% \vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}% \kern 4.48613pt\mathopen{\vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[% 0pt][r]{1}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\operatorname{% \mathcal{V}}}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\operatorname{\mathcal{V}}}}_{\mathmakebox[0pt][r]{1}}}\operatorname% {\mathcal{V}}_{1}$ , which acts as the identity on inputs from $Z$ and zeroes out $[q]\setminus Z$ . That is, $I_{Z}^{\shortuparrow}$ has $(Z,[q]\setminus Z)$ -block matrix form $I_{Z}^{\shortuparrow}=\left[\begin{smallmatrix}I_{Z}&0\\ 0&0\end{smallmatrix}\right]$ .

Lemma 30.

If $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ are Bi-Holant-indistinguishable and quantum-nonvanishing, then there exist $\varnothing\neq Z\subset[q]$ and $T_{1},T_{2}\in\operatorname{GL}_{q}$ such that, up to swapping the roles of $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ , after transforming $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ by $T_{1}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ by $T_{2}$ , every $\mathchoice{\mathop{}\kern 5.44333pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 5.44333pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right% \rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4.90399pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4.90399pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle_{0% }\ni F\leftrightsquigarrow G\in\mathchoice{\mathop{}\kern 5.44333pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 5.44333pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{% \mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4% .90399pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{% \mathop{}\kern 4.90399pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% n}}}\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}% \right\rangle_{0}$ and $\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right% \rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle_{n% }\ni F^{\prime}\leftrightsquigarrow G^{\prime}\in\mathchoice{\mathop{}\kern 4.% 48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{% \mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% 0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle\operatorname{% \mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[% 0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{0}}}\left\langle\operatorname{\mathcal{G}}|\operatorname% {\mathcal{G}}^{\prime}\right\rangle_{n}$ for every $n\geq 1$ satisfy

(I_{Z}^{\shortuparrow})^{\otimes n}F=G\text{ and }F^{\prime}=G^{\prime}(I_{Z}^% {\shortuparrow})^{\otimes n}.

(5)

Proof.

Lemma 29 gives an $H\in\operatorname{Stab}(\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle\oplus\left\langle\operatorname{\mathcal{G}}% |\operatorname{\mathcal{G}}^{\prime}\right\rangle)$ with, WLOG, $H|_{\operatorname{\mathcal{G}},\operatorname{\mathcal{F}}}\neq 0$ . Choose $T_{1},T_{2}\in\operatorname{GL}_{q}$ so that $T_{2}H_{\operatorname{\mathcal{G}},\operatorname{\mathcal{F}}}T_{1}^{-1}=I_{Z}% ^{\shortuparrow}\in\operatorname{\mathbb{K}}^{q\times q}$ for some $Z\subset[q]$ with $|Z|=\text{rank}(H_{\operatorname{\mathcal{G}},\operatorname{\mathcal{F}}})>0$ . By Theorem 25, $H$ satisfies $H\cdot K=K$ for every $K\in\left\langle\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{% F}}^{\prime}\right\rangle\oplus\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle\right\rangle$ . Transform $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ by $T_{1}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ by $T_{2}$ . By Proposition 10, this replaces $\left\langle\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^% {\prime}\right\rangle\oplus\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle\right\rangle$ with

\left\langle(T_{1}\oplus T_{2})\big(\left\langle\operatorname{\mathcal{F}}|% \operatorname{\mathcal{F}}^{\prime}\right\rangle\oplus\left\langle% \operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle% \big)\right\rangle=(T_{1}\oplus T_{2})\left\langle\left\langle\operatorname{% \mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle\oplus\left% \langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right% \rangle\right\rangle.

Now, after the transformation by $(T_{1}\oplus T_{2})$ ,

\widetilde{H}:=(T_{1}\oplus T_{2})H(T_{1}\oplus T_{2})^{-1}=\begin{bmatrix}T_{% 1}&0\\ 0&T_{2}\end{bmatrix}\begin{bmatrix}*&*\\ H_{\operatorname{\mathcal{G}},\operatorname{\mathcal{F}}}&*\end{bmatrix}\begin% {bmatrix}T_{1}^{-1}&0\\ 0&T_{2}^{-1}\end{bmatrix}=\begin{bmatrix}*&*\\ I_{Z}^{\shortuparrow}&*\end{bmatrix}

satisfies $\widetilde{H}\cdot K=K$ for every $K\in\left\langle\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{% F}}^{\prime}\right\rangle\oplus\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle\right\rangle$ .

Let $\mathchoice{\mathop{}\kern 5.44333pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 5.44333pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right% \rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4.90399pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4.90399pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle_{0% }\ni F\leftrightsquigarrow G\in\mathchoice{\mathop{}\kern 5.44333pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 5.44333pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{% \mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4% .90399pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{% \mathop{}\kern 4.90399pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% n}}}\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}% \right\rangle_{0}$ . Then $(F\otimes I)\oplus(G\otimes I)\in\mathchoice{\mathop{}\kern 15.56837pt% \mathopen{\vphantom{\left\langle\left\langle\operatorname{\mathcal{F}}|% \operatorname{\mathcal{F}}^{\prime}\right\rangle\oplus\left\langle% \operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle% \right\rangle}}_{\mathmakebox[0pt][r]{n+1}}}{\mathop{}\kern 15.56837pt% \mathopen{\vphantom{\left\langle\left\langle\operatorname{\mathcal{F}}|% \operatorname{\mathcal{F}}^{\prime}\right\rangle\oplus\left\langle% \operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle% \right\rangle}}_{\mathmakebox[0pt][r]{n+1}}}{\mathop{}\kern 13.4458pt\mathopen% {\vphantom{\left\langle\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle\oplus\left\langle\operatorname{\mathcal{G}}% |\operatorname{\mathcal{G}}^{\prime}\right\rangle\right\rangle}}_{\mathmakebox% [0pt][r]{n+1}}}{\mathop{}\kern 13.4458pt\mathopen{\vphantom{\left\langle\left% \langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right% \rangle\oplus\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}% ^{\prime}\right\rangle\right\rangle}}_{\mathmakebox[0pt][r]{n+1}}}\left\langle% \left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}% \right\rangle\oplus\left\langle\operatorname{\mathcal{G}}|\operatorname{% \mathcal{G}}^{\prime}\right\rangle\right\rangle_{1}$ , so $\widetilde{H}^{\otimes n+1}((F\otimes I)\oplus(G\otimes I))=\big((F\otimes I)% \oplus(G\otimes I)\big)\widetilde{H}$ , which in $(V(\operatorname{\mathcal{F}}),V(\operatorname{\mathcal{G}}))$ -block matrix form (see e.g. [57, Appendix A]) is

\begin{bmatrix}*&*&\ldots&*\\ \vdots&\vdots&\iddots&\vdots\\ *&*&\ldots&*\\ (I_{Z}^{\shortuparrow})^{\otimes n+1}&*&\ldots&*\end{bmatrix}\begin{bmatrix}F% \otimes I&0\\ 0&0\\ \vdots&\vdots\\ 0&0\\ 0&G\otimes I\end{bmatrix}=\begin{bmatrix}F\otimes I&0\\ 0&0\\ \vdots&\vdots\\ 0&0\\ 0&G\otimes I\end{bmatrix}\begin{bmatrix}*&*\\ I_{Z}^{\shortuparrow}&*\end{bmatrix}.

(6)

The bottom left block of (6) gives the second equality in

\big((I_{Z}^{\shortuparrow})^{\otimes n}F\big)\otimes I_{Z}^{\shortuparrow}=(I% _{Z}^{\shortuparrow})^{\otimes n+1}(F\otimes I)=(G\otimes I)I_{Z}^{% \shortuparrow}=G\otimes I_{Z}^{\shortuparrow}

(7)

(see Figure 6), which implies $(I_{Z}^{\shortuparrow})^{\otimes n}F=G$ . Similarly, if $\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right% \rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle_{n% }\ni F^{\prime}\leftrightsquigarrow G^{\prime}\in\mathchoice{\mathop{}\kern 4.% 48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{% \mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% 0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle\operatorname{% \mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[% 0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{0}}}\left\langle\operatorname{\mathcal{G}}|\operatorname% {\mathcal{G}}^{\prime}\right\rangle_{n}$ , then $F^{\prime}=G^{\prime}(I_{Z}^{\shortuparrow})^{\otimes n}$ . $\hfill\blacktriangleleft$

Figure 6: Illustrating (7) for

n=3

.

If $Z=[q]$ in Lemma 30, then, since $\operatorname{\mathcal{F}}\subset\mathchoice{\mathop{}\kern 5.44333pt\mathopen% {\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 5.44333pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4% .90399pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|% \operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{% \mathop{}\kern 4.90399pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% n}}}\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}% \right\rangle_{0}$ corresponds to $\operatorname{\mathcal{G}}\subset\mathchoice{\mathop{}\kern 5.44333pt\mathopen% {\vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 5.44333pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{% \mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4% .90399pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{% \mathop{}\kern 4.90399pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% n}}}\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}% \right\rangle_{0}$ and $\operatorname{\mathcal{F}}^{\prime}\subset\mathchoice{\mathop{}\kern 4.48613pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4% .48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|% \operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{% \mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% 0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle\operatorname{% \mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[% 0pt][r]{0}}}\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^% {\prime}\right\rangle_{n}$ corresponds to $\operatorname{\mathcal{G}}^{\prime}\subset\mathchoice{\mathop{}\kern 4.48613pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{% \mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4% .48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{% \mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% 0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle\operatorname{% \mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[% 0pt][r]{0}}}\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^% {\prime}\right\rangle_{n}$ , (5) already gives $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}=\operatorname{% \mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ after the transformations by $T_{1}$ and $T_{2}$ , so we are done. Otherwise, (5) asserts that, after these transformations, every $\mathchoice{\mathop{}\kern 5.44333pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 5.44333pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right% \rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4.90399pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4.90399pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle_{0% }\ni F\leftrightsquigarrow G\in\mathchoice{\mathop{}\kern 5.44333pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 5.44333pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{% \mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4% .90399pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{% \mathop{}\kern 4.90399pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% n}}}\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}% \right\rangle_{0}$ and $\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right% \rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle_{n% }\ni F^{\prime}\leftrightsquigarrow G^{\prime}\in\mathchoice{\mathop{}\kern 4.% 48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{% \mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% 0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle\operatorname{% \mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[% 0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{0}}}\left\langle\operatorname{\mathcal{G}}|\operatorname% {\mathcal{G}}^{\prime}\right\rangle_{n}$ have $(Z,[q]\setminus Z)$ -block vector form

\begin{aligned} F=\begin{bmatrix}F|_{Z}\\ *\\ \vdots\\ *\end{bmatrix},G=\begin{bmatrix}F|_{Z}\\ 0\\ \vdots\\ 0\end{bmatrix},\end{aligned}\quad\begin{aligned} &F^{\prime}=\begin{bmatrix}G^% {\prime}|_{Z}&0&\ldots&0\end{bmatrix},\\ &G^{\prime}=\begin{bmatrix}G^{\prime}|_{Z}&*&\ldots&*\end{bmatrix}.\end{aligned}

(8)

Now, if we can show that all of the $*$ blocks in (8) are 0 for every $F$ and $G^{\prime}$ , then we again obtain $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}=\operatorname{% \mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ and are done. Suppose we could realize the subdomain restrictor $I_{Z}^{\shortuparrow}\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 4.48613pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3% .90283pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|% \operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{% \mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% 1}}}\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}% \right\rangle_{1}$ . Then, for any $F\in\mathchoice{\mathop{}\kern 5.44333pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 5.44333pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right% \rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4.90399pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{\mathop{}\kern 4.90399pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle_{0}$ ,

\widehat{F}:=\begin{bmatrix}F|_{Z}\\ *\\ \vdots\\ *\end{bmatrix}-\begin{bmatrix}F|_{Z}\\ 0\\ \vdots\\ 0\end{bmatrix}=\begin{bmatrix}0\\ *\\ \vdots\\ *\end{bmatrix}=F-(I_{Z}^{\shortuparrow})^{\otimes n}F\in\mathchoice{\mathop{}% \kern 5.44333pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|% \operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{n}}}{% \mathop{}\kern 5.44333pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% n}}}{\mathop{}\kern 4.90399pt\mathopen{\vphantom{\left\langle\operatorname{% \mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[% 0pt][r]{n}}}{\mathop{}\kern 4.90399pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{n}}}\left\langle\operatorname{\mathcal{F}}|\operatorname% {\mathcal{F}}^{\prime}\right\rangle_{0}.

(9)

However, any $(\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime})\cup\{\widehat% {F}\}$ -grid containing $\widehat{F}$ has Holant value $\langle\widehat{F},F^{\prime}\rangle$ for some $F^{\prime}\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right% \rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4.48613pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3% .90283pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|% \operatorname{\mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}% \left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}% \right\rangle_{n}$ , and, by the block forms of $\widehat{F}$ in (9) and $F^{\prime}$ in (8), $\langle\widehat{F},F^{\prime}\rangle=0$ . Thus $\widehat{F}$ is $(\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime})$ -vanishing, so quantum-nonvanishing of $(\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime})$ forces $\widehat{F}=0$ , and the $*$ blocks of $F$ are 0, as desired.

Similar reasoning holds for $G^{\prime}$ if $I_{Z}^{\shortuparrow}\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 4.48613pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{% \mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3% .90283pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{% \mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{% 1}}}\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}% \right\rangle_{1}$ , so it suffices to realize $\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right% \rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle_{1% }\ni I_{Z}^{\shortuparrow}\leftrightsquigarrow I_{Z}^{\shortuparrow}\in% \mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right% \rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{% \mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}\left\langle% \operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right\rangle_{1}$ . Let $\operatorname{\mathbf{K}}$ be a nontrivial $(1,1)$ - $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ -gadget with signature $K$ , and let $\widetilde{K}$ be the signature of $\operatorname{\mathbf{K}}_{\operatorname{\mathcal{F}}|\operatorname{\mathcal{F% }}^{\prime}\to\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}}$ . To preserve covariant/contravariant balance, $\operatorname{\mathbf{K}}$ must contain at least one signature in both $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{F}}^{\prime}$ . The right input to $\operatorname{\mathbf{K}}$ is incident to an $F^{\prime}\in\operatorname{\mathcal{F}}^{\prime}$ , which by (8) is only supported on $Z$ . Similarly, the left input to $\operatorname{\mathbf{K}}_{\operatorname{\mathcal{F}}|\operatorname{\mathcal{F% }}^{\prime}\to\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}}$ is incident to a $G\in\operatorname{\mathcal{G}}$ , which is only supported on $Z$ . Therefore $K$ and $\widetilde{K}$ have block form

K=\begin{bmatrix}K|_{Z}&0\\ *&0\end{bmatrix}\text{ and }\widetilde{K}=\begin{bmatrix}\widetilde{K}|_{Z}&*% \\ 0&0\end{bmatrix}.

Now there exist $T_{3}$ and $T_{4}$ such that, upon transforming $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ by $T_{3}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ by $T_{4}$ , the block structure (8) is preserved and $K$ and $\widetilde{K}$ are in Jordan normal form, so there is a polynomial $p$ such that

\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle}}_% {\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right% \rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}|\operatorname{% \mathcal{F}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}\left\langle% \operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}\right\rangle_{1% }\ni p(K)=I_{X}^{\shortuparrow}\leftrightsquigarrow I_{X}^{\shortuparrow}=p(% \widetilde{K})\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}\right% \rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 4.48613pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{% \prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3.90283pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|\operatorname{% \mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}{\mathop{}\kern 3% .90283pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{G}}|% \operatorname{\mathcal{G}}^{\prime}\right\rangle}}_{\mathmakebox[0pt][r]{1}}}% \left\langle\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}% \right\rangle_{1}

for some $X\subset Z$ [16, Lemma 5.1]. If $X=Z$ then we are done. Otherwise, use $I_{[q]\setminus X}^{\shortuparrow}=I-I_{X}^{\shortuparrow}$ to restrict $\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{\prime}$ and $\operatorname{\mathcal{G}}|\operatorname{\mathcal{G}}^{\prime}$ to $[q]\setminus X\supset[q]\setminus Z$ and repeat inductively on this smaller domain. Eventually, we obtain either $I_{Z}^{\shortuparrow}$ or $I_{[q]\setminus Z}^{\shortuparrow}$ , and in the latter case apply $I_{Z}^{\shortuparrow}=I-I_{[q]\setminus Z}^{\shortuparrow}$ . See the full version [16] for details.

5 More Corollaries of the Main Theorems

In this section, we exploit the expressive power of Bi-Holant to derive novel consequences of Theorems 19 and 23. We begin with an extension of the main result of Young [57]. The following proposition – which is equivalent to the fact that contraction with $=_{2}$ defines the standard bilinear form on $\operatorname{\mathbb{K}}^{q}$ – and Proposition 3 show that this result is a special case of the converse of the bipartite Holant theorem.

Proposition 31.

$T\in\operatorname{GL}_{q}$ is orthogonal iff $T\cdot(=_{2})=(=_{2})$ for contravariant or covariant $=_{2}$ .

Theorem 32 ([57, Theorem 2.3]).

Real-valued $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are Holant-indistinguishable if and only if there is a real orthogonal $T$ such that $T\operatorname{\mathcal{F}}=\operatorname{\mathcal{G}}$ .

Theorem 32 does not hold for complex-valued signatures – for example, consider $\operatorname{\mathcal{F}}=\{0\}$ and the vanishing set $\operatorname{\mathcal{G}}$ containing the single unary signature $[1,i]$ . Say that $\operatorname{\mathcal{F}}\subset\operatorname{\mathcal{V}}(\operatorname{% \mathbb{C}}^{q})$ is conjugate-closed if $F\in\operatorname{\mathcal{F}}\iff\overline{F}\in\operatorname{\mathcal{F}}$ , where $\overline{F}$ is the entrywise complex conjugate of $F$ (note that any real-valued set is conjugate-closed). Young [57, Section 6.1] conjectured the following extension of Theorem 32, which we we confirm using Theorem 23.

Corollary 33.

Suppose $\operatorname{\mathcal{F}},\operatorname{\mathcal{G}}\subset\operatorname{% \mathcal{V}}(\operatorname{\mathbb{C}}^{q})$ are conjugate-closed. Then $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are Holant-indistinguishable if and only if there is a complex orthogonal matrix $T$ such that $T\operatorname{\mathcal{F}}=\operatorname{\mathcal{G}}$ .

Proof.

By Proposition 3, $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are Holant-indistinguishable if and only if $=_{2}|\operatorname{\mathcal{F}},=_{2}$ and $=_{2}|\operatorname{\mathcal{G}},=_{2}$ are Holant-indistinguishable. Now the $(\Leftarrow)$ direction follows from Proposition 31 and Theorem 9. We will show that $=_{2}|\operatorname{\mathcal{F}},=_{2}$ is quantum-nonvanishing (the $\operatorname{\mathcal{G}}$ argument is similar); then the $(\Rightarrow)$ direction follows from Proposition 31 and Theorem 23 with $\operatorname{\mathbb{K}}=\operatorname{\mathbb{C}}$ . See 7(a). Let $0\neq K\in\mathchoice{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\left\langle% =_{2}|\operatorname{\mathcal{F}},=_{2}\right\rangle}}_{\mathmakebox[0pt][r]{% \ell}}}{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\left\langle=_{2}|% \operatorname{\mathcal{F}},=_{2}\right\rangle}}_{\mathmakebox[0pt][r]{\ell}}}{% \mathop{}\kern 3.48613pt\mathopen{\vphantom{\left\langle=_{2}|\operatorname{% \mathcal{F}},=_{2}\right\rangle}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3% .48613pt\mathopen{\vphantom{\left\langle=_{2}|\operatorname{\mathcal{F}},=_{2}% \right\rangle}}_{\mathmakebox[0pt][r]{\ell}}}\left\langle=_{2}|\operatorname{% \mathcal{F}},=_{2}\right\rangle_{r}$ . By definition, $K=\sum_{i=1}^{m}c_{i}K_{i}$ , where each $c_{i}\in\operatorname{\mathbb{C}}$ and each $K_{i}$ is the signature of a $(=_{2}|\operatorname{\mathcal{F}},=_{2})$ -gadget $\operatorname{\mathbf{K}}_{i}$ . Since $\operatorname{\mathcal{F}}$ is conjugate closed, each entrywise conjugate $\overline{K_{i}}$ is the signature of the $(=_{2}|\operatorname{\mathcal{F}},=_{2})$ -gadget constructed from $\operatorname{\mathbf{K}}_{i}$ with replacing every $F\in\operatorname{\mathcal{F}}$ in $\operatorname{\mathbf{K}}_{i}$ by $\overline{F}\in\operatorname{\mathcal{F}}$ . Therefore $\overline{K}=\sum_{i=1}^{m}\overline{c_{i}}\overline{K_{i}}\in\left\langle=_{2% }|\operatorname{\mathcal{F}},=_{2}\right\rangle$ . Now construct the dual $K^{*}\in\mathchoice{\mathop{}\kern 4.42825pt\mathopen{\vphantom{\left\langle=_% {2}|\operatorname{\mathcal{F}},=_{2}\right\rangle}}_{\mathmakebox[0pt][r]{r}}}% {\mathop{}\kern 4.42825pt\mathopen{\vphantom{\left\langle=_{2}|\operatorname{% \mathcal{F}},=_{2}\right\rangle}}_{\mathmakebox[0pt][r]{r}}}{\mathop{}\kern 4.% 03014pt\mathopen{\vphantom{\left\langle=_{2}|\operatorname{\mathcal{F}},=_{2}% \right\rangle}}_{\mathmakebox[0pt][r]{r}}}{\mathop{}\kern 4.03014pt\mathopen{% \vphantom{\left\langle=_{2}|\operatorname{\mathcal{F}},=_{2}\right\rangle}}_{% \mathmakebox[0pt][r]{r}}}\left\langle=_{2}|\operatorname{\mathcal{F}},=_{2}% \right\rangle_{\ell}$ by connecting a left-facing $=_{2}$ to each right input of $\overline{K}$ and connecting a right-facing $=_{2}$ to each left input of $\overline{K}$ . Then $\langle K,K^{*}\rangle\neq 0$ , so $K^{*}$ witnesses that $K$ is $(=_{2}|\operatorname{\mathcal{F}},=_{2})$ -nonvanishing. $\hfill\blacktriangleleft$

5.1 Bounded-Degree Graph Homomorphisms and #CSP

Graphs $F$ and $G$ are homomorphism indistinguishable over a graph class $\mathfrak{G}$ if $\hom(X,F)=\hom(X,G)$ for every $X\in\mathfrak{G}$ . It follows from the discussion around Figure 1 that two graphs $F$ and $G$ are homomorphism-indistinguishable over graphs of maximum degree at most $d$ iff $\operatorname{\mathcal{EQ}}_{\leq d}|A_{F}$ and $\operatorname{\mathcal{EQ}}_{\leq d}|A_{G}$ are Holant-indistinguishable. More generally, for any $\operatorname{\mathcal{F}}$ consider $\operatorname{\#CSP}(\operatorname{\mathcal{F}})=\operatorname{Holant}_{% \operatorname{\mathcal{EQ}}\cup\operatorname{\mathcal{F}}}$ and $\operatorname{\#CSP}^{(d)}(\operatorname{\mathcal{F}})=\operatorname{Holant}_{% \operatorname{\mathcal{EQ}}_{\leq d}|\operatorname{\mathcal{F}}}$ . The counting constraint satisfaction problem #CSP is a well-studied problem in counting complexity, itself the subject of broad dichotomy theorems [3, 25, 6, 5]. In $\operatorname{\#CSP}^{(d)}(\operatorname{\mathcal{F}})$ , every variable appears at most $d$ times across all constraints [14]. In general, $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are $\operatorname{\#CSP}$ -indistinguishable (i.e. $\operatorname{\mathcal{EQ}}\cup\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{EQ}}\cup\operatorname{\mathcal{G}}$ are Holant-indistinguishable) if and only if $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are isomorphic [56]. Putting $\operatorname{\mathcal{F}}=\{A_{F}\}$ and $\operatorname{\mathcal{G}}=\{A_{G}\}$ , we recover the classical result of Lovász that homomorphism-indistinguishability is equivalent to isomorphism [39]. This also follows from from Theorem 32 and the fact that $T$ is a permutation matrix if and only if $T\operatorname{\mathcal{EQ}}=\operatorname{\mathcal{EQ}}$ (viewing the equalities as contravariant) [55, 57]. In fact, the following sharper characterization holds.

Proposition 34.

$T\in\operatorname{GL}_{q}$ is a permutation matrix if and only if $T\{=_{2},=_{3}\}=\{=_{2},=_{3}\}$ .

Proof.

Assume $T\{=_{2},=_{3}\}=\{=_{2},=_{3}\}$ . By Proposition 31, $T$ is orthogonal and preserves the covariant $=_{2}$ . Therefore, by Proposition 10, $T$ preserves the signature of every $(=_{3}|=_{2})$ -gadget. Every $=_{n}$ for $n\geq 4$ is the signature of the $(=_{3}|=_{2})$ -gadget constructed by chaining together $n-2$ copies of $=_{3}$ using the covariant $=_{2}$ (and $=_{1}$ is realized by connecting two inputs of a single $=_{3}$ with $=_{2}$ ). Therefore $T\operatorname{\mathcal{EQ}}=\operatorname{\mathcal{EQ}}$ , so $T$ is a permutation matrix. $\hfill\blacktriangleleft$

(a) The construction in Corollary 33.

(b) The construction in Lemma 36.

Figure 7: Connecting quantum gadgets with their conjugates for quantum-nonvanishing.

However, recall that $\operatorname{Holant}_{\operatorname{\mathcal{EQ}}_{\leq d}\mid A_{G}}$ , and, more generally, $\operatorname{Holant}_{\operatorname{\mathcal{EQ}}_{\leq d}\mid\operatorname{% \mathcal{F}}}$ are strictly bipartite problems, so Theorem 32 does not apply. Instead, we apply Theorem 23 to obtain the following.

Corollary 35.

For $d\geq 3$ , if $\operatorname{\mathcal{EQ}}_{\leq d}|\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{EQ}}_{\leq d}|\operatorname{\mathcal{G}}$ are quantum-nonvanishing, then $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are $\operatorname{\#CSP}^{(d)}$ -indistinguishable if and only if $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are isomorphic.

Corollary 35 raises the interesting problem of characterizing for which graphs $G$ the set $\operatorname{\mathcal{EQ}}_{\leq d}|A_{G}$ is quantum-nonvanishing. The next lemma implies that graphs with invertible adjacency matrices have this property.

Lemma 36.

If $\operatorname{\mathcal{F}}\subset\operatorname{\mathcal{V}}(\operatorname{% \mathbb{C}}^{q})$ is conjugate-closed and satisfies $(=_{2})\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{2}}}{\mathop{}% \kern 4.48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}% \right\rangle}}_{\mathmakebox[0pt][r]{2}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[% 0pt][r]{2}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{2}}}\left% \langle\operatorname{\mathcal{F}}\right\rangle_{0}$ and $A\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}% \kern 4.48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}% \right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[% 0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}\left% \langle\operatorname{\mathcal{F}}\right\rangle_{2}$ (or vice-versa) for some $A$ whose matrix form $A^{1,1}$ is nonsingular, then $\operatorname{\mathcal{F}}$ is quantum-nonvanishing.

Proof.

See 7(b). Let $0\neq K\in\mathchoice{\mathop{}\kern 3.84726pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{\ell}}}{% \mathop{}\kern 3.84726pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {F}}\right\rangle}}_{\mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}\right\rangle}}_{% \mathmakebox[0pt][r]{\ell}}}{\mathop{}\kern 3.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{\ell}}}% \left\langle\operatorname{\mathcal{F}}\right\rangle_{r}$ . If $\ell=0$ , then, as in the proof of Corollary 33, construct the dual $K^{*}\in\mathchoice{\mathop{}\kern 4.42825pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{r}}}{\mathop{}% \kern 4.42825pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}% \right\rangle}}_{\mathmakebox[0pt][r]{r}}}{\mathop{}\kern 4.03014pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[% 0pt][r]{r}}}{\mathop{}\kern 4.03014pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{r}}}\left% \langle\operatorname{\mathcal{F}}\right\rangle_{0}$ by connecting each right input of $K$ with a copy of $(=_{2})\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{2}}}{\mathop{}% \kern 4.48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}% \right\rangle}}_{\mathmakebox[0pt][r]{2}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[% 0pt][r]{2}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{2}}}\left% \langle\operatorname{\mathcal{F}}\right\rangle_{0}$ and conjugating all coefficients and signatures composing $K$ . Then $\langle K,K^{*}\rangle\neq 0$ , so $K$ is $\operatorname{\mathcal{F}}$ -nonvanishing. Otherwise, $(A^{1,1})^{\otimes\ell}K\neq 0$ by nonsingularity of $A^{1,1}$ , and therefore the signature $K^{\prime}\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{% \mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal% {F}}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt% \mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}\right\rangle}}_{% \mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}% \left\langle\operatorname{\mathcal{F}}\right\rangle_{\ell+r}$ formed by connecting $\ell$ copies of $A$ with the $\ell$ left inputs of $K$ (equivalently, connecting $\ell$ copies of right-facing $=_{2}$ with the $\ell$ left inputs of $(A^{1,1})^{\otimes\ell}K$ ) is nonzero. Again, since $K^{\prime}$ is now fully covariant, its dual $(K^{\prime})^{*}$ is in $\mathchoice{\mathop{}\kern 13.91443pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{\ell+r}}}{% \mathop{}\kern 13.91443pt\mathopen{\vphantom{\left\langle\operatorname{% \mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{\ell+r}}}{\mathop{}\kern 12.% 15524pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{F}}\right\rangle% }}_{\mathmakebox[0pt][r]{\ell+r}}}{\mathop{}\kern 12.15524pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[% 0pt][r]{\ell+r}}}\left\langle\operatorname{\mathcal{F}}\right\rangle_{0}$ . The $\left\langle\operatorname{\mathcal{F}}\right\rangle$ -grid formed by contracting $K^{\prime}$ and $(K^{\prime})^{*}$ contains $K$ and has nonzero value, so $K$ is $\operatorname{\mathcal{F}}$ -nonvanishing. $\hfill\blacktriangleleft$

Corollary 37.

Let $\operatorname{\mathcal{F}},\operatorname{\mathcal{G}}\subset\operatorname{% \mathcal{V}}(\operatorname{\mathbb{C}}^{q})$ be conjugate-closed. For $d\geq 3$ , if there exist $A_{1}\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{EQ}}_{\leq d}|\operatorname{\mathcal{F}}\right\rangle}}% _{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{EQ}}_{\leq d}|\operatorname{\mathcal{F}}\right% \rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{EQ}}_{\leq d}|\operatorname{% \mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283% pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{EQ}}_{\leq d}|% \operatorname{\mathcal{F}}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}\left% \langle\operatorname{\mathcal{EQ}}_{\leq d}|\operatorname{\mathcal{F}}\right% \rangle_{2}$ and $A_{2}\in\mathchoice{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left\langle% \operatorname{\mathcal{EQ}}_{\leq d}|\operatorname{\mathcal{G}}\right\rangle}}% _{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 4.48613pt\mathopen{\vphantom{\left% \langle\operatorname{\mathcal{EQ}}_{\leq d}|\operatorname{\mathcal{G}}\right% \rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283pt\mathopen{% \vphantom{\left\langle\operatorname{\mathcal{EQ}}_{\leq d}|\operatorname{% \mathcal{G}}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}{\mathop{}\kern 3.90283% pt\mathopen{\vphantom{\left\langle\operatorname{\mathcal{EQ}}_{\leq d}|% \operatorname{\mathcal{G}}\right\rangle}}_{\mathmakebox[0pt][r]{0}}}\left% \langle\operatorname{\mathcal{EQ}}_{\leq d}|\operatorname{\mathcal{G}}\right% \rangle_{2}$ whose matrix forms are nonsingular, then $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are $\operatorname{\#CSP}^{(d)}$ -indistinguishable if and only if $\operatorname{\mathcal{F}}$ and $\operatorname{\mathcal{G}}$ are isomorphic.

Specializing to $\operatorname{\mathcal{F}}=\{A_{F}\}$ and $\operatorname{\mathcal{G}}=\{A_{G}\}$ for nonsingular $A_{F}$ and $A_{G}$ , we obtain

Corollary 38.

Graphs $F$ and $G$ with nonsingular adjacency matrices are homomorphism-indistinguishable over graphs of maximum degree at most 3 if and only if they are isomorphic.

We may also apply Theorem 19, which applies to all graphs $F$ and $G$ , to obtain the first characterization of homomorphism-indistinguishability over graphs of bounded degree.

Corollary 39.

Graphs $F$ and $G$ on $q$ vertices are homomorphism-indistinguishable over all graphs of maximum degree at most $d$ if and only if $\overline{\operatorname{GL}_{q}(\operatorname{\mathcal{EQ}}_{\leq d}|A_{F})}% \cap\overline{\operatorname{GL}_{q}(\operatorname{\mathcal{EQ}}_{\leq d}|A_{G}% )}\neq\varnothing$ .

Thus the problem of determining whether two graphs are homomorphism-indistinguishable over all graphs of maximum degree at most $d$ is decidable.

The decidability result in Corollary 39, which follows from Corollary 20, answers another open question, and is interesting because homomorphism-indistinguishability over some graph classes (e.g. planar graphs [42]) is undecidable. While Theorem 19 and Corollary 20 – of which Corollary 39 is a special case – do not immediatly yield a polynomial-time algorithm for testing bounded-degree homomorphism-indistinguishability, it is possible that efficient algorithms – and a more specific, algebraic characterization than that given by Corollary 39 – exist for this case.

5.2 Indistinguishability, TOCI, and GI

Lysikov and Walter [41] define the class TOCI of (problems reducible to) orbit closure intersection problems for actions of general linear groups on finite subsets of $\bigoplus_{i=1}^{m}\operatorname{\mathcal{V}}(\operatorname{\mathbb{C}}^{q_{i}})$ (sets are allowed to contain signatures with different domains). They show that $\textbf{GI}\subset\textbf{TOCI}$ by reducing isomorphism of $q$ -vertex graphs $F$ and $G$ to $\operatorname{GL}_{q}$ -orbit-intersection of $(A_{F},=_{3}|=_{2})$ and $(A_{G},=_{3}|=_{2})$ [41, Lemma 5.26 and Proposition 5.28]¹¹1Our framework gives a short alternative proof of this reduction. First, if $F\cong G$ , then, since every permutation matrix preserves $\operatorname{\mathcal{EQ}}$ , the $\operatorname{GL}_{q}$ -orbits of $(A_{F},=_{3}|=_{2})$ and $(A_{G},=_{3}|=_{2})$ intersect. Conversely, the “easy” $(\Longleftarrow)$ direction of Theorem 19 asserts that $(A_{F},=_{3}|=_{2})$ and $(A_{G},=_{3}|=_{2})$ are Holant-indistinguishable. As in the proof of Proposition 34, contravariant $=_{3}$ and covariant $=_{2}$ together construct all of $\operatorname{\mathcal{EQ}}$ , so $(A_{F}|\operatorname{\mathcal{EQ}})$ and $(A_{G}|\operatorname{\mathcal{EQ}})$ are Holant-indistinguishable – that is, $F$ and $G$ are homomorphism-indistinguishable. Then, by Lovász’s theorem, $F\cong G$ . . They also show that the orbit closure intersection problem for $\operatorname{\mathcal{F}}$ containing two contravariant ternary signatures and one covariant binary signature, all on the same domain, is TOCI-complete [41, Corollary 1.3]. Combining these results with Theorem 19 gives the following.

Corollary 40.

The following problem is TOCI-complete: Given ternary $F_{3},F_{3}^{\prime},G_{3},G_{3}^{\prime}$ and binary $F_{2},G_{2}$ , decide whether $(F_{3},F_{3}^{\prime}\mid F_{2})$ and $(G_{3},G_{3}^{\prime}\mid G_{2})$ are Holant-indistinguishable.

Corollary 41.

The following problem is GI-hard: Given ternary $F_{3},G_{3}$ and binary $F_{2},F_{2}^{\prime},G_{2},G_{2}^{\prime}$ , decide whether $(F_{2},F_{3}\mid F_{2}^{\prime})$ and $(G_{2},G_{3}\mid G_{2}^{\prime})$ are Holant-indistinguishable.

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] Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Mendes de Oliveira, and Avi Wigderson. Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, STOC 2018, pages 172–181, New York, NY, USA, 2018. ACM. doi:10.1145/3188745.3188942.
[3] Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5), October 2013. doi:10.1145/2528400.
[4] Peter Bürgisser and Christian Ikenmeyer. Geometric complexity theory and tensor rank. In Proceedings of the forty-third annual ACM Symposium on Theory of Computing (STOC), pages 509–518, 2011. doi:10.1145/1993636.1993704.
[5] Jin-Yi Cai and Xi Chen. Complexity of counting csp with complex weights. J. ACM, 64(3), 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 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1259–1276. IEEE, 2015. doi:10.1109/FOCS.2015.81.
[8] Jin-Yi Cai and Artem Govorov. On a theorem of lovász that (., h) determines the isomorphism type of h. ACM Trans. Comput. Theory, 13(2), 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 Journal on Computing, 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. In 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, July 8-11, 2025, Aarhus, Denmark, volume 334 of LIPIcs, pages 148:1–148:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ICALP.2025.148.
[11] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Holographic algorithms by fibonacci gates and holographic reductions for hardness. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 644–653. IEEE, 2008. doi:10.1109/FOCS.2008.34.
[12] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Computational complexity of holant problems. SIAM Journal on Computing, 40(4):1101–1132, 2011. doi:10.1137/100814585.
[13] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for holant* problems with domain size 3. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1278–1295. SIAM, SIAM, 2013. doi:10.1137/1.9781611973105.93.
[14] Jin-Yi Cai and Daniel P. Szabo. Bounded degree nonnegative counting csp. ACM Trans. Comput. Theory, 16(2), March 2024. doi:10.1145/3632184.
[15] Jin-Yi Cai and Ben Young. Planar #csp equality corresponds to quantum isomorphism – a holant viewpoint. ACM Transactions on Computation Theory, 16(3), September 2024. doi:10.1145/3689486.
[16] Jin-Yi Cai and Ben Young. Vanishing signatures, orbit closure, and the converse of the holant theorem, 2025. doi:10.48550/arXiv.2509.10991.
[17] Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, and Chuanqi Zhang. On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:23, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2024.31.
[18] Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász Meets Weisfeiler and Leman. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1–40:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2018.40.
[19] Harm Derksen. Polynomial bounds for rings of invariants. Proceedings of the American Mathematical Society, 129(4):955–963, 2001.
[20] Harm Derksen and Gregor Kemper. Computational Invariant Theory. Encyclopaedia of Mathematical Sciences. Springer, Berlin, Heidelberg, 2nd ed. edition, 2015. doi:10.1007/978-3-662-48422-7.
[21] Harm Derksen and Visu Makam. Algorithms for orbit closure separation for invariants and semi-invariants of matrices. Algebra & Number Theory, 14(10):2791–2813, 2020.
[22] Harm Derksen and Visu Makam. Polystability in positive characteristic and degree lower bounds for invariant rings. Journal of Combinatorial Algebra, 6(3):353–405, 2022.
[23] Harm Derksen and Visu Makam. Invariant theory and wheeled props. Journal of Pure and Applied Algebra, 227(9):107302, 2023. doi:10.1016/j.jpaa.2022.107302.
[24] 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.
[25] Martin Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM Journal on Computing, 42(3):1245–1274, 2013. doi:10.1137/100811258.
[26] 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.
[27] Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Oliveira, Michael Walter, and Avi Wigderson. Search problems in algebraic complexity, gct, and hardness of generators for invariant rings. In Proceedings of the 35th Computational Complexity Conference, CCC ’20, Dagstuhl, DEU, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CCC.2020.12.
[28] Roe Goodman and Nolan R. Wallach. Symmetry, Representations, and Invariants. Graduate Texts in Mathematics. Springer, New York, 2009. doi:10.1007/978-0-387-79852-3.
[29] Joshua Grochow and Youming Qiao. On the complexity of isomorphism problems for tensors, groups, and polynomials i: Tensor isomorphism-completeness. SIAM Journal on Computing, 52(2):568–617, 2023. doi:10.1137/21M1441110.
[30] Joshua A. Grochow and Youming Qiao. On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, STOC ’25, pages 766–776, New York, NY, USA, 2025. ACM. doi:10.1145/3717823.3718282.
[31] Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism Tensors and Linear Equations. Advances in Combinatorics, April 2025. doi:10.19086/aic.2025.4.
[32] Pavol Hell and Jaroslav Nesetril. Graphs and homomorphisms, volume 28 of Oxford lecture series in mathematics and its applications. Oxford University Press, 2004.
[33] David Hilbert. Ueber dietheorie der algebraischen formen. Mathematische Annalen, 36:473–534, 1890.
[34] Sangxia Huang and Pinyan Lu. A dichotomy for real weighted holant problems. Computational Complexity, 25:255–304, 2016. doi:10.1007/s00037-015-0118-3.
[35] Gábor Ivanyos and Youming Qiao. On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4115–4126. SIAM, 2023. doi:10.1137/1.9781611977554.ch158.
[36] Prem Nigam Kar, David E. Roberson, Tim Seppelt, and Peter Zeman. NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 105:1–105:19, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2025.105.
[37] J. M. Landsberg. Geometry and Complexity Theory. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2017.
[38] Jiabao Lin and H. Wang. The complexity of boolean holant problems with nonnegative weights. SIAM Journal on Computing, 47(3):798–828, 2018. doi:10.1137/17M113304X.
[39] László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):321–328, 1967.
[40] László Lovász. The rank of connection matrices and the dimension of graph algebras. European Journal of Combinatorics, 27(6):962–970, 2006. doi:10.1016/j.ejc.2005.04.012.
[41] Vladimir Lysikov and Michael Walter. Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness, 2024. To appear in FOCS’25. doi:10.48550/arXiv.2411.04639.
[42] 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.
[43] David Mumford, John Fogarty, and Frances Kirwan. Geometric invariant theory, Third Edition, volume 34 of Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer, Berlin, Heidelberg, 3rd ed. edition, 1994.
[44] 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. SIAM, 2023. doi:10.1137/1.9781611977554.ch87.
[45] Guus Regts. Edge-reflection positivity and weighted graph homomorphisms. J. Comb. Theory A, 129(C):80–92, January 2015. doi:10.1016/j.jcta.2014.09.006.
[46] David E. Roberson. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree, 2022. doi:10.48550/arXiv.2206.10321.
[47] David E. Roberson and Tim Seppelt. Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability. TheoretiCS, Volume 3, September 2024. doi:10.46298/theoretics.24.20.
[48] Alexander Schrijver. Graph Invariants in the Edge Model. In Building Bridges: Between Mathematics and Computer Science, pages 487–498. Springer, Berlin, Heidelberg, 2008. doi:10.1007/978-3-540-85221-6_16.
[49] 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.
[50] Shuai Shao and Jin-Yi Cai. A dichotomy for real boolean holant problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1091–1102. IEEE, 2020. doi:10.1109/FOCS46700.2020.00105.
[51] 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.
[52] Leslie G. Valiant. Accidental algorithms. In 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, Berkeley, California, USA, October 21-24, 2006, Proceedings, pages 509–517. IEEE, IEEE Computer Society, 2006. doi:10.1109/FOCS.2006.7.
[53] Leslie G. Valiant. Holographic algorithms. SIAM Journal on Computing, 37(5):1565–1594, 2008. doi:10.1137/070682575.
[54] Hermann Weyl. The Classical Groups: Their Invariants and Representations. Princeton University Press, 1966. doi:10.2307/j.ctv3hh48t.
[55] Mingji Xia. Holographic reduction: A domain changed application and its partial converse theorems. In Automata, Languages and Programming: 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I 37, pages 666–677. Springer, 2010. doi:10.1007/978-3-642-14165-2_56.
[56] Ben Young. Equality on all #csp instances yields constraint function isomorphism via interpolation and intertwiners. The Electronic Journal of Combinatorics, 32, 2025. doi:10.37236/13879.
[57] Ben Young. The Converse of the Real Orthogonal Holant Theorem. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 136:1–136:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2025.136.

Appendix A Dictionary of Terminologies

Table 1 lists Holant concepts in this work on the left, and other names for these concepts on the right (for more on wheeled PROPs, see [16, 23]).

Table 1: Dictionary of terminologies.

Signature $F$	Tensor
Signature set $\operatorname{\mathcal{F}}$ (finite)	Tensor tuple
Signature grid $\Omega$	Tensor network
Quantum gadget signature algebra $\left\langle\operatorname{\mathcal{F}}\right\rangle$	Sub-wheeled PROP of $\operatorname{\mathcal{V}}$
$\operatorname{\mathcal{F}}$ is quantum-nonvanishing	Wheeled PROP $\left\langle\operatorname{\mathcal{F}}\right\rangle$ is simple
$\operatorname{\mathcal{F}}$ is (Bi-Holant-)vanishing	$\operatorname{\mathcal{F}}$ is in the null cone

[bib.bib1] [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.

[bib.bib2] [2] Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Mendes de Oliveira, and Avi Wigderson. Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, STOC 2018, pages 172–181, New York, NY, USA, 2018. ACM. doi:10.1145/3188745.3188942.

[bib.bib3] [3] Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5), October 2013. doi:10.1145/2528400.

[bib.bib4] [4] Peter Bürgisser and Christian Ikenmeyer. Geometric complexity theory and tensor rank. In Proceedings of the forty-third annual ACM Symposium on Theory of Computing (STOC), pages 509–518, 2011. doi:10.1145/1993636.1993704.

[bib.bib5] [5] Jin-Yi Cai and Xi Chen. Complexity of counting csp with complex weights. J. ACM, 64(3), June 2017. doi:10.1145/2822891.

[bib.bib6] [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.

[bib.bib7] [7] Jin-Yi Cai, Zhiguo Fu, Heng Guo, and Tyson Williams. A holant dichotomy: is the fkt algorithm universal? In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1259–1276. IEEE, 2015. doi:10.1109/FOCS.2015.81.

[bib.bib8] [8] Jin-Yi Cai and Artem Govorov. On a theorem of lovász that (., h) determines the isomorphism type of h. ACM Trans. Comput. Theory, 13(2), 2021. doi:10.1145/3448641.

[bib.bib9] [9] Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. SIAM Journal on Computing, 45(5):1671–1728, 2016. doi:10.1137/15M1049798.

[bib.bib10] [10] Jin-Yi Cai and Jin Soo Ihm. Holant* dichotomy on domain size 3: A geometric perspective. In 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, July 8-11, 2025, Aarhus, Denmark, volume 334 of LIPIcs, pages 148:1–148:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ICALP.2025.148.

[bib.bib11] [11] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Holographic algorithms by fibonacci gates and holographic reductions for hardness. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 644–653. IEEE, 2008. doi:10.1109/FOCS.2008.34.

[bib.bib12] [12] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Computational complexity of holant problems. SIAM Journal on Computing, 40(4):1101–1132, 2011. doi:10.1137/100814585.

[bib.bib13] [13] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for holant* problems with domain size 3. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1278–1295. SIAM, SIAM, 2013. doi:10.1137/1.9781611973105.93.

[bib.bib14] [14] Jin-Yi Cai and Daniel P. Szabo. Bounded degree nonnegative counting csp. ACM Trans. Comput. Theory, 16(2), March 2024. doi:10.1145/3632184.

[bib.bib15] [15] Jin-Yi Cai and Ben Young. Planar #csp equality corresponds to quantum isomorphism – a holant viewpoint. ACM Transactions on Computation Theory, 16(3), September 2024. doi:10.1145/3689486.

[bib.bib16] [16] Jin-Yi Cai and Ben Young. Vanishing signatures, orbit closure, and the converse of the holant theorem, 2025. doi:10.48550/arXiv.2509.10991.

[bib.bib17] [17] Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, and Chuanqi Zhang. On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:23, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2024.31.

[bib.bib18] [18] Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász Meets Weisfeiler and Leman. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1–40:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2018.40.

[bib.bib19] [19] Harm Derksen. Polynomial bounds for rings of invariants. Proceedings of the American Mathematical Society, 129(4):955–963, 2001.

[bib.bib20] [20] Harm Derksen and Gregor Kemper. Computational Invariant Theory. Encyclopaedia of Mathematical Sciences. Springer, Berlin, Heidelberg, 2nd ed. edition, 2015. doi:10.1007/978-3-662-48422-7.

[bib.bib21] [21] Harm Derksen and Visu Makam. Algorithms for orbit closure separation for invariants and semi-invariants of matrices. Algebra & Number Theory, 14(10):2791–2813, 2020.

[bib.bib22] [22] Harm Derksen and Visu Makam. Polystability in positive characteristic and degree lower bounds for invariant rings. Journal of Combinatorial Algebra, 6(3):353–405, 2022.

[bib.bib23] [23] Harm Derksen and Visu Makam. Invariant theory and wheeled props. Journal of Pure and Applied Algebra, 227(9):107302, 2023. doi:10.1016/j.jpaa.2022.107302.

[bib.bib24] [24] 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.

[bib.bib25] [25] Martin Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM Journal on Computing, 42(3):1245–1274, 2013. doi:10.1137/100811258.

[bib.bib26] [26] 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.

[bib.bib27] [27] Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Oliveira, Michael Walter, and Avi Wigderson. Search problems in algebraic complexity, gct, and hardness of generators for invariant rings. In Proceedings of the 35th Computational Complexity Conference, CCC ’20, Dagstuhl, DEU, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CCC.2020.12.

[bib.bib28] [28] Roe Goodman and Nolan R. Wallach. Symmetry, Representations, and Invariants. Graduate Texts in Mathematics. Springer, New York, 2009. doi:10.1007/978-0-387-79852-3.

[bib.bib29] [29] Joshua Grochow and Youming Qiao. On the complexity of isomorphism problems for tensors, groups, and polynomials i: Tensor isomorphism-completeness. SIAM Journal on Computing, 52(2):568–617, 2023. doi:10.1137/21M1441110.

[bib.bib30] [30] Joshua A. Grochow and Youming Qiao. On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, STOC ’25, pages 766–776, New York, NY, USA, 2025. ACM. doi:10.1145/3717823.3718282.

[bib.bib31] [31] Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism Tensors and Linear Equations. Advances in Combinatorics, April 2025. doi:10.19086/aic.2025.4.

[bib.bib32] [32] Pavol Hell and Jaroslav Nesetril. Graphs and homomorphisms, volume 28 of Oxford lecture series in mathematics and its applications. Oxford University Press, 2004.

[bib.bib33] [33] David Hilbert. Ueber dietheorie der algebraischen formen. Mathematische Annalen, 36:473–534, 1890.

[bib.bib34] [34] Sangxia Huang and Pinyan Lu. A dichotomy for real weighted holant problems. Computational Complexity, 25:255–304, 2016. doi:10.1007/s00037-015-0118-3.

[bib.bib35] [35] Gábor Ivanyos and Youming Qiao. On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4115–4126. SIAM, 2023. doi:10.1137/1.9781611977554.ch158.

[bib.bib36] [36] Prem Nigam Kar, David E. Roberson, Tim Seppelt, and Peter Zeman. NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 105:1–105:19, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2025.105.

[bib.bib37] [37] J. M. Landsberg. Geometry and Complexity Theory. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2017.

[bib.bib38] [38] Jiabao Lin and H. Wang. The complexity of boolean holant problems with nonnegative weights. SIAM Journal on Computing, 47(3):798–828, 2018. doi:10.1137/17M113304X.

[bib.bib39] [39] László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):321–328, 1967.

[bib.bib40] [40] László Lovász. The rank of connection matrices and the dimension of graph algebras. European Journal of Combinatorics, 27(6):962–970, 2006. doi:10.1016/j.ejc.2005.04.012.

[bib.bib41] [41] Vladimir Lysikov and Michael Walter. Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness, 2024. To appear in FOCS’25. doi:10.48550/arXiv.2411.04639.

[bib.bib42] [42] 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.

[bib.bib43] [43] David Mumford, John Fogarty, and Frances Kirwan. Geometric invariant theory, Third Edition, volume 34 of Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer, Berlin, Heidelberg, 3rd ed. edition, 1994.

[bib.bib44] [44] 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. SIAM, 2023. doi:10.1137/1.9781611977554.ch87.

[bib.bib45] [45] Guus Regts. Edge-reflection positivity and weighted graph homomorphisms. J. Comb. Theory A, 129(C):80–92, January 2015. doi:10.1016/j.jcta.2014.09.006.

[bib.bib46] [46] David E. Roberson. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree, 2022. doi:10.48550/arXiv.2206.10321.

[bib.bib47] [47] David E. Roberson and Tim Seppelt. Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability. TheoretiCS, Volume 3, September 2024. doi:10.46298/theoretics.24.20.

[bib.bib48] [48] Alexander Schrijver. Graph Invariants in the Edge Model. In Building Bridges: Between Mathematics and Computer Science, pages 487–498. Springer, Berlin, Heidelberg, 2008. doi:10.1007/978-3-540-85221-6_16.

[bib.bib49] [49] 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.

[bib.bib50] [50] Shuai Shao and Jin-Yi Cai. A dichotomy for real boolean holant problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1091–1102. IEEE, 2020. doi:10.1109/FOCS46700.2020.00105.

[bib.bib51] [51] 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.

[bib.bib52] [52] Leslie G. Valiant. Accidental algorithms. In 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, Berkeley, California, USA, October 21-24, 2006, Proceedings, pages 509–517. IEEE, IEEE Computer Society, 2006. doi:10.1109/FOCS.2006.7.

[bib.bib53] [53] Leslie G. Valiant. Holographic algorithms. SIAM Journal on Computing, 37(5):1565–1594, 2008. doi:10.1137/070682575.

[bib.bib54] [54] Hermann Weyl. The Classical Groups: Their Invariants and Representations. Princeton University Press, 1966. doi:10.2307/j.ctv3hh48t.

[bib.bib55] [55] Mingji Xia. Holographic reduction: A domain changed application and its partial converse theorems. In Automata, Languages and Programming: 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I 37, pages 666–677. Springer, 2010. doi:10.1007/978-3-642-14165-2_56.

[bib.bib56] [56] Ben Young. Equality on all #csp instances yields constraint function isomorphism via interpolation and intertwiners. The Electronic Journal of Combinatorics, 32, 2025. doi:10.37236/13879.

[bib.bib57] [57] Ben Young. The Converse of the Real Orthogonal Holant Theorem. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 136:1–136:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2025.136.

Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Holant Problems and the Holant Theorem

Homomorphism Indistinguishability

Orbit Equality and Orbit Closure Intersection

Our Results

Theorem (Theorem 19).

Theorem (Theorem 23).

2 Background and Preliminaries

2.1 Holant and Bi-Holant

Definition 1 (Holantℱ|ℱ′).

Definition 2 (ℰ⁢𝒬,=n).

Proposition 3.

Proof.

Definition 4 (Bi-Holant).

Definition 5 ((Bi-Holant) ℱ-gadget).

Definition 6 (𝔔ℱ,⟨ℱ⟩).

2.2 Transformations, Indistinguishability, and the Holant Theorem

Definition 7 ((⋅)ℱ→𝒢, (Bi-)Holant-indistinguishable).

Definition 8 (T⋅F, T⁢ℱ).

Theorem 9 (The Holant Theorem [53]).

Proposition 10.

Proof.

Theorem 11 (The Bi-Holant Theorem).

Example 12.

3 The Approximate Converse

Theorem 13 (Tensor First Fundamental Theorem for GLq).

Definition 14 (GLq⁡ℱ, GLq⁡ℱ¯).

Definition 15 (ℂ⁡[𝒳]).

Theorem 16 (Mumford, Fogarty, and Kirwan [43]).

Theorem 17 (Hilbert [33]).

Theorem 18.

Proof.

Theorem 19 (first main theorem).

Proof.

Corollary 20.

Corollary 21.

4 The Conditional Converse

Definition 22 (Quantum-nonvanishing, ℱ-nonvanishing).

Theorem 23 (second main theorem).

Theorem 24.

Theorem 25 ([23, Theorem 6.2, Proposition 6.5]).

Definition 26 (⊕).

Proposition 27.

Proof.

Lemma 28 ([16, Lemma 5.2]).

Lemma 29.

Proof.

Lemma 30.

Proof.

5 More Corollaries of the Main Theorems

Proposition 31.

Theorem 32 ([57, Theorem 2.3]).

Corollary 33.

Proof.

5.1 Bounded-Degree Graph Homomorphisms and #CSP

Proposition 34.

Proof.

Corollary 35.

Lemma 36.

Proof.

Corollary 37.

Corollary 38.

Corollary 39.

5.2 Indistinguishability, TOCI, and GI

Corollary 40.

Corollary 41.

References

Appendix A Dictionary of Terminologies

Definition 1 ( $\operatorname{Holant}_{\operatorname{\mathcal{F}}|\operatorname{\mathcal{F}}^{% \prime}}$ ).

Definition 2 ( $\operatorname{\mathcal{EQ}},=_{n}$ ).

Definition 5 ((Bi-Holant) $\operatorname{\mathcal{F}}$ -gadget).

Definition 6 ( $\operatorname{\mathfrak{Q}}_{\operatorname{\mathcal{F}}},\left\langle% \operatorname{\mathcal{F}}\right\rangle$ ).

Definition 7 ( $(\cdot)_{\operatorname{\mathcal{F}}\to\operatorname{\mathcal{G}}}$ , (Bi-)Holant-indistinguishable).

Definition 8 ( $T\cdot F$ , $T\operatorname{\mathcal{F}}$ ).

Theorem 13 (Tensor First Fundamental Theorem for $\operatorname{GL}_{q}$ ).

Definition 14 ( $\operatorname{GL}_{q}\operatorname{\mathcal{F}}$ , $\overline{\operatorname{GL}_{q}\operatorname{\mathcal{F}}}$ ).

Definition 15 ( $\operatorname{\mathbb{C}}[\operatorname{\mathcal{X}}]$ ).

Definition 22 (Quantum-nonvanishing, $\operatorname{\mathcal{F}}$ -nonvanishing).

Definition 26 ( $\oplus$ ).