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

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

Nidhal Mghirbi, Seth Douglas

Published Oct 27, 2026• 2 citations
Publisher

Abstract

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

DOI
10.5281/zenodo.23697254

Related papers

The price of precision: usable entanglement in nonlocal games and the geometry of groups

Seth Douglas, Nidhal Mghirbi

In a nonlocal game of quantum value one that no finite-dimensional strategy wins, near-perfect play needs growing dimension, which separable states can have. We ask how much usable entanglement it needs: the demand at loss $\varepsilon$ is the least one-way distillable entanglement of the original state of a strategy of loss at most $\varepsilon$. For synchronous games with tested diagonals and for constraint-variable consistency games, demand diverges exactly when no finite-dimensional strategy is perfect; then, for any number of Bell pairs and any fidelity below one, every sufficiently good mixed strategy yields that many at that fidelity by local isometries. For rational synchronous or binary constraint games, a loss guaranteeing this is computable under a promise, but boundedness of demand is undecidable among games of value one. Demand is at least logarithmic if near-winners have a sign relation and an even dilation mirrored by both players, as in a game from Abels' group. For agreement games the directions agree up to a factor three in loss, optimal among Bob-fixed deterministic local symmetrizations. The geometry of the group behind a game, not its presentation, sets the rates. Fixed games demand $\alpha\log(1/\varepsilon)$ for every $\alpha=\frac12\sum_i\log_{m_i}q_i$ with $q_i\ge2$ a power of two dividing $m_i$, a dense set containing all positive rationals and some transcendentals, such as $\frac12\log_62$; a configuration-lamp game demands $\varepsilon^{-1+o(1)}$; Pauli lamps on the points of Houghton's three rays give demand between $\varepsilon^{-0.0690}$ and $\varepsilon^{-1/4}$. If group relations hold exactly and Alice matches Bob to error $e$, demand counts qubits addressable by short words: $\Theta(1/e)$, $\Theta(e^{-k})$ for integers $k\ge1$, or $2^{\Theta(1/e)}$. Conditional on our attainment and tail bounds, the $I_{3322}$ optimum needs bounded usable entanglement.

•Oct 27, 2026•3 citations

Near-Optimal and Explicit Bell Inequality Violations

Harry Buhrman, Oded Regev, Giannicola Scarpa +1 more

Entangled quantum systems can exhibit correlations that cannot be simulated classically. For historical reasons such correlations are called “Bell inequality violations.” We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work. The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a strategy using a maximally entangled state with local dimension $n$ (e.g., $\log n$ EPR-pairs), while we show that the winning probability of any classical strategy differs from $\frac{1}{2}$ by at most $O((\log n)/\sqrt{n})$. The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here $n$-dimensional entanglement allows the game to be won with probability $1/(\log n)^2$, while the best winning probability without entanglement is $1/n$. This near-linear ratio is almost optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players. An earlier version of this paper appeared in the Proceedings of the 26th IEEE Conference on Computational Complexity, pages 157--166, 2011.

arXiv:1012.5043•Theory of Computing•Jan 1, 2012•33 citations

Perfect play in a finite nonlocal game requires infinite entanglement entropy

Seth Douglas, Nidhal Mghirbi

How much infinity can a finite nonlocal game require? We construct a finite two-player game with classical questions, classical answers and a Boolean winning rule. It has a perfect strategy on a tensor product of separable Hilbert spaces. Every perfect normal spatial strategy contains, under local isometries, the same pure entangled state with infinite entropy. For mixed strategies, both marginal entropies are infinite and the pure state remains a tensor factor. Thus infinite dimension can be strengthened to infinite entropy without losing spatial attainment. The proof constructs a rational Bell functional whose perfect strategies contain a state with Catalan Schmidt multiplicities, and compiles it into Boolean tests. For either construction, the minimum marginal entropy at loss $\varepsilon$ is $\Theta(\log(1/\varepsilon))$. The lower bound holds for every normal spatial strategy, including mixed states and POVMs. It follows from polynomial decoding on the actual state and a finite-strip entropy estimate. Height and size cutoffs give the matching upper order. The sharp leading constant remains open.

•Nov 2, 2026•5 citations

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

Near-Optimal and Explicit Bell Inequality Violations

Harry Buhrman, Oded Regev, Giannicola Scarpa +1 more

Bell inequality violations correspond to behavior of entangled quantum systems that cannot be simulated classically. We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work.The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a quantum strategy using a maximally entangled state with local dimension n (e.g., log n EPR-pairs), while we show that the winning probability of any classical strategy differs from 1/2 by at most O(log n/√n).The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here n-dimensional entanglement allows to win the game with probability 1/(log n)2, while the best winning probability without entanglement is 1/n. This near-linear ratio ("Bell inequality violation'') is near-optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2011•48 citations

Unbounded entanglement in nonlocal games

Laura Mančinska, Thomas Vidick

Quantum entanglement is known to provide a strong advantage in many two-party distributed tasks. We investigate the question of how much entanglement is needed to reach optimal performance. For the first time we show that there exists a purely classical scenario for which no finite amount of entanglement suffices. To this end we introduce a simple two-party nonlocal game H, inspired by Lucien Hardy’s paradox. In our game each player has only two possible questions and can provide bit strings of any finite length as answer. We exhibit a sequence of strategies which use entangled states in increasing dimension d and succeed with probability 1 − O(d−c ) for some c ≥ 0.13. On the other hand, we show that any strategy using an entangled state of local dimension d has success probability at most 1 − Ω(d−2 ). In addition, we show that any strategy restricted to producing answers in a set of cardinality at most d has success probability at most 1 − Ω(d−2 ). Finally, we generalize our construction to derive similar results starting from any game G with two questions per player and finite answers sets in which quantum strategies have an advantage.

arXiv:1402.4145•Quantum Information and Computation•Nov 1, 2015•9 citations
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).
In a nonlocal game of quantum value one that no finite-dimensional strategy wins, near-perfect play needs growing dimension, which separable states can have. We ask how much usable entanglement it needs: the demand at loss ε\varepsilonε is the least one-way distillable entanglement of the original state of a strategy of loss at most ε\varepsilonε. For synchronous games with tested diagonals and for constraint-variable consistency games, demand diverges exactly when no finite-dimensional strategy is perfect; then, for any number of Bell pairs and any fidelity below one, every sufficiently good mixed strategy yields that many at that fidelity by local isometries. For rational synchronous or binary constraint games, a loss guaranteeing this is computable under a promise, but boundedness of demand is undecidable among games of value one. Demand is at least logarithmic if near-winners have a sign relation and an even dilation mirrored by both players, as in a game from Abels' group. For agreement games the directions agree up to a factor three in loss, optimal among Bob-fixed deterministic local symmetrizations. The geometry of the group behind a game, not its presentation, sets the rates. Fixed games demand αlog⁡(1/ε)\alpha\log(1/\varepsilon)αlog(1/ε) for every α=12∑ilog⁡miqi\alpha=\frac12\sum_i\log_{m_i}q_iα=21​∑i​logmi​​qi​ with qi≥2q_i\ge2qi​≥2 a power of two dividing mim_imi​, a dense set containing all positive rationals and some transcendentals, such as 12log⁡62\frac12\log_6221​log6​2; a configuration-lamp game demands ε−1+o(1)\varepsilon^{-1+o(1)}ε−1+o(1); Pauli lamps on the points of Houghton's three rays give demand between ε−0.0690\varepsilon^{-0.0690}ε−0.0690 and ε−1/4\varepsilon^{-1/4}ε−1/4. If group relations hold exactly and Alice matches Bob to error eee, demand counts qubits addressable by short words: Θ(1/e)\Theta(1/e)Θ(1/e), Θ(e−k)\Theta(e^{-k})Θ(e−k) for integers k≥1k\ge1k≥1, or 2Θ(1/e)2^{\Theta(1/e)}2Θ(1/e). Conditional on our attainment and tail bounds, the I3322I_{3322}I3322​ optimum needs bounded usable entanglement.
Entangled quantum systems can exhibit correlations that cannot be simulated classically. For historical reasons such correlations are called “Bell inequality violations.” We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work. The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a strategy using a maximally entangled state with local dimension nnn (e.g., log⁡n\log nlogn EPR-pairs), while we show that the winning probability of any classical strategy differs from 12\frac{1}{2}21​ by at most O((log⁡n)/n)O((\log n)/\sqrt{n})O((logn)/n​). The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here nnn-dimensional entanglement allows the game to be won with probability 1/(log⁡n)21/(\log n)^21/(logn)2, while the best winning probability without entanglement is 1/n1/n1/n. This near-linear ratio is almost optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players. An earlier version of this paper appeared in the Proceedings of the 26th IEEE Conference on Computational Complexity, pages 157--166, 2011.
How much infinity can a finite nonlocal game require? We construct a finite two-player game with classical questions, classical answers and a Boolean winning rule. It has a perfect strategy on a tensor product of separable Hilbert spaces. Every perfect normal spatial strategy contains, under local isometries, the same pure entangled state with infinite entropy. For mixed strategies, both marginal entropies are infinite and the pure state remains a tensor factor. Thus infinite dimension can be strengthened to infinite entropy without losing spatial attainment. The proof constructs a rational Bell functional whose perfect strategies contain a state with Catalan Schmidt multiplicities, and compiles it into Boolean tests. For either construction, the minimum marginal entropy at loss ε\varepsilonε is Θ(log⁡(1/ε))\Theta(\log(1/\varepsilon))Θ(log(1/ε)). The lower bound holds for every normal spatial strategy, including mixed states and POVMs. It follows from polynomial decoding on the actual state and a finite-strip entropy estimate. Height and size cutoffs give the matching upper order. The sharp leading constant remains open.
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.)
Bell inequality violations correspond to behavior of entangled quantum systems that cannot be simulated classically. We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work.The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a quantum strategy using a maximally entangled state with local dimension n (e.g., log n EPR-pairs), while we show that the winning probability of any classical strategy differs from 1/2 by at most O(log n/√n).The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here n-dimensional entanglement allows to win the game with probability 1/(log n)2, while the best winning probability without entanglement is 1/n. This near-linear ratio ("Bell inequality violation'') is near-optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players.
Quantum entanglement is known to provide a strong advantage in many two-party distributed tasks. We investigate the question of how much entanglement is needed to reach optimal performance. For the first time we show that there exists a purely classical scenario for which no finite amount of entanglement suffices. To this end we introduce a simple two-party nonlocal game H, inspired by Lucien Hardy’s paradox. In our game each player has only two possible questions and can provide bit strings of any finite length as answer. We exhibit a sequence of strategies which use entangled states in increasing dimension d and succeed with probability 1 − O(d−c ) for some c ≥ 0.13. On the other hand, we show that any strategy using an entangled state of local dimension d has success probability at most 1 − Ω(d−2 ). In addition, we show that any strategy restricted to producing answers in a set of cardinality at most d has success probability at most 1 − Ω(d−2 ). Finally, we generalize our construction to derive similar results starting from any game G with two questions per player and finite answers sets in which quantum strategies have an advantage.