SciPost Submission Page

Fast counting with tensor networks

by Stefanos Kourtis, Claudio Chamon, Eduardo R. Mucciolo, Andrei E. Ruckenstein

Submission summary

As Contributors: Stefanos Kourtis
Preprint link: scipost_201908_00005v1
Date submitted: 2019-08-05
Submitted by: Kourtis, Stefanos
Submitted to: SciPost Physics
Domain(s): Theor. & Comp.
Subject area: Condensed Matter Physics - Computational

Abstract

We introduce tensor network contraction algorithms for counting satisfying assignments of constraint satisfaction problems (#CSPs). We represent each arbitrary #CSP formula as a tensor network, whose full contraction yields the number of satisfying assignments of that formula, and use graph theoretical methods to determine favorable orders of contraction. We employ our heuristics for the solution of #P-hard counting boolean satisfiability (#SAT) problems, namely monotone #1-in-3SAT and #Cubic-Vertex-Cover, and find that they outperform state-of-the-art solvers by a significant margin.

Current status:
Editor-in-charge assigned

Submission & Refereeing History

Submission scipost_201908_00005v1 on 5 August 2019

Login to report or comment