A Quantum Characterization Of NP
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 into the power of quantum information and the impact of entanglement.
quantum complexity interactive proof