## 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.

Original language | English (US) |
---|---|

Pages (from-to) | 357-381 |

Number of pages | 25 |

Journal | Linear Algebra and Its Applications |

Volume | 466 |

DOIs | |

State | Published - Feb 1 2015 |

## All Science Journal Classification (ASJC) codes

- Algebra and Number Theory
- Numerical Analysis
- Geometry and Topology
- Discrete Mathematics and Combinatorics