  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.
