StoqMa(k) equals StoqMa for any polynomial k via a positive value-based de Finetti theorem that approximates nonnegative product values with symmetric extensions.
Short multi-prover quantum proofs for SAT without entangled measurements
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
BellQMA protocols are a subclass of multi-prover quantum Merlin-Arthur protocols in which the verifier is restricted to perform nonadaptive,unentangled measurements on the quantum states received from each Merlin. In this paper, we prove that m-clause 3-SAT instances have BellQMA proofs of satisfiability with constant soundness gap, in which O(sqrt(m)polylog(m)) Merlins each send O(log m) qubits to Arthur. Our result answers a question of Aaronson et al., who gave a protocol with similar parameters that used entangled measurements; the analysis of our protocol is significantly simpler than that of Aaronson et al. Our result also complements recent work of Brandao, Christandl, and Yard, who showed upper bounds on the power of multiprover quantum proofs with unentangled but adaptive (LOCC) measurements.
fields
quant-ph 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
StoqMA(2) contains NP with Õ(√n)-qubit proofs and completeness error 2^{-polylog(n)}, is contained in EXP, and satisfies StoqMA(k)=StoqMA(2) for k≥2 when completeness error is negligible.
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.
-
Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference
StoqMA(2) contains NP with Õ(√n)-qubit proofs and completeness error 2^{-polylog(n)}, is contained in EXP, and satisfies StoqMA(k)=StoqMA(2) for k≥2 when completeness error is negligible.