Generalized counting constraint satisfaction problems with determinantal circuits

DOI10.1016/J.LAA.2014.09.050zbMATH Open1302.05108arXiv1302.1932OpenAlexW2084163074MaRDI QIDQ472444FDOQ472444

Authors: Jason Morton, Jacob M. Turner 

Publication date: 19 November 2014

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

monoidal categoriescounting complexitytensor network

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational Complexity
• The geometry of tensor calculus. I
• The Complexity of the Counting Constraint Satisfaction Problem
• Traced monoidal categories
• Complexity of counting CSP with complex weights
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• The complexity of tensor calculus
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• Categorical quantum circuits
• A combinatorial Laplacian with vertex weights
• Towards an algebraic theory of Boolean circuits.
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• Holographic algorithms without matchgates
• Computing the Tutte polynomial of lattice path matroids using determinantal circuits
• Belief propagation in monoidal categories
• Multi-Path Matroids

Cited In (4)

• Tensor network contractions for \#SAT
• Computing the Tutte polynomial of lattice path matroids using determinantal circuits
• Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
• A finite-tame-wild trichotomy theorem for tensor diagrams

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)