  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. Physical realization of a state described by a generic
tensor network is equivalent to finding the satisfying assignment of a 3SAT
instance and, consequently, this experimental task is expected to be hard.
