A Dichotomy for MIP* in the Presence of Unital Noise

Abstract

We study two-prover one-round quantum interactive proofs in which the provers share arbitrarily many copies of a noisy EPR pair. Prior work showed that if the shared state $\psi$ has quantum maximal correlation ${\rho }_{\max }(\psi )<1$, then ${\mathrm{MIP}}^{\psi }[\mathrm{poly},O(1)]=\mathrm{MIP}=\mathrm{NEXP}$, while noiseless EPR pairs give ${\mathrm{MIP}}^{\mathrm{EPR}}[\mathrm{poly},O(1)]=\mathrm{RE}$. That result leaves two cases open: answers of polynomial length, and noise that keeps ${\rho }_{\max }(\psi )=1$, which unital noise can do. We settle both for unital noise. Equivalently, let $\psi$ be any two-qubit state with maximally mixed marginals. We show that $${\mathsf{MIP}}^{\psi }[\mathrm{poly},\mathrm{poly}]=\mathsf{MIP}=\mathsf{NEXP},\text{if ψ is separable or ρmax(ψ)<1};$$ $${\mathsf{MIP}}^{\psi }[\mathrm{poly},\mathrm{poly}]=\mathsf{RE},\text{if ψ is entangled and ρmax(ψ)=1.}$$ Beyond this complexity-theoretic dichotomy, our proof introduces two techniques of potential independent interest. The first technique approximates quantum measurements by positive low-degree operators. We prove that the square roots of the measurement elements, after applying the smoothing operation, can be approximated by low-degree operators, with error controlled in the Schatten 4-norm. This further gives a positive low-degree approximation with small normalization error. Second, we introduce Pauli folding, a randomized dimension-reduction method for low-degree quantum operators. For fixed accuracy, the number of qubits after folding is polynomial in the Pauli degree and the number of outcomes and does not depend on $n$. Moreover, Pauli folding preserves Hilbert-Schmidt inner products in expectation and is approximately multiplicative. This is an exponential improvement over the dimension reductions via invariance principles in all previous works.