A New Holant Dichotomy Inspired by Quantum Computation

DOI10.4230/LIPICS.ICALP.2017.16zbMATH Open1441.68159arXiv1702.00767OpenAlexW2963052590MaRDI QIDQ5111345FDOQ5111345

Authors: Miriam Backens 

Publication date: 27 May 2020

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${}^{*}$, 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.

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

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

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)

Cited In (16)

• Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
• A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation
• 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
• Perfect matchings, rank of connection tensors and graph homomorphisms
• A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
• Clifford gates in the Holant framework
• A complexity trichotomy for \(k\)-regular asymmetric spin systems with complex edge functions
• Bipartite 3-regular counting problems with mixed signs
• Complexity classification of the eight-vertex model
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• 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\)
• The Complexity of Boolean Holant Problems with Nonnegative Weights
• Title not available (Why is that?)

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)