Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Biennial Symposium on Communications

On Holant theorem and its proof

Ali Al-Bashabsheh, Yongyi Mao, Abbas Yongaçoğlu

Published Jan 1, 2010• 2 citations
Publisher

Abstract

Holographic algorithms are a recent breakthrough in computer science and has found applications in information theory. This paper provides a proof to the central component of holographic algorithms, namely, the Holant theorem. The proof is simpler and more direct compared with previous works. Along the proof, we also develop a mathematical tool, which we call c-tensor. We expect the notion of c-tensor may be applicable over a wide range of analysis.

DOI
10.1109/bsc.2010.5473006

Related papers

On Holant Theorem and Its Proof

Ali Al-Bashabsheh, Yongyi Mao, Abbas Yongaçoğlu

Holographic algorithms are a recent breakthrough in computer science and has found applications in information theory. This paper provides a proof to the central component of holographic algorithms, namely, the Holant theorem. Compared with previous works, the proof appears simpler and more direct. Along the proof, we also develop a mathematical tool, which we call c-tensor. We expect the notion of c-tensor may be applicable over a wide range of analysis.

arXiv:1005.1349•May 8, 2010•0 citations

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

Jin‐Yi Cai, Young, Ben

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.

arXiv:2509.10991•Leibniz international proceedings in informatics•Sep 13, 2025•0 citations

A New Holant Dichotomy Inspired by Quantum Computation

Miriam Backens

Holant problems are a framework for the analysis of counting complexity problems on graphs. This framework is simultaneously general enough to encompass many counting problems on graphs and specific enough to allow the derivation of dichotomy results, partitioning all problems into those which are in FP and those which are #P-hard. The Holant framework is based on the theory of holographic algorithms, which was originally inspired by concepts from quantum computation, but this connection appears not to have been explored before. Here, we employ quantum information theory to explain existing results in a concise way and to derive a dichotomy for a new family of problems, which we call Holant^+. This family sits in between the known families of Holant^*, for which a full dichotomy is known, and Holant^c, for which only a restricted dichotomy is known. Using knowledge from entanglement theory -- both previously existing work and new results of our own -- we prove a full dichotomy theorem for Holant^+, which is very similar to the restricted Holant^c dichotomy and may thus be a stepping stone to a full dichotomy for that family.

arXiv:1702.00767•Leibniz international proceedings in informatics•Jan 1, 2017•21 citations

The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights

Jiabao Lin, Hanpin Wang

Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Holant problems over Boolean domain with non-negative weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric. Holant problems are indeed read-twice $\#$CSPs. Intuitively, some $\#$CSPs that are $\#$P-hard become tractable when restricting to read-twice instances. To capture them, we introduce the Block-rank-one condition. It turns out that the condition leads to a clear separation. If a function set $\mathcal{F}$ satisfies the condition, then $\mathcal{F}$ is of affine type or product type. Otherwise (a) $\mathrm{Holant}(\mathcal{F})$ is $\#$P-hard; or (b) every function in $\mathcal{F}$ is a tensor product of functions of arity at most 2; or (c) $\mathcal{F}$ is transformable to a product type by some real orthogonal matrix. Holographic transformations play an important role in both the hardness proof and the characterization of tractability.

arXiv:1611.00975•Leibniz international proceedings in informatics•Nov 3, 2016•7 citations

Dichotomy for Real Holantc Problems

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

Holant problems capture a class of Sum-of-Product computations such as counting matchings. It is inspired by holographic algorithms and is equivalent to tensor networks, with counting CSP being a special case. A complexity classification for Holant problems is more difficult to prove, not only because it logically implies a classification for counting CSP, but also due to the deeper reason that there exist more intricate polynomial time tractable problems in the broader framework. We discover a new family of constraint functions ℒ which define polynomial time computable counting problems. These do not appear in counting CSP, and no newly discovered tractable constraints can be symmetric. It has a delicate support structure related to error-correcting codes. Local holographic transformations is fundamental in its tractability. We prove a complexity dichotomy theorem for all Holant problems defined by any real valued constraint function set on Boolean variables and contains two 0–1 pinning functions. Previously, dichotomy for the same framework was only known for symmetric constraint functions. The set ℒ supplies the last piece of tractability. We also prove a dichotomy for a variant of counting CSP as a technical component toward this Holant dichotomy.

Society for Industrial and Applied Mathematics eBooks•Jan 1, 2018•12 citations

Quantum Information Approaches to Holographic Dualities

A. Jahn

The AdS/CFT correspondence, a remarkable duality between certain gravitational theories in anti-de Sitter (AdS) spacetime and quantum field theories with conformal symmetry (CFT), has had a profound effect on the development of theoretical physics in the past two decades. Recently, many connections of AdS/CFT to quantum information theory have been found, in particular by providing gravitationally dual descriptions of various entanglement measures. Understanding these manifestions of AdS/CFT --- or more generally, the conjectured holographic principle encompassing it --- requires the combination of tools from both high-energy theory and quantum information physics. In this cumulative thesis, the convergence between these two fields is approached from two fronts: First, by calculations within the dual gravitational theory, and second, using a tensor network ansatz to describe the quantum states suspected to possess such a gravitational description. In the first approach, using the gravitational side of AdS/CFT, entanglement entropies of complicated 2+1-dimensional excited CFTs are computed, thus showing how the holographic approach provides access to systems previously out of reach of practical methods, while introducing new numerical methods that this approach necessitates. The second approach is given by tensor networks, a highly successful ansatz for computing properties of one- and two-dimensional quantum systems. Efficiently computable classes of tensor networks are tested in their ability to represent simple holographic systems, successfully reproducing both hyperbolic geometrical features as well as critical boundary states. In addition, the general properties of tensor networks on regular hyperbolic tesselations are considered, leading to new connections to models not previously considered in the context of holography. This interplay of different approaches to quantum information holography showcases the richness of this new field and suggests that a wide range of physical phenomena is accessible via the new tools now at our disposal.

•Jan 1, 2021•0 citations
Holographic algorithms are a recent breakthrough in computer science and has found applications in information theory. This paper provides a proof to the central component of holographic algorithms, namely, the Holant theorem. The proof is simpler and more direct compared with previous works. Along the proof, we also develop a mathematical tool, which we call c-tensor. We expect the notion of c-tensor may be applicable over a wide range of analysis.
Valiant's Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets F\mathcal{F}F and G\mathcal{G}G of tensors (a.k.a. constraint functions or signatures) are related by a \emph{holographic transformation}, then F\mathcal{F}F and G\mathcal{G}G are \emph{Holant-indistinguishable}, i.e., every tensor network using tensors from F\mathcal{F}F, resp. from G\mathcal{G}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 F\mathcal{F}F and G\mathcal{G}G always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their GLq\text{GL}_qGLq​-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.
Holant problems are a framework for the analysis of counting complexity problems on graphs. This framework is simultaneously general enough to encompass many counting problems on graphs and specific enough to allow the derivation of dichotomy results, partitioning all problems into those which are in FP and those which are #P-hard. The Holant framework is based on the theory of holographic algorithms, which was originally inspired by concepts from quantum computation, but this connection appears not to have been explored before. Here, we employ quantum information theory to explain existing results in a concise way and to derive a dichotomy for a new family of problems, which we call Holant^+. This family sits in between the known families of Holant^*, for which a full dichotomy is known, and Holant^c, for which only a restricted dichotomy is known. Using knowledge from entanglement theory -- both previously existing work and new results of our own -- we prove a full dichotomy theorem for Holant^+, which is very similar to the restricted Holant^c dichotomy and may thus be a stepping stone to a full dichotomy for that family.
Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Holant problems over Boolean domain with non-negative weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric. Holant problems are indeed read-twice #\##CSPs. Intuitively, some #\##CSPs that are #\##P-hard become tractable when restricting to read-twice instances. To capture them, we introduce the Block-rank-one condition. It turns out that the condition leads to a clear separation. If a function set F\mathcal{F}F satisfies the condition, then F\mathcal{F}F is of affine type or product type. Otherwise (a) Holant(F)\mathrm{Holant}(\mathcal{F})Holant(F) is #\##P-hard; or (b) every function in F\mathcal{F}F is a tensor product of functions of arity at most 2; or (c) F\mathcal{F}F is transformable to a product type by some real orthogonal matrix. Holographic transformations play an important role in both the hardness proof and the characterization of tractability.
Holant problems capture a class of Sum-of-Product computations such as counting matchings. It is inspired by holographic algorithms and is equivalent to tensor networks, with counting CSP being a special case. A complexity classification for Holant problems is more difficult to prove, not only because it logically implies a classification for counting CSP, but also due to the deeper reason that there exist more intricate polynomial time tractable problems in the broader framework. We discover a new family of constraint functions ℒ which define polynomial time computable counting problems. These do not appear in counting CSP, and no newly discovered tractable constraints can be symmetric. It has a delicate support structure related to error-correcting codes. Local holographic transformations is fundamental in its tractability. We prove a complexity dichotomy theorem for all Holant problems defined by any real valued constraint function set on Boolean variables and contains two 0–1 pinning functions. Previously, dichotomy for the same framework was only known for symmetric constraint functions. The set ℒ supplies the last piece of tractability. We also prove a dichotomy for a variant of counting CSP as a technical component toward this Holant dichotomy.
The AdS/CFT correspondence, a remarkable duality between certain gravitational theories in anti-de Sitter (AdS) spacetime and quantum field theories with conformal symmetry (CFT), has had a profound effect on the development of theoretical physics in the past two decades. Recently, many connections of AdS/CFT to quantum information theory have been found, in particular by providing gravitationally dual descriptions of various entanglement measures. Understanding these manifestions of AdS/CFT --- or more generally, the conjectured holographic principle encompassing it --- requires the combination of tools from both high-energy theory and quantum information physics. In this cumulative thesis, the convergence between these two fields is approached from two fronts: First, by calculations within the dual gravitational theory, and second, using a tensor network ansatz to describe the quantum states suspected to possess such a gravitational description. In the first approach, using the gravitational side of AdS/CFT, entanglement entropies of complicated 2+1-dimensional excited CFTs are computed, thus showing how the holographic approach provides access to systems previously out of reach of practical methods, while introducing new numerical methods that this approach necessitates. The second approach is given by tensor networks, a highly successful ansatz for computing properties of one- and two-dimensional quantum systems. Efficiently computable classes of tensor networks are tested in their ability to represent simple holographic systems, successfully reproducing both hyperbolic geometrical features as well as critical boundary states. In addition, the general properties of tensor networks on regular hyperbolic tesselations are considered, leading to new connections to models not previously considered in the context of holography. This interplay of different approaches to quantum information holography showcases the richness of this new field and suggests that a wide range of physical phenomena is accessible via the new tools now at our disposal.