An exact tensor network for the 3SAT problem

Understand

We construct a tensor network that delivers an unnormalized quantum state whose coefficients are the solutions to a given instance of 3SAT, an NP-complete problem.

• The tensor network contraction that corresponds to the norm of the state counts the number of solutions to the instance.
• It follows that exact contractions of this tensor network are in the #P-complete computational complexity class, thus believed to be a hard task.
• Furthermore, we show that for a 3SAT instance with n bits, it is enough to perform a polynomial number of contractions of the tensor network structure associated to the computation of local observables to obtain one of the explicit solutions to the problem, if any.