Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.39318

A Dichotomy for MIP* in the Presence of Unital Noise

Yangjing Dong, Zhenyu Jiang, Minglong Qin, Penghui Yao, Haigang Zhou

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

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.

Related papers

A doubly exponential upper bound on noisy EPR states for binary games

Penghui Yao

This paper initiates the study of a class of entangled games, mono-state games, denoted by $(G,ψ)$, where $G$ is a two-player one-round game and $ψ$ is a bipartite state independent of the game $G$. In the mono-state game $(G,ψ)$, the players are only allowed to share arbitrary copies of $ψ$. This paper provides a doubly exponential upper bound on the copies of $ψ$ for the players to approximate the value of the game to an arbitrarily small constant precision for any mono-state binary game $(G,ψ)$, if $ψ$ is a noisy EPR state, which is a two-qubit state with completely mixed states as marginals and maximal correlation less than $1$. In particular, it includes $(1-ε)|Ψ\rangle\langleΨ|+ε\frac{I_2}{2}\otimes\frac{I_2}{2}$, an EPR state with an arbitrary depolarizing noise $ε>0$.The structure of the proofs is built the recent framework about the decidability of the non-interactive simulation of joint distributions, which is completely different from all previous optimization-based approaches or "Tsirelson's problem"-based approaches. This paper develops a series of new techniques about the Fourier analysis on matrix spaces and proves a quantum invariance principle and a hypercontractive inequality of random operators. This novel approach provides a new angle to study the decidability of the complexity class MIP$^*$, a longstanding open problem in quantum complexity theory.

arXiv:1904.08832•Apr 18, 2019•1 citation

Nonlocal Games with Noisy Maximally Entangled States are Decidable

Minglong Qin, Penghui Yao

This paper considers a special class of nonlocal games $(G,\psi)$, where $G$ is a two-player one-round game, and $\psi$ is a bipartite state independent of $G$. In the game $(G,\psi)$, the players are allowed to share arbitrarily many copies of $\psi$. The value of the game $(G,\psi)$, denoted by $\omega^*(G,\psi)$, is the supremum of the winning probability that the players can achieve with arbitrarily many copies of preshared states $\psi$. For a noisy maximally entangled state $\psi$, a two-player one-round game $G$ and an arbitrarily small precision $\epsilon>0$, this paper proves an upper bound on the number of copies of $\psi$ for the players to win the game with a probability $\epsilon$ close to $\omega^*(G,\psi)$. A noisy maximally entangled state is a two-qudit state with both marginals being completely mixed states and the maximal correlation being less than $1$. In particular, it includes $(1-\epsilon)|\Psi_m\rangle\langle\Psi_m|+\epsilon\frac{\mathbbm{1}_m}{m}\otimes\frac{\mathbbm{1}_m}{m}$ for $\epsilon>0$, where $|\Psi_m\rangle=\frac{1}{\sqrt{m}}\sum_{i=0}^{m-1}|m,m\rangle$ is an $m$-dimensional maximally entangled state. Hence, it is feasible to approximately compute $\omega^*(G,\psi)$ to an arbitrary precision. Recently, a breakthrough result by Ji et al. showed that it is undecidable to approximate the values of nonlocal games to a constant precision, when the players preshare arbitrarily many copies of perfect maximally entangled states, which implies that $\mathrm{MIP}^*=\mathrm{RE}$. In contrast, our result implies the hardness of approximating nonlocal games collapses when the preshared maximally entangled states are noisy. The paper develops a theory of Fourier analysis on matrix spaces by extending a number of techniques in Boolean analysis and Hermitian analysis to matrix spaces. We establish a series of new techniques, such as a quantum invariance principle and a hypercontractive inequality for random operators, which we believe have further applications. (A corrected version is attached.)

arXiv:2108.09140•SIAM Journal on Computing•Jan 1, 2021•11 citations

Quantum soundness of the classical low individual degree test

Zhengfeng Ji, Anand Natarajan, Thomas Vidick +2 more

Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as $\mathsf{MIP} = \mathsf{NEXP}$ [BFL91] and the PCP theorem [AS98,ALM+98]. Over the last ten years, versions of these tests which are sound against quantum provers have found increasing applications to the study of nonlocal games and the complexity class~$\mathsf{MIP}^*$. The culmination of this line of work is the result $\mathsf{MIP}^* = \mathsf{RE}$ [arXiv:2001.04383]. One of the key ingredients in the first reported proof of $\mathsf{MIP}^* = \mathsf{RE}$ is a two-prover variant of the low degree test, initially shown to be sound against multiple quantum provers in [arXiv:1302.1242]. Unfortunately a mistake was recently discovered in the latter result, invalidating the main result of [arXiv:1302.1242] as well as its use in subsequent works, including [arXiv:2001.04383]. We analyze a variant of the low degree test called the low individual degree test. Our main result is that the two-player version of this test is sound against quantum provers. This soundness result is sufficient to re-derive several bounds on~$\mathsf{MIP}^*$ that relied on [arXiv:1302.1242], including $\mathsf{MIP}^* = \mathsf{RE}$.

arXiv:2009.12982•Sep 27, 2020•10 citations

The Computational Advantage of MIP* Vanishes in the Presence of Noise

Yangjing Dong, Honghao Fu, Anand Natarajan +3 more

The class MIP* of quantum multiprover interactive proof systems with entanglement is much more powerful than its classical counterpart MIP [ 8 , 31 , 32 ]: while MIP = NEXP, the quantum class MIP * is equal to RE, a class including the halting problem. This is because the provers in MIP * can share unbounded quantum entanglement. However, recent works [ 53 , 54 ] have shown that this advantage is significantly reduced if the provers’ shared state contains noise. This article attempts to exactly characterize the effect of noise on the computational power of quantum multiprover interactive proof systems. We investigate the quantum two-prover one-round interactive system MIP * [poly, O (1)], where the verifier sends polynomially many bits to the provers and the provers send back constantly many bits. We show that noise completely destroys the computational advantage given by shared entanglement in this model. Specifically, we show that if the provers are allowed to share arbitrarily many EPR states, where each EPR state is affected by an arbitrarily small constant amount of noise, the resulting complexity class is equivalent to NEXP = MIP. This improves significantly on the previous best-known bound of NEEEXP (nondeterministic triply exponential time) [ 53 ]. We also show that this collapse in power is due to noise, rather than the O (1) answer size, by showing that allowing for noiseless EPR states gives the class the full power of RE = MIP * [poly, poly]. Along the way, we develop two technical tools of independent interest. First, we give a new, deterministic tester for the positivity of an exponentially large matrix, provided that it has a low-degree Fourier decomposition in terms of Pauli matrices. Secondly, we develop a new invariance principle for smooth matrix functions having bounded third-order Fréchet derivatives or which are Lipschitz continuous.

arXiv:2312.04360•Journal of the ACM•Aug 16, 2025•4 citations

Devastating Effects of Quantum Noises and Noisy Quantum Operations on Entanglement and Quantum Information Protocols

Ye Yeo, Timothy C. Ralph, Ping Koy Lam

10.1063/1.3630152

AIP conference proceedings•Jan 1, 2011•0 citations

MIPco=coRE

J. F. Lin

In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen showed that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP* except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084]. We introduce a new equivalence condition for RE/coRE-complete problems, which we call the weakly compressible condition. We show that both MIP* and MIPco satisfy this condition through the compression theorem, and thereby establish that the uncomputability for MIP* and MIPco can be proved under a unified framework (despite these two complexity classes being different). Notably, this approach also gives an alternative proof of the MIP*=RE theorem, which does not rely on the preservation of the entanglement bound. In addition to non-local games, this new condition could also potentially be applicable to other decision problems.

arXiv:2510.07162•Oct 8, 2025•1 citation
A recent work studied quantum two-prover one-round proof systems MIPψ[poly,O(1)]\mathsf{MIP}^ψ[\text{poly},O(1)]MIPψ[poly,O(1)]. It showed that when ψψψ is a noisy EPR state with quantum maximal correlation ρmax⁡(ψ)<1ρ_{\max}(ψ)<1ρmax​(ψ)<1, the resulting complexity class is equivalent to NEXP=MIP\mathsf{NEXP}=\mathsf{MIP}NEXP=MIP. In contrast, MIPEPR[poly,O(1)]=RE\mathsf{MIP}^{\text{EPR}}[\text{poly},O(1)]=\mathsf{RE}MIPEPR[poly,O(1)]=RE. Not all noise, however, decreases quantum maximal correlation. A basic example is dephasing noise: a dephased EPR pair retain quantum maximal correlation 111. In this work, we remove the constant-answer restriction and establish a complete dichotomy for MIPψ[poly,poly]\mathsf{MIP}^ψ[\text{poly},\text{poly}]MIPψ[poly,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ρ_{\max}(ψ)<1ρmax​(ψ)<1};][\mathsf{MIP}^ψ[\text{poly},\text{poly}]=\mathsf{MIP}^ψ[\text{poly},O(1)]=\mathsf{RE},\text{if ψψψ is entangled and ρmax⁡(ψ)=1ρ_{\max}(ψ)=1ρ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.
This paper initiates the study of a class of entangled games, mono-state games, denoted by (G,ψ)(G,ψ)(G,ψ), where GGG is a two-player one-round game and ψψψ is a bipartite state independent of the game GGG. In the mono-state game (G,ψ)(G,ψ)(G,ψ), the players are only allowed to share arbitrary copies of ψψψ. This paper provides a doubly exponential upper bound on the copies of ψψψ for the players to approximate the value of the game to an arbitrarily small constant precision for any mono-state binary game (G,ψ)(G,ψ)(G,ψ), if ψψψ is a noisy EPR state, which is a two-qubit state with completely mixed states as marginals and maximal correlation less than 111. In particular, it includes (1−ε)∣Ψ⟩⟨Ψ∣+εI22⊗I22(1-ε)|Ψ\rangle\langleΨ|+ε\frac{I_2}{2}\otimes\frac{I_2}{2}(1−ε)∣Ψ⟩⟨Ψ∣+ε2I2​​⊗2I2​​, an EPR state with an arbitrary depolarizing noise ε>0ε>0ε>0.The structure of the proofs is built the recent framework about the decidability of the non-interactive simulation of joint distributions, which is completely different from all previous optimization-based approaches or "Tsirelson's problem"-based approaches. This paper develops a series of new techniques about the Fourier analysis on matrix spaces and proves a quantum invariance principle and a hypercontractive inequality of random operators. This novel approach provides a new angle to study the decidability of the complexity class MIP∗^*∗, a longstanding open problem in quantum complexity theory.
This paper considers a special class of nonlocal games (G,ψ)(G,\psi)(G,ψ), where GGG is a two-player one-round game, and ψ\psiψ is a bipartite state independent of GGG. In the game (G,ψ)(G,\psi)(G,ψ), the players are allowed to share arbitrarily many copies of ψ\psiψ. The value of the game (G,ψ)(G,\psi)(G,ψ), denoted by ω∗(G,ψ)\omega^*(G,\psi)ω∗(G,ψ), is the supremum of the winning probability that the players can achieve with arbitrarily many copies of preshared states ψ\psiψ. For a noisy maximally entangled state ψ\psiψ, a two-player one-round game GGG and an arbitrarily small precision ϵ>0\epsilon>0ϵ>0, this paper proves an upper bound on the number of copies of ψ\psiψ for the players to win the game with a probability ϵ\epsilonϵ close to ω∗(G,ψ)\omega^*(G,\psi)ω∗(G,ψ). A noisy maximally entangled state is a two-qudit state with both marginals being completely mixed states and the maximal correlation being less than 111. In particular, it includes $(1-\epsilon)|\Psi_m\rangle\langle\Psi_m|+\epsilon\frac{\mathbbm{1}_m}{m}\otimes\frac{\mathbbm{1}_m}{m}$ for ϵ>0\epsilon>0ϵ>0, where ∣Ψm⟩=1m∑i=0m−1∣m,m⟩|\Psi_m\rangle=\frac{1}{\sqrt{m}}\sum_{i=0}^{m-1}|m,m\rangle∣Ψm​⟩=m​1​∑i=0m−1​∣m,m⟩ is an mmm-dimensional maximally entangled state. Hence, it is feasible to approximately compute ω∗(G,ψ)\omega^*(G,\psi)ω∗(G,ψ) to an arbitrary precision. Recently, a breakthrough result by Ji et al. showed that it is undecidable to approximate the values of nonlocal games to a constant precision, when the players preshare arbitrarily many copies of perfect maximally entangled states, which implies that MIP∗=RE\mathrm{MIP}^*=\mathrm{RE}MIP∗=RE. In contrast, our result implies the hardness of approximating nonlocal games collapses when the preshared maximally entangled states are noisy. The paper develops a theory of Fourier analysis on matrix spaces by extending a number of techniques in Boolean analysis and Hermitian analysis to matrix spaces. We establish a series of new techniques, such as a quantum invariance principle and a hypercontractive inequality for random operators, which we believe have further applications. (A corrected version is attached.)
Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as MIP=NEXP\mathsf{MIP} = \mathsf{NEXP}MIP=NEXP [BFL91] and the PCP theorem [AS98,ALM+98]. Over the last ten years, versions of these tests which are sound against quantum provers have found increasing applications to the study of nonlocal games and the complexity class~MIP∗\mathsf{MIP}^*MIP∗. The culmination of this line of work is the result MIP∗=RE\mathsf{MIP}^* = \mathsf{RE}MIP∗=RE [arXiv:2001.04383]. One of the key ingredients in the first reported proof of MIP∗=RE\mathsf{MIP}^* = \mathsf{RE}MIP∗=RE is a two-prover variant of the low degree test, initially shown to be sound against multiple quantum provers in [arXiv:1302.1242]. Unfortunately a mistake was recently discovered in the latter result, invalidating the main result of [arXiv:1302.1242] as well as its use in subsequent works, including [arXiv:2001.04383]. We analyze a variant of the low degree test called the low individual degree test. Our main result is that the two-player version of this test is sound against quantum provers. This soundness result is sufficient to re-derive several bounds on~MIP∗\mathsf{MIP}^*MIP∗ that relied on [arXiv:1302.1242], including MIP∗=RE\mathsf{MIP}^* = \mathsf{RE}MIP∗=RE.
The class MIP* of quantum multiprover interactive proof systems with entanglement is much more powerful than its classical counterpart MIP [ 8 , 31 , 32 ]: while MIP = NEXP, the quantum class MIP * is equal to RE, a class including the halting problem. This is because the provers in MIP * can share unbounded quantum entanglement. However, recent works [ 53 , 54 ] have shown that this advantage is significantly reduced if the provers’ shared state contains noise. This article attempts to exactly characterize the effect of noise on the computational power of quantum multiprover interactive proof systems. We investigate the quantum two-prover one-round interactive system MIP * [poly, O (1)], where the verifier sends polynomially many bits to the provers and the provers send back constantly many bits. We show that noise completely destroys the computational advantage given by shared entanglement in this model. Specifically, we show that if the provers are allowed to share arbitrarily many EPR states, where each EPR state is affected by an arbitrarily small constant amount of noise, the resulting complexity class is equivalent to NEXP = MIP. This improves significantly on the previous best-known bound of NEEEXP (nondeterministic triply exponential time) [ 53 ]. We also show that this collapse in power is due to noise, rather than the O (1) answer size, by showing that allowing for noiseless EPR states gives the class the full power of RE = MIP * [poly, poly]. Along the way, we develop two technical tools of independent interest. First, we give a new, deterministic tester for the positivity of an exponentially large matrix, provided that it has a low-degree Fourier decomposition in terms of Pauli matrices. Secondly, we develop a new invariance principle for smooth matrix functions having bounded third-order Fréchet derivatives or which are Lipschitz continuous.
In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen showed that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP* except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084]. We introduce a new equivalence condition for RE/coRE-complete problems, which we call the weakly compressible condition. We show that both MIP* and MIPco satisfy this condition through the compression theorem, and thereby establish that the uncomputability for MIP* and MIPco can be proved under a unified framework (despite these two complexity classes being different). Notably, this approach also gives an alternative proof of the MIP*=RE theorem, which does not rely on the preservation of the entanglement bound. In addition to non-local games, this new condition could also potentially be applicable to other decision problems.