Generalized counting constraint satisfaction problems with determinantal circuits
From MaRDI portal
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Multilinear algebra, tensor calculus (15A69) Analysis of algorithms and problem complexity (68Q25) Graph polynomials (05C31) Determinants, permanents, traces, other special matrix functions (15A15) Matrix equations and identities (15A24)
Abstract: Generalized counting constraint satisfaction problems include Holant problems with planarity restrictions; polynomial-time algorithms for such problems include matchgates and matchcircuits, which are based on Pfaffians. In particular, they use gates which are expressible in terms of a vector of sub-Pfaffians of a skew-symmetric matrix. We introduce a new type of circuit based instead on determinants, with seemingly different expressive power. In these determinantal circuits, a gate is represented by the vector of all minors of an arbitrary matrix. Determinantal circuits permit a different class of gates. Applications of these circuits include proofs of theorems from algebraic graph theory including the Chung-Langlands formula for the number of rooted spanning forests of a graph and computing Tutte Polynomials of certain matroids. They also give a strategy for simulating quantum circuits with closed timelike curves. Monoidal category theory provides a useful language for discussing such counting problems, turning combinatorial restrictions into categorical properties. We introduce the counting problem in monoidal categories and count-preserving functors as a way to study FP subclasses of problems in settings which are generally #P-hard. Using this machinery we show that, surprisingly, determinantal circuits can be simulated by Pfaffian circuits at quadratic cost.
Recommendations
- Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
- Holographic algorithms without matchgates
- Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- Holant problems and counting CSP
Cites work
- scientific article; zbMATH DE number 47926 (Why is no real title available?)
- scientific article; zbMATH DE number 1216133 (Why is no real title available?)
- scientific article; zbMATH DE number 706259 (Why is no real title available?)
- A combinatorial Laplacian with vertex weights
- Belief propagation in monoidal categories
- Categorical quantum circuits
- Complexity of counting CSP with complex weights
- Computational Complexity
- Computing the Tutte polynomial of lattice path matroids using determinantal circuits
- Geometric complexity theory. I: An approach to the P vs. NP and related problems
- Holographic algorithms without matchgates
- Lattice path matroids: Enumerative aspects and Tutte polynomials
- Multi-Path Matroids
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- The Complexity of the Counting Constraint Satisfaction Problem
- The complexity of tensor calculus
- The geometry of tensor calculus. I
- Towards an algebraic theory of Boolean circuits.
- Traced monoidal categories
Cited in
(4)
This page was built for publication: Generalized counting constraint satisfaction problems with determinantal circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472444)
