A Dichotomy for MIP* in the Presence of Unital Noise

Abstract:A recent work studied quantum two-prover one-round proof systems $\mathsf{MIP}^{\psi}[\text{poly},O(1)]$. It showed that when $\psi$ is a noisy EPR state with quantum maximal correlation $\rho_{\max}(\psi)<1$, the resulting complexity class is equivalent to $\mathsf{NEXP}=\mathsf{MIP}$. In contrast, $\mathsf{MIP}^{\text{EPR}}[\text{poly},O(1)]=\mathsf{RE}$. Not all noise, however, decreases quantum maximal correlation. A basic example is dephasing noise: a dephased EPR pair retain quantum maximal correlation $1$. In this work, we remove the constant-answer restriction and establish a complete dichotomy for $\mathsf{MIP}^{\psi}[\text{poly},\text{poly}]$, where the provers share arbitrarily many copies of EPR pairs subject to unital noise. Equivalently, let $\psi$ be a fixed two-qubit state with maximally mixed marginals. We prove that \[\mathsf{MIP}^{\psi}[\text{poly},\text{poly}]=\mathsf{MIP} =\mathsf{NEXP},~\text{if $\psi$ is separable or $\rho_{\max}(\psi)<1$};\]\[\mathsf{MIP}^{\psi}[\text{poly},\text{poly}]=\mathsf{MIP}^{\psi}[\text{poly},O(1)]=\mathsf{RE},\text{if $\psi$ is entangled and $\rho_{\max}(\psi)=1$.}\] Beyond the complexity classification, our proof develops two techniques that may be useful more broadly in quantum information and quantum complexity. First, we introduce a positivity-preserving low-degree approximation framework for quantum measurements: instead of truncating positive operators directly in the Pauli basis, we approximate suitable square-root factorizations, simultaneously achieving low Pauli degree, positivity, and global control over an entire POVM. Second, we develop a new dimension-reduction method, called Pauli folding, for low-degree positive operators. Its key ingredient is an almost-multiplicativity theorem for randomized Pauli hashing, which allows noncommutative products, positivity, and normalization to survive compression with controlled error.

arXiv:2609.39318 [quant-ph]

(or arXiv:2609.39318v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.39318 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

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.