A full dichotomy for Holant^c, inspired by quantum computation

DOI10.1137/20M1311557zbMATH Open1492.68101arXiv2201.03375MaRDI QIDQ5096443FDOQ5096443

Authors: Miriam Backens 

Publication date: 17 August 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

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

Recommendations

• A New Holant Dichotomy Inspired by Quantum Computation
• A complete dichotomy for complex-valued \(\textsc{Holant}^c\)
• Dichotomy for real Holant\(^{\mathrm c}\) problems
• Computational complexity of Holant problems
• From Holant to \#CSP and back: dichotomy for Holant\(^{c }\) problems

zbMATH Keywords

computational complexityentanglementcounting complexityholant problems

Mathematics Subject Classification ID

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

Cites Work

• Quantum cryptography based on Bell’s theorem
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• The Heisenberg representation of quantum computers
• Quantum computation and quantum information. 10th anniversary edition
• Holographic Algorithms
• The Complexity of Weighted Boolean #CSP
• Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
• On the role of entanglement in quantum-computational speed-up
• Graph homomorphisms with complex values: a dichotomy theorem
• The expressibility of functions on the boolean domain, with applications to counting CSPs
• Valiant's holant theorem and matchgate tensors
• Holant problems for 3-regular graphs with complex edge functions
• The complexity of complex weighted Boolean \#CSP
• Completing the proof of ``Generic quantum nonlocality
• Simple criteria for the SLOCC classification
• Title not available (Why is that?)
• A New Holant Dichotomy Inspired by Quantum Computation
• A complete dichotomy rises from the capture of vanishing signatures
• Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
• Functional clones and expressibility of partition functions
• Clifford gates in the Holant framework
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity Dichotomies for Counting Problems
• Title not available (Why is that?)
• Holant Clones and the Approximability of Conservative Holant Problems

Cited In (4)

• Restricted Holant dichotomy on domains 3 and 4
• Bipartite 3-regular counting problems with mixed signs
• Complexity classification of the eight-vertex model
• Restricted Holant dichotomy on domain sizes 3 and 4

This page was built for publication: A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation

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