A full dichotomy for Holantc, inspired by quantum computation

Research output: Contribution to journalArticlepeer-review

54 Downloads (Pure)

Abstract

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 Holantc. These two families of holant problems assume the availability of certain unary constraint functions - the two pinning functions in the case of Holantc, 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.

Original languageEnglish
Pages (from-to)1739-1799
JournalSIAM Journal on Computing
Volume50
Issue number6
DOIs
Publication statusPublished - 30 Nov 2021

Keywords

  • counting complexity
  • holant problems
  • computational complexity
  • entanglement

Fingerprint

Dive into the research topics of 'A full dichotomy for Holantc, inspired by quantum computation'. Together they form a unique fingerprint.

Cite this