An exact tensor network for the 3SAT problem

Details An exact tensor network for the 3SAT problem An exact tensor network for the 3SAT problem

2011-05-16

arxiv.org/abs/1105.3201v2

Quantum Information and Computation Vol.12 No.3&4, 0283-0292 (2012)

Physics

Quantum Physics

10 pages, 2 figures. New numerical examples

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

An exact tensor network for the 3SAT problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An exact tensor network for the 3SAT problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An exact tensor network for the 3SAT problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-727448