The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems

Abstract

Interference and entanglement are among the most fundamental properties of quantum mechanics. In this work, we investigate the power of interference in the role of detecting entanglement in the context of quantum Merlin-Arthur verification. In particular, we show that unentanglement gives no additional power to stoquastic Merlin-Arthur proof systems, whose restriction to a classical gate set results in entrywise non-negative acceptance operators and non-negative optimal witnesses, therein removing destructive interference from the verification process. Our results show that for any polynomial number of unentangled witnesses $k = k(n)$, \[ \mathsf{StoqMA}(k) = \mathsf{StoqMA}. \] The analytic core of this result is a new non-negative de Finetti theorem for separately bosonic states. If a mixed state $ρ$ is supported on the tensor product of symmetric subspaces of $\mathcal{H}_1^{\otimes R} \otimes \mathcal{H}_2^{\otimes R} \otimes \cdots \otimes \mathcal{H}_k^{\otimes R}$ then there exists a separable state $τ$ on $\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k$ such that \[ \mathrm{Tr}\big(M(ρ_{\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k} - τ)\big) \le 2 \sqrt{\frac{k\, \log_2\dim(\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k)}{R-1}}, \] simultaneously for all non-negative effects $M$. For any such operator $M$, one can define the separately symmetric lift $\mathrm{SS}_R(M)$ whose largest eigenvalue approximates the maximum acceptance probability of $M$ over product states within the same error bound. Such a lift can be approximated by a stoquastic verifier, giving that product-state constraint of $\mathsf{StoqMA}(k)$ verifiers can be absorbed into a polynomially larger one-witness $\mathsf{StoqMA}$ verification, while preserving an inverse polynomial completeness-soundness gap.