Valiant's Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets $\mathcal{F}$ and $\mathcal{G}$ of tensors (a.k.a. constraint functions or signatures) are related by a \emph{holographic transformation}, then $\mathcal{F}$ and $\mathcal{G}$ are \emph{Holant-indistinguishable}, i.e., every tensor network using tensors from $\mathcal{F}$, resp. from $\mathcal{G}$, contracts to the same value. Xia (ICALP 2010) conjectured the converse of the Holant theorem, but a counterexample was found based on \emph{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 $\mathcal{F}$ and $\mathcal{G}$ always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their $\text{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 \textbf{TOCI} introduced by Lysikov and Walter, and hence hard for graph isomorphism.

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

Recently, Cai [ 3 ] showed that Shor’s quantum factoring algorithm fails to factor large integers when algorithm’s quantum Fourier transform (QFT) is corrupted by a vanishing level of random noise on the QFT’s precise controlled rotation gates. We show that under the same error model, Shor’s quantum discrete log algorithm, and its various modifications, fail to compute discrete logs modulo P for a positive density of primes P and a similarly vanishing level of noise. We also show that the same noise level causes Shor’s algorithm to fail with probability \(1-o(1)\) to compute discrete logs modulo P for randomly selected primes P .

Recently, Mančinska and Roberson proved [Mančinska and Roberson, 2020] that two graphs G and G' are quantum isomorphic if and only if they admit the same number of homomorphisms from all planar graphs. We extend this result to planar #CSP with any pair of sets ℱ and ℱ' of real-valued, arbitrary-arity constraint functions. Graph homomorphism is the special case where each of ℱ and ℱ' contains a single symmetric 0-1-valued binary constraint function. Our treatment uses the framework of planar Holant problems. To prove that quantum isomorphic constraint function sets give the same value on any planar #CSP instance, we apply a novel form of holographic transformation of Valiant [Valiant, 2008], using the quantum permutation matrix 𝒰 defining the quantum isomorphism. Due to the noncommutativity of 𝒰’s entries, it turns out that this form of holographic transformation is only applicable to planar Holant. To prove the converse, we introduce the quantum automorphism group Qut(ℱ) of a set of constraint functions/tensors ℱ, and characterize the intertwiners of Qut(ℱ) as the signature matrices of planar Holant(ℱ | EQ) quantum gadgets. Then we define a new notion of (projective) connectivity for constraint functions and reduce arity while preserving the quantum automorphism group. Finally, to address the challenges posed by generalizing from 0-1 valued to real-valued constraint functions, we adapt a technique of Lovász [László Lovász, 1967] in the classical setting for isomorphisms of real-weighted graphs to the setting of quantum isomorphisms.