A quantum characterization of NP
arXiv:0709.0738
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.
The class QMA_Log(2) have been replace by PQMA_log(2) where the power of the verifier is slightly weaker
Cited by in corpus (8)
- Entanglement Theory and the Quantum Simulation of Many-Body Physics
- Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements
- Improved Soundness for QMA with Multiple Provers
- Limitations of semidefinite programs for separable states and entangled games
- Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap
- One-Sided Error QMA with Shared EPR Pairs -- A Simpler Proof
- The Power of Unentanglement
- QMA(2) with postselection equals to NEXP