A Tensor Network Algorithm For The Solution of 3-SAT

We present a novel tensor network approach to the solution of the 3-SAT problem. We start from a graph visualization of 3-SAT instances and find a suitable embedding of these instances on a reversible circuit defined on a lattice. We then encode the reversible circuit into a two-dimensional rectangular tensor network. We demonstrate a tensor-network compression-decimation algorithm that fully contracts the network and reaches solution in O(n) for tree-like 3-SAT instances. We examine the change of this scaling as a function of the density of cycles in the graph. Finally we compare our algorithms performance to state-of-the-art SAT solvers.