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

A complete dichotomy for complex-valued holantc

Miriam Backens

Published Jul 13, 2018• 9 citations
Publisher

Abstract

Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holantc 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 Holantc and one for Holantc with complex symmetric functions, i.e. functions which only depend on the Hamming weight of the input. Here, we derive a dichotomy theorem for Holantc with complex-valued, not necessarily symmetric functions. The tractable cases are the complex-valued generalisations of the tractable cases of the real-valued Holantc dichotomy. The proof uses results from quantum information theory, particularly about entanglement. This full dichotomy for Holantc answers a question that has been open for almost a decade.

DOI
10.4230/lipics.icalp.2018.12

Related papers

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•3 citations

A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation

Miriam Backens

Holant problems are a family of counting problems parameterized by sets of algebraic-complex-valued constraint functions and defined on graphs. They arise from the theory of holographic algorithms, which was originally inspired by concepts from quantum computation. Here, we employ quantum information theory to explain existing results about holant problems in a concise way and to derive two new dichotomies: one for a new family of problems, which we call ${{Holant}}^+$, and, building on this, a full dichotomy for ${{Holant}}^c$. These two families of holant problems assume the availability of certain unary constraint functions---the two pinning functions in the case of ${{Holant}}^c$, and four functions in the case of ${{Holant}}^+$---and allow arbitrary sets of algebraic-complex valued constraint functions otherwise. The dichotomy for ${{Holant}}^+$ also applies when inputs are restricted to instances defined on planar graphs. In proving these complexity classifications, we derive an original result about entangled quantum states.

arXiv:2201.03375•SIAM Journal on Computing•Jan 1, 2021•8 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

Dichotomy for Holant Problems of Boolean Domain

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

Holant problems are a general framework to study counting problems. Both counting Constraint Satisfaction Problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant ∗ (F), where F is a set of constraint functions on Boolean variables and output complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique and indeed the formulation of the theorem use holographic algorithms and reductions. By considering these counting problems over the complex domain, we discover surprising new tractable classes, which are associated with isotropic vectors, i.e., a (non-zero) vector whose inner product with itself is zero. 1

•Aug 14, 2010•34 citations

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•64 citations

A Dichotomy for Real Boolean Holant Problems

Shuai Shao, Jin‐Yi Cai

We prove a complexity dichotomy for Holant problems on the boolean domain with arbitrary sets of real-valued constraint functions. These constraint functions need not be symmetric nor do we assume any auxiliary functions. It is proved that for every set F of real-valued constraint functions, Holant(F) is either P-time computable or #P-hard. The classification has an explicit criterion. This is a culmination of much research on this problem, and it uses many previous results and techniques. Dealing with some concrete functions plays an important role in this proof. In particular, two functions, called f6 and f8, and their associated families exhibit intriguing and extraordinary closure properties related to Bell states in quantum information theory.

Annual Symposium on Foundations of Computer Science•Nov 1, 2020•15 citations
Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holantc 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 Holantc and one for Holantc with complex symmetric functions, i.e. functions which only depend on the Hamming weight of the input. Here, we derive a dichotomy theorem for Holantc with complex-valued, not necessarily symmetric functions. The tractable cases are the complex-valued generalisations of the tractable cases of the real-valued Holantc dichotomy. The proof uses results from quantum information theory, particularly about entanglement. This full dichotomy for Holantc answers a question that has been open for almost a decade.
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 problems are a family of counting problems parameterized by sets of algebraic-complex-valued constraint functions and defined on graphs. They arise from the theory of holographic algorithms, which was originally inspired by concepts from quantum computation. Here, we employ quantum information theory to explain existing results about holant problems in a concise way and to derive two new dichotomies: one for a new family of problems, which we call Holant+{{Holant}}^+Holant+, and, building on this, a full dichotomy for Holantc{{Holant}}^cHolantc. These two families of holant problems assume the availability of certain unary constraint functions---the two pinning functions in the case of Holantc{{Holant}}^cHolantc, and four functions in the case of Holant+{{Holant}}^+Holant+---and allow arbitrary sets of algebraic-complex valued constraint functions otherwise. The dichotomy for Holant+{{Holant}}^+Holant+ also applies when inputs are restricted to instances defined on planar graphs. In proving these complexity classifications, we derive an original result about entangled quantum states.
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.
Holant problems are a general framework to study counting problems. Both counting Constraint Satisfaction Problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant ∗ (F), where F is a set of constraint functions on Boolean variables and output complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique and indeed the formulation of the theorem use holographic algorithms and reductions. By considering these counting problems over the complex domain, we discover surprising new tractable classes, which are associated with isotropic vectors, i.e., a (non-zero) vector whose inner product with itself is zero. 1
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 for Holant problems on the boolean domain with arbitrary sets of real-valued constraint functions. These constraint functions need not be symmetric nor do we assume any auxiliary functions. It is proved that for every set F of real-valued constraint functions, Holant(F) is either P-time computable or #P-hard. The classification has an explicit criterion. This is a culmination of much research on this problem, and it uses many previous results and techniques. Dealing with some concrete functions plays an important role in this proof. In particular, two functions, called f6 and f8, and their associated families exhibit intriguing and extraordinary closure properties related to Bell states in quantum information theory.