Abstract: Stoquasticity, originating in sign-problem-free physical systems, gives rise to StoqMA, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between MA and AM. Unentanglement similarly gives rise to QMA(2), introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes QMA to two unentangled proofs and still has only the trivial NEXP upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via StoqMA(2), the class of unentangled stoquastic Merlin-Arthur proof systems. Although StoqMA is semi-quantum and may collapse to MA, StoqMA(2) turns out to be surprisingly powerful. We establish the following results: - NP⊆StoqMA(2) with O(n)-qubit proofs and completeness error 2−polylog(n). Conversely, StoqMA(2)⊆EXP via the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014); with our lower bound, our refined analysis yields the optimality of this algorithm under ETH. - StoqMA(2)1⊆PSPACE, and the containment holds with completeness error 2−2poly(n). - PreciseStoqMA(2), a variant of StoqMA(2) with exponentially small promise gap, cannot achieve perfect completeness unless EXP=NEXP. In contrast, PreciseStoqMA achieves perfect completeness, since PSPACE⊆PreciseStoqMA1. - When the completeness error is negligible, StoqMA(k)=StoqMA(2) for k≥2. Our lower bounds are obtained by stoquastizing the short-proof QMA(2) protocols via distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our new rectangular closure testing framework.
Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!
