A full dichotomy for Holant, inspired by quantum computation
arXiv:2201.03375 · doi:10.1137/20M1311557
Abstract
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. These two families of holant problems assume the availability of certain unary constraint functions -- the two pinning functions in the case of Holant, 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.
59 pages, combines edited versions of arXiv:1702.00767 and arXiv:1704.05798 with some new results; v2 restores a missing case to the proof of Lemma 48, see doi:10.1137/24M167723X for the corresponding erratum
References in corpus (10)
- Quantum Error Correction for Beginners
- Four qubits can be entangled in nine different ways
- The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
- Exact synthesis of multiqubit Clifford+T circuits
- Inductive Entanglement Classification of Four Qubits under SLOCC
- The Complexity of Weighted Boolean #CSP
- Completing the proof of "Generic quantum nonlocality"
- The Simple Criteria of SLOCC Equivalence Classes
- The inductive entanglement classification yields ten rather than eight classes of four-qubit entangled states
- Functional Clones and Expressibility of Partition Functions