The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems

arXiv:2605.16249v2 Announce Type: replace 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 $\rho$ 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 $\tau$ on $\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k$ such that \[ \mathrm{Tr}\big(M(\rho_{\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k} - \tau)\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.

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 $\rho$ 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 $\tau$ on $\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k$ such that \[ \mathrm{Tr}\big(M(\rho_{\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k} - \tau)\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.

Quantum Physics (quant-ph); Computational Complexity (cs.CC)

arXiv:2605.16249 [quant-ph]

(or arXiv:2605.16249v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2605.16249 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems

Related coverage