论文标题
Holant $^c $的完整二分法，灵感来自量子计算
A full dichotomy for Holant$^c$, inspired by quantum computation
论文作者
论文摘要
Holant问题是通过代数复合物有价值约束功能的一组参数进行计数问题的家族，并在图表上定义。它们来自全息算法的理论，该理论最初是受量子计算概念的启发。在这里，我们采用量子信息理论以简洁的方式来解释有关Holant问题的现有结果，并得出两个新的二分法：一个用于新的问题家族，我们称之为Holant $^+$，并在此基础上为Holant $^c $进行了完整的二分法。这两个Holant问题家族假设了某些一级约束功能的可用性 - 在Holant $^c $的情况下，两个固定功能，在Holant $^+$的情况下进行了四个功能 - 并允许任意的代数 - 复合物值的约束功能。当输入仅限于在平面图上定义的实例时，Holant $^+$的二分法也适用。在证明这些复杂性分类时，我们得出了有关纠缠量子状态的原始结果。
Holant problems are a family of counting problems parameterised 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.
