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

DOI10.1137/20M1311557MaRDI QIDQ5096443zbMATH OpenFDO

Authors Miriam Backens

Publication date 17 August 2022

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

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

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)

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.

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

Cites work

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

Cited in

(6)

• A New Holant Dichotomy Inspired by Quantum Computation
• Restricted Holant dichotomy on domains 3 and 4
• A complete dichotomy for complex-valued \(\textsc{Holant}^c\)
• 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)