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

Gadget Computation in Holant Problems

YANG Yang

Published Jan 1, 2016• 0 citations
Publisher

Abstract

F-gate and interpolation method are common reduction techniques in process of Holant dichotomy theorem’s proof,and Gadget computation plays an important role.In order to increase the computational efficiency of Garget,this paper proposes a general algorithm based on edge enumeration and matrix computation.But the general algorithm only computes in exponential time,so aiming at this problem,this paper proposes an accelerative algorithm by introducing the special function.It calls special functions according to the degrees of freedom,which makes Holant problems be solved in polynomial computation time.Moreover,this paper finds that Gadget computation can be extended to Holant(F∪[1,1]) problem,and the accelerated algorithm can also show the tractable families of the problem.

DOI
10.3969/j.issn.1000-3428.2016.01.002

Related papers

Computational Complexity of Holant Problems

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant problems. Compared to counting constraint satisfaction problems (#CSP), it is a refinement with a more explicit role for the constraint functions. Both graph homomorphism and #CSP can be viewed as special cases of Holant problems. We prove complexity dichotomy theorems in this framework. Our dichotomy theorems apply to local constraint functions, which are symmetric functions on Boolean input variables and evaluate to arbitrary real or complex values. We discover surprising tractable subclasses of counting problems, which could not easily be specified in the #CSP framework. When all unary functions are assumed to be free ($\mathrm{Holant}^*$ problems), the tractable ones consist of functions that are degenerate, or of arity at most two, or holographic transformations of Fibonacci gates. When only two special unary functions, the constant zero and constant one functions, are assumed to be free ($\mathrm{Holant}^c$ problems), we further identify three special families of tractable cases. Then we prove that all other cases are #P-hard. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations.

SIAM Journal on Computing•Jan 1, 2011•67 citations

Holant Problems for Regular Graphs with Complex Edge Functions

Michael Kowalczyk, Jin‐Yi Cai

We prove a complexity dichotomy theorem for Holant Problems on $3$-regular graphs with an arbitrary complex-valued edge function. Three new techniques are introduced: (1) higher dimensional iterations in interpolation; (2) Eigenvalue Shifted Pairs, which allow us to prove that a pair of combinatorial gadgets \emph{in combination} succeed in proving \#P-hardness; and (3) algebraic symmetrization, which significantly lowers the \emph{symbolic complexity} of the proof for computational complexity. With \emph{holographic reductions} the classification theorem also applies to problems beyond the basic model.

Leibniz international proceedings in informatics•Jan 1, 2010•15 citations

Holant Problems for Regular Graphs with Complex Edge Functions

Michael Kowalczyk, Jin‐Yi Cai

We prove a complexity dichotomy theorem for Holant Problems on 3-regular graphs with an arbitrary complex-valued edge function. Three new techniques are introduced: (1) higher dimensional iterations in interpolation; (2) Eigenvalue Shifted Pairs, which allow us to prove that a pair of combinatorial gadgets in combination succeed in proving #P-hardness; and (3) algebraic symmetrization, which significantly lowers the symbolic complexity of the proof for computational complexity. With holographic reductions the classification theorem also applies to problems beyond the basic model.

arXiv:1001.0464•Jan 4, 2010•15 citations

A Complete Dichotomy for Complex-Valued Holant^c

Miriam Backens

Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holant^c denotes a subfamily of those problems, where any function set considered must contain the two unary functions pinning inputs to values 0 or 1. The complexity classification of Holant problems usually takes the form of dichotomy theorems, showing that for any set of functions in the family, the problem is either #P-hard or it can be solved in polynomial time. Previous such results include a dichotomy for real-valued Holant^c and one for Holant^c with complex symmetric functions. Here, we derive a dichotomy theorem for Holant^c with complex-valued, not necessarily symmetric functions. The tractable cases are the complex-valued generalisations of the tractable cases of the real-valued Holant^c dichotomy. The proof uses results from quantum information theory, particularly about entanglement.

arXiv:1704.05798•Leibniz international proceedings in informatics•Apr 19, 2017•25 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•11 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•30 citations
F-gate and interpolation method are common reduction techniques in process of Holant dichotomy theorem’s proof,and Gadget computation plays an important role.In order to increase the computational efficiency of Garget,this paper proposes a general algorithm based on edge enumeration and matrix computation.But the general algorithm only computes in exponential time,so aiming at this problem,this paper proposes an accelerative algorithm by introducing the special function.It calls special functions according to the degrees of freedom,which makes Holant problems be solved in polynomial computation time.Moreover,this paper finds that Gadget computation can be extended to Holant(F∪[1,1]) problem,and the accelerated algorithm can also show the tractable families of the problem.
We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant problems. Compared to counting constraint satisfaction problems (#CSP), it is a refinement with a more explicit role for the constraint functions. Both graph homomorphism and #CSP can be viewed as special cases of Holant problems. We prove complexity dichotomy theorems in this framework. Our dichotomy theorems apply to local constraint functions, which are symmetric functions on Boolean input variables and evaluate to arbitrary real or complex values. We discover surprising tractable subclasses of counting problems, which could not easily be specified in the #CSP framework. When all unary functions are assumed to be free (Holant∗\mathrm{Holant}^*Holant∗ problems), the tractable ones consist of functions that are degenerate, or of arity at most two, or holographic transformations of Fibonacci gates. When only two special unary functions, the constant zero and constant one functions, are assumed to be free (Holantc\mathrm{Holant}^cHolantc problems), we further identify three special families of tractable cases. Then we prove that all other cases are #P-hard. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations.
We prove a complexity dichotomy theorem for Holant Problems on 333-regular graphs with an arbitrary complex-valued edge function. Three new techniques are introduced: (1) higher dimensional iterations in interpolation; (2) Eigenvalue Shifted Pairs, which allow us to prove that a pair of combinatorial gadgets \emph{in combination} succeed in proving \#P-hardness; and (3) algebraic symmetrization, which significantly lowers the \emph{symbolic complexity} of the proof for computational complexity. With \emph{holographic reductions} the classification theorem also applies to problems beyond the basic model.
We prove a complexity dichotomy theorem for Holant Problems on 3-regular graphs with an arbitrary complex-valued edge function. Three new techniques are introduced: (1) higher dimensional iterations in interpolation; (2) Eigenvalue Shifted Pairs, which allow us to prove that a pair of combinatorial gadgets in combination succeed in proving #P-hardness; and (3) algebraic symmetrization, which significantly lowers the symbolic complexity of the proof for computational complexity. With holographic reductions the classification theorem also applies to problems beyond the basic model.
Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holant^c denotes a subfamily of those problems, where any function set considered must contain the two unary functions pinning inputs to values 0 or 1. The complexity classification of Holant problems usually takes the form of dichotomy theorems, showing that for any set of functions in the family, the problem is either #P-hard or it can be solved in polynomial time. Previous such results include a dichotomy for real-valued Holant^c and one for Holant^c with complex symmetric functions. Here, we derive a dichotomy theorem for Holant^c with complex-valued, not necessarily symmetric functions. The tractable cases are the complex-valued generalisations of the tractable cases of the real-valued Holant^c dichotomy. The proof uses results from quantum information theory, particularly about entanglement.
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 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.