This presentation will cover the application of tensor network techniques to the solution of constrained counting problems. I will start by surveying propositional logic and will demonstrate how tensor networks can naturally express formulas of propositional logic. Depending on the choice of algebra, contraction of these networks is equivalent to either logical inference or enumeration of solutions of the corresponding formulas. Having formulated these computational problems theoretically, I will then turn to methods for contracting tensor networks of actual problem instances. Since the network structure is instance-dependent and may be irregular, the problem of finding a resource-efficient contraction order (sometimes called contraction path) is itself a nontrivial computational problem. I will first formalize this problem and define precise metrics for the computational cost of contraction associated with a contraction path. Then, I will introduce some proxy metrics of contraction cost that lend themselves to algorithmic searches yielding very high efficiency contraction paths. Finally, I will present the performance of these algorithms on model counting benchmarks and compare them to other approaches. I will also discuss the extention to weighted model counting and the classical simulation of quantum circuits as a particular example, using Google's Sycamore circuits as a benchmark.
The presentation covers parts of: J. Gray and S. Kourtis, Quantum 5, 410 (2021)