StoqMa(k) equals StoqMa for any polynomial k via a positive value-based de Finetti theorem that approximates nonnegative product values with symmetric extensions.
A quantum characterization of NP
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
fields
quant-ph 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
StoqMa(k) equals StoqMa for any polynomial k via a positive value-based de Finetti theorem that approximates nonnegative product values with symmetric extensions.