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.
翻译：长期的问题是一个以数数复合值值限制功能参数参数计算问题的家庭, 并在图表中定义。 它们来自全息算法理论, 最初是由量子计算的概念所启发的。 在这里, 我们使用量子信息理论, 以简洁的方式解释关于兴奋剂问题的现有结果, 并得出两个新的二分法: 一个是新问题家族的二分法, 我们称之为Holant$ $ $ $, 在此基础上, 完全分解Holant$ $ 。 这两个摇篮问题家庭 假设了某些单项限制功能的可用性, 即Holant$ $ $ 的两分法函数, 和 Holant $ $ 的四元函数 。 并且允许任意的数位数分法值限制功能。 当输入限于平面图上界定的情况时, 霍伦特$ $ 的二分法 也适用 。 为了证明这些复杂性分类, 我们得出关于混合量度状态的原始结果 。
相关内容
微信扫码咨询专知VIP会员