Abstract
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 verifier 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 verifier. 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.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.