A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation
From MaRDI portal
Publication:5096443
DOI10.1137/20M1311557zbMath1492.68101arXiv2201.03375MaRDI QIDQ5096443
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
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)
Related Items
Complexity classification of the eight-vertex model ⋮ Bipartite 3-regular counting problems with mixed signs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Holant problems for 3-regular graphs with complex edge functions
- The complexity of complex weighted Boolean \#CSP
- Simple criteria for the SLOCC classification
- Clifford gates in the Holant framework
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- Functional clones and expressibility of partition functions
- Valiant's holant theorem and matchgate tensors
- Completing the proof of ``Generic quantum nonlocality
- A Complete Dichotomy Rises from the Capture of Vanishing Signatures
- Quantum Computation and Quantum Information
- Holographic Algorithms
- The Complexity of Weighted Boolean #CSP
- Quantum cryptography based on Bell’s theorem
- Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
- Complexity Dichotomies for Counting Problems
- On the role of entanglement in quantum-computational speed-up
- Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
- Holant Clones and the Approximability of Conservative Holant Problems
- A New Holant Dichotomy Inspired by Quantum Computation
- The expressibility of functions on the boolean domain, with applications to counting CSPs
- Graph Homomorphisms with Complex Values: A Dichotomy Theorem
