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:2108.09140 · SIAM Journal on Computing

Nonlocal Games with Noisy Maximally Entangled States are Decidable

Minglong Qin, Penghui Yao

Published Jan 1, 2021• 13 citations
arXivHTMLPDF

Abstract

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.)

DOI
10.1137/20m134592x

Related papers

Decidability of Fully Quantum Nonlocal Games with Noisy Maximally Entangled States

Minglong Qin, Penghui Yao

This paper considers the decidability of fully quantum nonlocal games with noisy maximally entangled states. Fully quantum nonlocal games are a generalization of nonlocal games, where both questions and answers are quantum and the referee performs a binary POVM measurement to decide whether they win the game after receiving the quantum answers from the players. The quantum value of a fully quantum nonlocal game is the supremum of the probability that they win the game, where the supremum is taken over all the possible entangled states shared between the players and all the valid quantum operations performed by the players. The seminal work $$\text {MIP}^*=\text {RE}$$ ( Ji et al. MIP ∗ = RE, 2020; Ji et al. Quantum soundness of the classical low individual degree test, 2020) implies that it is undecidable to approximate the quantum value of a fully nonlocal game. This still holds even if the players are only allowed to share (arbitrarily many copies of) maximally entangled states. This paper investigates the case that the shared maximally entangled states are noisy. We prove that there is a computable upper bound on the copies of noisy maximally entangled states for the players to win a fully quantum nonlocal game with a probability arbitrarily close to the quantum value. This implies that it is decidable to approximate the quantum values of these games. Hence, the hardness of approximating the quantum value of a fully quantum nonlocal game is not robust against the noise in the shared states. This paper is built on the framework for the decidability of non-interactive simulations of joint distributions (Ghazi et al. in: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), Los Alamitos, 2016; De et al. in: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, 2018; Ghazi et al. Proceedings of the 33rd Computational Complexity Conference, 2018) and generalizes the analogous result for nonlocal games in Qin and Yao (SIAM J Comput 50(6):1800–1891, 2021). We extend the theory of Fourier analysis to the space of super-operators and prove several key results including an invariance principle and a dimension reduction for super-operators. These results are interesting in their own right and are believed to have further applications.

arXiv:2211.10613•Algorithmica•Aug 13, 2025•7 citations

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•4 citations

An explicit nonlocal game of quantum value one that needs exponential entanglement

Nidhal Mghirbi, Seth Douglas

How much entanglement does near-optimal play of a two-player nonlocal game require? We give an explicit binary linear system game, with $1687$ equations in $1993$ variables and at most three variables in each equation, whose quantum value is one, and in which every strategy that wins with probability $1-\varepsilon$ needs entanglement entropy $\varepsilon^{-1+o(1)}$, hence local dimension $\exp(\varepsilon^{-1+o(1)})$. The same bound holds for the entanglement of formation of mixed strategies, and a strategy on a maximally entangled state of local dimension $\exp(C\varepsilon^{-1}\log(1/\varepsilon))$ suffices, so the exponent is sharp. For explicit two-player games of quantum value one, the best previous lower bound was polynomial in $1/\varepsilon$. The game comes from a finitely generated, elementary amenable group: a lamplighter whose lamps are Pauli pairs indexed by finite sets of points on the three rays on which Houghton's group acts. Exponentially many of these pairs share one central involution, yet the relation that any two of them commute can be derived from a fixed finite set of relations in a number of steps only quasi-polynomial in the number of points. Two tools may be of independent use. The first counts qubits from approximate Pauli relations measured in an arbitrary state, with the errors of different pairs adding in squares. The second identifies, in both directions and at the natural precision $\sqrt\varepsilon$, the near-optimal strategies of a linear system game with approximate representations of its solution group measured in the players' actual state, so that no power of $\varepsilon$ is lost by passing to a flat state. The same tools give sharp rates for two earlier examples: the CHSH$(n)$ games need $\Theta(\min(n,1/\varepsilon))$ ebits, and the linear system game of Slofstra and Vidick needs local dimension $\Theta(\varepsilon^{-1/2})$.

•Oct 27, 2026•2 citations

Maximally entangled states are not complete for pseudo-telepathy

Olivier Lalonde

One of the longstanding open problems in quantum nonlocality is to determine if maximally entangled states are complete for bipartite pseudo-telepathic games: namely, if every nonlocal game which admits a perfect entangled strategy admits such a strategy which uses a maximally entangled state. We exhibit a counterexample to this in the form of a bipartite nonlocal game with input sets of size 4 and 3 and output sets both of size 6. This game is part of a new class of nonlocal games, which we call inner product games, which could be of independent interest.

quant-pharXiv:2608.05378•Aug 7, 2026•2 citations

A lower bound on the value of entangled binary games

Salman Beigi

A two-player one-round binary game consists of two cooperative players who each replies by one bit to a message that he receives privately; they win the game if both questions and answers satisfy some predetermined property. A game is called entangled if the players are allowed to share a priori entanglement. It is well-known that the maximum winning probability (value) of entangled XOR-games (binary games in which the predetermined property depends only on the XOR of the two output bits) can be computed by a semidefinite program. In this paper we extend this result in the following sense; if a binary game is uniform, meaning that in an optimal strategy the marginal distributions of the output of each player are uniform, then its entangled value can be efficiently computed by a semidefinite program. We also introduce a lower bound on the entangled value of a general two-player one-round game; this bound depends on the size of the output set of each player and can be computed by a semidefinite program. In particular, we show that if the game is binary, $\omega_q$ is its entangled value, and $\omega_{sdp}$ is the optimum value of the corresponding semidefinite program, then $0.68\,\omega_{sdp} < \omega_q \leq \omega_{sdp}$.

arXiv:0909.5518•Quantum Information and Computation•Nov 1, 2010•1 citation

Non-local games and communication complexity with noisy entanglement

Srijita Kundu, Olivier Lalonde

We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted communication complexity in a model where Alice and Bob may share arbitrarily many noisy EPR pairs. We study four noise models: depolarizing noise, unital noise, biased reset noise, and erasure noise. Our results are as follows: 1. We upper bound the value of the CHSH game under all these noise models in terms of the noise parameter, without any assumptions on the measurements used in the strategy. 2. We prove a parallel repetition theorem for general non-local games under all noise models except biased reset noise; we prove an improved parallel repetition theorem for unique games. Our parallel repetition rate is smaller than the quantum parallel repetition rate for CHSH in a nontrivial noise regime. 3. Using our unique-game parallel repetition theorem and a relation defined by the CHSH game, we prove a separation between communication complexity with noisy vs noiseless entanglement. This implies an $Ω(n)$ two-way communication lower bound for distilling $n$ EPR pairs from noisy EPR pairs, in the same nontrivial noise regime. 4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness. 5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication.

quant-pharXiv:2609.05122•Sep 7, 2026•2 citations
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−ϵ)∣Ψm⟩⟨Ψm∣+ϵ\mathbbm1mm⊗\mathbbm1mm(1-\epsilon)|\Psi_m\rangle\langle\Psi_m|+\epsilon\frac{\mathbbm{1}_m}{m}\otimes\frac{\mathbbm{1}_m}{m}(1−ϵ)∣Ψm​⟩⟨Ψm​∣+ϵm\mathbbm1m​​⊗m\mathbbm1m​​ 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.)
This paper considers the decidability of fully quantum nonlocal games with noisy maximally entangled states. Fully quantum nonlocal games are a generalization of nonlocal games, where both questions and answers are quantum and the referee performs a binary POVM measurement to decide whether they win the game after receiving the quantum answers from the players. The quantum value of a fully quantum nonlocal game is the supremum of the probability that they win the game, where the supremum is taken over all the possible entangled states shared between the players and all the valid quantum operations performed by the players. The seminal work MIP∗=RE\text {MIP}^*=\text {RE}MIP∗=RE ( Ji et al. MIP ∗ = RE, 2020; Ji et al. Quantum soundness of the classical low individual degree test, 2020) implies that it is undecidable to approximate the quantum value of a fully nonlocal game. This still holds even if the players are only allowed to share (arbitrarily many copies of) maximally entangled states. This paper investigates the case that the shared maximally entangled states are noisy. We prove that there is a computable upper bound on the copies of noisy maximally entangled states for the players to win a fully quantum nonlocal game with a probability arbitrarily close to the quantum value. This implies that it is decidable to approximate the quantum values of these games. Hence, the hardness of approximating the quantum value of a fully quantum nonlocal game is not robust against the noise in the shared states. This paper is built on the framework for the decidability of non-interactive simulations of joint distributions (Ghazi et al. in: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), Los Alamitos, 2016; De et al. in: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, 2018; Ghazi et al. Proceedings of the 33rd Computational Complexity Conference, 2018) and generalizes the analogous result for nonlocal games in Qin and Yao (SIAM J Comput 50(6):1800–1891, 2021). We extend the theory of Fourier analysis to the space of super-operators and prove several key results including an invariance principle and a dimension reduction for super-operators. These results are interesting in their own right and are believed to have further applications.
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.
How much entanglement does near-optimal play of a two-player nonlocal game require? We give an explicit binary linear system game, with 168716871687 equations in 199319931993 variables and at most three variables in each equation, whose quantum value is one, and in which every strategy that wins with probability 1−ε1-\varepsilon1−ε needs entanglement entropy ε−1+o(1)\varepsilon^{-1+o(1)}ε−1+o(1), hence local dimension exp⁡(ε−1+o(1))\exp(\varepsilon^{-1+o(1)})exp(ε−1+o(1)). The same bound holds for the entanglement of formation of mixed strategies, and a strategy on a maximally entangled state of local dimension exp⁡(Cε−1log⁡(1/ε))\exp(C\varepsilon^{-1}\log(1/\varepsilon))exp(Cε−1log(1/ε)) suffices, so the exponent is sharp. For explicit two-player games of quantum value one, the best previous lower bound was polynomial in 1/ε1/\varepsilon1/ε. The game comes from a finitely generated, elementary amenable group: a lamplighter whose lamps are Pauli pairs indexed by finite sets of points on the three rays on which Houghton's group acts. Exponentially many of these pairs share one central involution, yet the relation that any two of them commute can be derived from a fixed finite set of relations in a number of steps only quasi-polynomial in the number of points. Two tools may be of independent use. The first counts qubits from approximate Pauli relations measured in an arbitrary state, with the errors of different pairs adding in squares. The second identifies, in both directions and at the natural precision ε\sqrt\varepsilonε​, the near-optimal strategies of a linear system game with approximate representations of its solution group measured in the players' actual state, so that no power of ε\varepsilonε is lost by passing to a flat state. The same tools give sharp rates for two earlier examples: the CHSH(n)(n)(n) games need Θ(min⁡(n,1/ε))\Theta(\min(n,1/\varepsilon))Θ(min(n,1/ε)) ebits, and the linear system game of Slofstra and Vidick needs local dimension Θ(ε−1/2)\Theta(\varepsilon^{-1/2})Θ(ε−1/2).
One of the longstanding open problems in quantum nonlocality is to determine if maximally entangled states are complete for bipartite pseudo-telepathic games: namely, if every nonlocal game which admits a perfect entangled strategy admits such a strategy which uses a maximally entangled state. We exhibit a counterexample to this in the form of a bipartite nonlocal game with input sets of size 4 and 3 and output sets both of size 6. This game is part of a new class of nonlocal games, which we call inner product games, which could be of independent interest.
A two-player one-round binary game consists of two cooperative players who each replies by one bit to a message that he receives privately; they win the game if both questions and answers satisfy some predetermined property. A game is called entangled if the players are allowed to share a priori entanglement. It is well-known that the maximum winning probability (value) of entangled XOR-games (binary games in which the predetermined property depends only on the XOR of the two output bits) can be computed by a semidefinite program. In this paper we extend this result in the following sense; if a binary game is uniform, meaning that in an optimal strategy the marginal distributions of the output of each player are uniform, then its entangled value can be efficiently computed by a semidefinite program. We also introduce a lower bound on the entangled value of a general two-player one-round game; this bound depends on the size of the output set of each player and can be computed by a semidefinite program. In particular, we show that if the game is binary, ωq\omega_qωq​ is its entangled value, and ωsdp\omega_{sdp}ωsdp​ is the optimum value of the corresponding semidefinite program, then 0.68 ωsdp<ωq≤ωsdp0.68\,\omega_{sdp} < \omega_q \leq \omega_{sdp}0.68ωsdp​<ωq​≤ωsdp​.
We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted communication complexity in a model where Alice and Bob may share arbitrarily many noisy EPR pairs. We study four noise models: depolarizing noise, unital noise, biased reset noise, and erasure noise. Our results are as follows: 1. We upper bound the value of the CHSH game under all these noise models in terms of the noise parameter, without any assumptions on the measurements used in the strategy. 2. We prove a parallel repetition theorem for general non-local games under all noise models except biased reset noise; we prove an improved parallel repetition theorem for unique games. Our parallel repetition rate is smaller than the quantum parallel repetition rate for CHSH in a nontrivial noise regime. 3. Using our unique-game parallel repetition theorem and a relation defined by the CHSH game, we prove a separation between communication complexity with noisy vs noiseless entanglement. This implies an Ω(n)Ω(n)Ω(n) two-way communication lower bound for distilling nnn EPR pairs from noisy EPR pairs, in the same nontrivial noise regime. 4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness. 5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication.