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 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.00767Leibniz international proceedings in informaticsJan 1, 201721 citations

Clifford equivalence of Howard–Vala T-gates

Lingxuan Feng, Shunlong Luo

The European Physical Journal PlusJun 5, 20251 citation

Classical holons

Joseph Wheatley

Physica C SuperconductivityFeb 1, 19901 citation

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.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 ComputingJan 1, 201164 citations

Gadget Computation in Holant Problems

YANG Yang

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.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.

Jan 1, 20160 citations

The Leibniz project

David Finkelstein

Journal of Philosophical LogicJan 1, 19775 citations

\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.