A New Holant Dichotomy Inspired by Quantum Computation

DOI10.4230/LIPICS.ICALP.2017.16MaRDI QIDQ5111345zbMATH OpenOpenAlexFDO

Authors Miriam Backens

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1702.00767

zbMATH Keywords

computational complexityentanglementcounting complexityHolant dichotomy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Quantum computation (81P68) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Abstract: Holant problems are a framework for the analysis of counting complexity problems on graphs. This framework is simultaneously general enough to encompass many other counting problems on graphs and specific enough to allow the derivation of dichotomy results, partitioning all problem instances into those which can be solved in polynomial time and those which are #P-hard. The Holant framework is based on the theory of holographic algorithms, which was originally inspired by concepts from quantum computation, but this connection appears not to have been explored before. Here, we employ quantum information theory to explain existing results in a concise way and to derive a dichotomy for a new family of problems, which we call Holant${}^{+}$. This family sits in between the known families of Holant${}^{\ast }$, for which a full dichotomy is known, and Holant${}^c$, for which only a restricted dichotomy is known. Using knowledge from entanglement theory -- both previously existing work and new results of our own -- we prove a full dichotomy theorem for Holant${}^{+}$, which is very similar to the restricted Holant${}^c$ dichotomy. Other than the dichotomy for #R${}_3$-CSP, ours is the first Holant dichotomy in which the allowed functions are not restricted and in which only a finite number of functions are assumed to be freely available.

Recommendations

• A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
• A complete dichotomy for complex-valued \(\textsc{Holant}^c\)
• Computational complexity of Holant problems
• Dichotomy for real Holant\(^{\mathrm c}\) problems
• From Holant to \#CSP and back: dichotomy for Holant\(^{c }\) problems

Cited in

(18)

• Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• Hypothesis of quantum as a distributed self-organized computation by collective of particles
• The complexity of Boolean Holant problems with nonnegative weights
• Dichotomy for non-negative valued Holant problems on 3-regular bipartite graphs
• A complete dichotomy for complex-valued \(\textsc{Holant}^c\)
• Perfect matchings, rank of connection tensors and graph homomorphisms
• A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
• A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
• From holant to quantum entanglement and back
• Clifford gates in the Holant framework
• A complexity trichotomy for \(k\)-regular asymmetric spin systems with complex edge functions
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• Bipartite 3-regular counting problems with mixed signs
• Complexity classification of the eight-vertex model
• The complexity of counting planar graph homomorphisms of domain size 3
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• The complexity of counting \(\mathrm{CSP}^d\)

This page was built for publication: A New Holant Dichotomy Inspired by Quantum Computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111345)