On product, generic and random generic quantum satisfiability

Details On product, generic and random generic quantum satisfiability On product, generic and random generic quantum satisfiability

2009-10-12

arxiv.org/abs/0910.2058v2

Phys. Rev. A 81, 062345 (2010)

Physics

Quantum Physics

9 pages, 5 figures, 1 table. Updated to more closely match published version. New proof in appendix

Scientific paper

10.1103/PhysRevA.81.062345

We report a cluster of results on k-QSAT, the problem of quantum satisfiability for k-qubit projectors which generalizes classical satisfiability with k-bit clauses to the quantum setting. First we define the NP-complete problem of product satisfiability and give a geometrical criterion for deciding when a QSAT interaction graph is product satisfiable with positive probability. We show that the same criterion suffices to establish quantum satisfiability for all projectors. Second, we apply these results to the random graph ensemble with generic projectors and obtain improved lower bounds on the location of the SAT--unSAT transition. Third, we present numerical results on random, generic satisfiability which provide estimates for the location of the transition for k=3 and k=4 and mild evidence for the existence of a phase which is satisfiable by entangled states alone.

Affiliated with

Also associated with

No associations

Rating

On product, generic and random generic quantum satisfiability 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 On product, generic and random generic quantum satisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On product, generic and random generic quantum satisfiability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-463862