Fast counting with tensor networks
share
We introduce tensor network contraction algorithms for the counting of satisfying assignments in constraint satisfaction problems (#CSP). We represent each arbitrary #CSP instance as a tensor network whose full contraction yields the number of satisfying assignments for that instance. We then use methods of graph theory and computational complexity theory to develop fast tensor contraction protocols. In particular, we employ the tools of multilevel graph partitioning and community structure detection to determine favorable orders of contraction of arbitrary tensor networks. We first prove analytically that full tensor contraction can be performed in subexponential time for #CSP instances defined on graphs with sublinear separators. We then implement numerical heuristics for the solution of general #P-hard counting boolean satisfiability (#SAT) problems, focusing on random instances of #Cubic-Vertex-Cover as a concrete example, and show that they outperform state-of-the-art #SAT solvers by a significant margin. Our results promote tensor network contraction algorithms as a powerful practical tool for fast solution of some #CSPs.
READ FULL TEXT