arXiv preprint ·
A Dichotomy for MIP* in the Presence of Unital Noise
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
A recent work studied quantum two-prover one-round proof systems $\mathsf{MIP}^ψ[\text{poly},O(1)]$. It showed that when $ψ$ is a noisy EPR state with quantum maximal correlation $ρ_{\max}(ψ)<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}^ψ[\text{poly},\text{poly}]$, where the provers share arbitrarily many copies of EPR pairs subject to unital noise. Equivalently, let $ψ$ be a fixed two-qubit state with maximally mixed marginals. We prove that \[\mathsf{MIP}^ψ[\text{poly},\text{poly}]=\mathsf{MIP} =\mathsf{NEXP},~\text{if $ψ$ is separable or $ρ_{\max}(ψ)<1$};\]\[\mathsf{MIP}^ψ[\text{poly},\text{poly}]=\mathsf{MIP}^ψ[\text{poly},O(1)]=\mathsf{RE},\text{if $ψ$ is entangled and $ρ_{\max}(ψ)=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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Exponential separation in sensing continuous signals via squeezing
Complexity study of the Hartle-Hawking state in JT gravity
Polarisation-resolved identification of spontaneous four-wave mixing processes in a multimode fused tapered fibre coupler
Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories
A Separation Between Types of Quantum Oracle Separations
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.