A quantum characterization of NP

Details A quantum characterization of NP A quantum characterization of NP

2007-09-05

arxiv.org/abs/0709.0738v2

Physics

Quantum Physics

The class QMA_Log(2) have been replace by PQMA_log(2) where the power of the verifier is slightly weaker

Scientific paper

In this article we introduce a new complexity class called PQMA_log(2). Informally, this is the class of languages for which membership has a logarithmic-size quantum proof with perfect completeness and soundness which is polynomially close to 1 in a context where the veri?er is provided a proof with two unentangled parts. We then show that PQMA_log(2) = NP. For this to be possible, it is important, when defining the class, not to give too much power to the veri?er. This result, when compared to the fact that QMA_log = BQP, gives us new insight on the power of quantum information and the impact of entanglement.

Affiliated with

Also associated with

No associations

Rating

A quantum characterization of NP 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 A quantum characterization of NP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A quantum characterization of NP will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-657163