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.
Recommendations
Cites work
- A quantum characterization of NP
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
- Quantum Arthur-Merlin games
- Quantum entanglement and communication complexity
- Semidefinite Programming
- The power of unentanglement
Cited in
(9)- Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
- Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\)
- Quantum free games
- The power of unentangled quantum proofs with non-negative amplitudes
- Shorter unentangled proofs for ground state connectivity
- NP vs QMA\(_{\log}(2)\)
- scientific article; zbMATH DE number 1530002 (Why is no real title available?)
- A quantum characterization of NP
- Characterising the intersection of QMA and coQMA
This page was built for publication: A quantum characterization of NP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q445251)
