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

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

Seth Douglas, Nidhal Mghirbi

Published Oct 27, 2026• 2 citations
Publisher

Abstract

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.

DOI
10.5281/zenodo.23697345

Related papers

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•1 citation

The price of unreachable perfection: dimension laws at every regular scale

Seth Douglas, Nidhal Mghirbi

How expensive is an optimum that a finite quantum system can approach but never attain? For a fixed finite rational nonlocal game of quantum value one, write A_G(n)=log2 D_G(2^(−n)), where D_G is the least local dimension at loss 2^(−n). We prescribe log2 A_G(n) at every logarithmic-space, nondecreasing unit-increment scale F with F(n)/log n → ∞, up to an additive O(log n+log²(F(n)+2)) error, and match the one-way distillable entanglement of the original mixed strategy state. At every asymptotically flat such scale, the positive finite lower and upper normalized dimension endpoints are exactly the ordered pairs with lower endpoint in Σ⁰₂ and upper endpoint in Π⁰₂; existing positive limits are exactly Δ⁰₂. A single uniform spectral-tail construction supplies the density-free profile law behind these results. It also classifies stretched-scale pairs in the unit square and gives quasi-polynomial dimension windows of width three in the exponent. A computable unit-increment target outside every rational game's profile shows that computability alone is insufficient. We locate the boundaries through a quantitative locality cap, an honest-linear compression cap, and an explicitly conditional route to finite exponents above one. A separate exact-marginal correlation theorem identifies a Farey law and its Diophantine endpoint curve. The dimension arithmetic necessity applies to all rational games; the operational realization statements concern the constructed games.

•Oct 29, 2026•0 citations

Perfect play in a binary-scoring nonlocal game requires infinite dimension but only finite energy

Seth Douglas, Nidhal Mghirbi

A finite rational binary-scoring game can require infinite dimension for perfect play while admitting finite energy and finite entanglement entropy. Our game has ten Alice questions, eleven Bob questions, at most six answers, and 52 uniform question pairs. It is spatially perfect and never finitely perfect, with sharp dimension profile $D_\Gamma(\varepsilon)=10\log_2(1/\varepsilon)+O(\log\log(1/\varepsilon))$. Among pure perfect strategies, the displayed strategy attains the least entanglement entropy, $5.362740278498934$ ebits, and least mean occupation, $275/18$ per oscillator. We classify all perfect normal type-I marginal spectra and prove that this spectrum is the unique majorization maximum. These constants are also the small-loss limits of the entropy and one-sided oscillator energy prices. In the massive free scalar field we construct a pure perfect state in two strictly separated bounded regions, equal to the vacuum outside a bounded containing region and with every polynomial energy moment finite. In contrast, every fixed faithful split state has a positive loss floor; the complementary-wedge vacuum has supremum one without attainment. Energy-analytic states, bounded-region invertible vacuum preparations and product-Kraus preparations cannot be perfect. Every perfect pure spatial strategy has infinite Schmidt rank; finite entropy is attained but not forced. In every type-II$_1$ factor the normalized trace has a loss floor, while bounded faithful prepared densities win perfectly with sharp trace-entropy deficit $\Delta_* = \ln(7/6)-\ln(2)/7$. Type-II$_\infty$ permits every finite trace entropy. A graded modular ladder gives a normal semifinite hosting criterion. Its scalar fingerprint has sharp capacity and entropy-gap bounds; the capacity floor is approached but not attained in type I, and attained in type II.

•Oct 29, 2026•2 citations

Beyond the Magic Square Game: Widening the Gap for Two Bell States

Tony Lau

Prior to this work, the largest known gap between the entangled value and the classical value for a one-round two-player nonlocal game with a perfect entangled strategy using two Bell states of entanglement was $\frac{1}{9}$, achieved by the Mermin-Peres magic square game. A larger gap of $\frac{2}{15}$ has been claimed for the related doily game of Kelleher, Roomy, and Holweck (Quant. Inf. Proc., 2024). However, this value assumes that the classical players use identical local strategies, and we show that dropping this assumption reduces the gap back to $\frac{1}{9}$. We then demonstrate that $\frac{1}{9}$ is not optimal by explicitly constructing a new nonlocal game with gap $\frac{4}{35}$.

quant-pharXiv:2603.20748•Mar 24, 2026•0 citations

Perfect play in a binary-scoring nonlocal game requires infinite dimension but only finite energy

Seth Douglas, Nidhal Mghirbi

A finite rational binary-scoring game can require infinite dimension for perfect play while admitting finite energy and finite entanglement entropy. Our game has ten Alice questions, eleven Bob questions, at most six answers, and 52 uniform question pairs. It is spatially perfect and never finitely perfect, with sharp dimension profile $D_\Gamma(\varepsilon)=10\log_2(1/\varepsilon)+O(\log\log(1/\varepsilon))$. Among pure perfect strategies, the displayed strategy attains the least entanglement entropy, $5.362740278498934$ ebits, and least mean occupation, $275/18$ per oscillator. We classify all perfect normal type-I marginal spectra and prove that this spectrum is the unique majorization maximum. These constants are also the small-loss limits of the entropy and one-sided oscillator energy prices. In the massive free scalar field we construct a pure perfect state in two strictly separated bounded regions, equal to the vacuum outside a bounded containing region and with every polynomial energy moment finite. In contrast, every fixed faithful split state has a positive loss floor; the complementary-wedge vacuum has supremum one without attainment. Energy-analytic states, bounded-region invertible vacuum preparations and product-Kraus preparations cannot be perfect. Every perfect pure spatial strategy has infinite Schmidt rank; finite entropy is attained but not forced. In every type-II$_1$ factor the normalized trace has a loss floor, while bounded faithful prepared densities win perfectly with sharp trace-entropy deficit $\Delta_* = \ln(7/6)-\ln(2)/7$. Type-II$_\infty$ permits every finite trace entropy. A graded modular ladder gives a normal semifinite hosting criterion. Its scalar fingerprint has sharp capacity and entropy-gap bounds; the capacity floor is approached but not attained in type I, and attained in type II.

•Oct 29, 2026•0 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•11 citations
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.
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).
How expensive is an optimum that a finite quantum system can approach but never attain? For a fixed finite rational nonlocal game of quantum value one, write A_G(n)=log2 D_G(2^(−n)), where D_G is the least local dimension at loss 2^(−n). We prescribe log2 A_G(n) at every logarithmic-space, nondecreasing unit-increment scale F with F(n)/log n → ∞, up to an additive O(log n+log²(F(n)+2)) error, and match the one-way distillable entanglement of the original mixed strategy state. At every asymptotically flat such scale, the positive finite lower and upper normalized dimension endpoints are exactly the ordered pairs with lower endpoint in Σ⁰₂ and upper endpoint in Π⁰₂; existing positive limits are exactly Δ⁰₂. A single uniform spectral-tail construction supplies the density-free profile law behind these results. It also classifies stretched-scale pairs in the unit square and gives quasi-polynomial dimension windows of width three in the exponent. A computable unit-increment target outside every rational game's profile shows that computability alone is insufficient. We locate the boundaries through a quantitative locality cap, an honest-linear compression cap, and an explicitly conditional route to finite exponents above one. A separate exact-marginal correlation theorem identifies a Farey law and its Diophantine endpoint curve. The dimension arithmetic necessity applies to all rational games; the operational realization statements concern the constructed games.
A finite rational binary-scoring game can require infinite dimension for perfect play while admitting finite energy and finite entanglement entropy. Our game has ten Alice questions, eleven Bob questions, at most six answers, and 52 uniform question pairs. It is spatially perfect and never finitely perfect, with sharp dimension profile DΓ(ε)=10log⁡2(1/ε)+O(log⁡log⁡(1/ε))D_\Gamma(\varepsilon)=10\log_2(1/\varepsilon)+O(\log\log(1/\varepsilon))DΓ​(ε)=10log2​(1/ε)+O(loglog(1/ε)). Among pure perfect strategies, the displayed strategy attains the least entanglement entropy, 5.3627402784989345.3627402784989345.362740278498934 ebits, and least mean occupation, 275/18275/18275/18 per oscillator. We classify all perfect normal type-I marginal spectra and prove that this spectrum is the unique majorization maximum. These constants are also the small-loss limits of the entropy and one-sided oscillator energy prices. In the massive free scalar field we construct a pure perfect state in two strictly separated bounded regions, equal to the vacuum outside a bounded containing region and with every polynomial energy moment finite. In contrast, every fixed faithful split state has a positive loss floor; the complementary-wedge vacuum has supremum one without attainment. Energy-analytic states, bounded-region invertible vacuum preparations and product-Kraus preparations cannot be perfect. Every perfect pure spatial strategy has infinite Schmidt rank; finite entropy is attained but not forced. In every type-II1_11​ factor the normalized trace has a loss floor, while bounded faithful prepared densities win perfectly with sharp trace-entropy deficit Δ∗=ln⁡(7/6)−ln⁡(2)/7\Delta_* = \ln(7/6)-\ln(2)/7Δ∗​=ln(7/6)−ln(2)/7. Type-II∞_\infty∞​ permits every finite trace entropy. A graded modular ladder gives a normal semifinite hosting criterion. Its scalar fingerprint has sharp capacity and entropy-gap bounds; the capacity floor is approached but not attained in type I, and attained in type II.
Prior to this work, the largest known gap between the entangled value and the classical value for a one-round two-player nonlocal game with a perfect entangled strategy using two Bell states of entanglement was 19\frac{1}{9}91​, achieved by the Mermin-Peres magic square game. A larger gap of 215\frac{2}{15}152​ has been claimed for the related doily game of Kelleher, Roomy, and Holweck (Quant. Inf. Proc., 2024). However, this value assumes that the classical players use identical local strategies, and we show that dropping this assumption reduces the gap back to 19\frac{1}{9}91​. We then demonstrate that 19\frac{1}{9}91​ is not optimal by explicitly constructing a new nonlocal game with gap 435\frac{4}{35}354​.
A finite rational binary-scoring game can require infinite dimension for perfect play while admitting finite energy and finite entanglement entropy. Our game has ten Alice questions, eleven Bob questions, at most six answers, and 52 uniform question pairs. It is spatially perfect and never finitely perfect, with sharp dimension profile DΓ(ε)=10log⁡2(1/ε)+O(log⁡log⁡(1/ε))D_\Gamma(\varepsilon)=10\log_2(1/\varepsilon)+O(\log\log(1/\varepsilon))DΓ​(ε)=10log2​(1/ε)+O(loglog(1/ε)). Among pure perfect strategies, the displayed strategy attains the least entanglement entropy, 5.3627402784989345.3627402784989345.362740278498934 ebits, and least mean occupation, 275/18275/18275/18 per oscillator. We classify all perfect normal type-I marginal spectra and prove that this spectrum is the unique majorization maximum. These constants are also the small-loss limits of the entropy and one-sided oscillator energy prices. In the massive free scalar field we construct a pure perfect state in two strictly separated bounded regions, equal to the vacuum outside a bounded containing region and with every polynomial energy moment finite. In contrast, every fixed faithful split state has a positive loss floor; the complementary-wedge vacuum has supremum one without attainment. Energy-analytic states, bounded-region invertible vacuum preparations and product-Kraus preparations cannot be perfect. Every perfect pure spatial strategy has infinite Schmidt rank; finite entropy is attained but not forced. In every type-II1_11​ factor the normalized trace has a loss floor, while bounded faithful prepared densities win perfectly with sharp trace-entropy deficit Δ∗=ln⁡(7/6)−ln⁡(2)/7\Delta_* = \ln(7/6)-\ln(2)/7Δ∗​=ln(7/6)−ln(2)/7. Type-II∞_\infty∞​ permits every finite trace entropy. A graded modular ladder gives a normal semifinite hosting criterion. Its scalar fingerprint has sharp capacity and entropy-gap bounds; the capacity floor is approached but not attained in type I, and attained in type II.
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.)