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:1402.4145

Unbounded entanglement in nonlocal games

Laura Mančinska, Thomas Vidick

Published Feb 17, 2014• 0 citations
arXivHTMLPDF

Abstract

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\geq 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.

DOI
10.48550/arxiv.1402.4145

Related papers

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.

Quantum Information and Computation•Nov 1, 2015•0 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•1 citation

Entangled games do not require much entanglement (withdrawn)

Gus Gutoski

We prove an explicit upper bound on the amount of entanglement required by any strategy in a two-player cooperative game with classical questions and quantum answers. Specifically, we show that every strategy for a game with n-bit questions and n-qubit answers can be implemented exactly by players who share an entangled state of no more than 5n qubits--a bound which is optimal to within a factor of 5/2. Previously, no upper bound at all was known on the amount of entanglement required even to approximate such a strategy. It follows that the problem of computing the value of these games is in NP, whereas previously this problem was not known to be computable.

arXiv:0908.3491•Aug 24, 2009•0 citations

A three-player coherent state embezzlement game

Zhengfeng Ji, Debbie Leung, Thomas Vidick

We introduce a three-player nonlocal game, with a finite number of classical questions and answers, such that the optimal success probability of 1 in the game can only be achieved in the limit of strategies using arbitrarily high-dimensional entangled states. Precisely, there exists a constant 0

arXiv:1802.04926•Quantum•Oct 26, 2020•10 citations

Classical Interaction Cannot Replace Quantum Nonlocality

Gavinsky, Dmytro

We present a two-player communication task that can be solved by a protocol of polylogarithmic cost in the simultaneous message passing model with classical communication and shared entanglement, but requires exponentially more communication in the classical interactive model. Our second result is a two-player nonlocality game with input length $n$ and output of polylogarithmic length, that can be won with probability 1-o(1) by players sharing polylogarithmic amount of entanglement. On the other hand, the game is lost with probability $Ω(1)$ by players without entanglement, even if they are allowed to exchange up to k bits in interactive communication for certain $k\inΩ(n^{1/4})$. These two results give almost the strongest possible (and the strongest known) indication of nonlocal properties of two-party entanglement.

arXiv:0901.0956•Jan 8, 2009•11 citations

Bounding Quantum-Classical Separations for Classes of Nonlocal Games

Tom Bannink, Jop Briët, Harry Buhrman +2 more

We bound separations between the entangled and classical values for several classes of nonlocal $t$-player games. Our motivating question is whether there is a family of $t$-player XOR games for which the entangled bias is $1$ but for which the classical bias goes down to $0$, for fixed $t$. Answering this question would have important consequences in the study of multi-party communication complexity, as a positive answer would imply an unbounded separation between randomized communication complexity with and without entanglement. Our contribution to answering the question is identifying several general classes of games for which the classical bias can not go to zero when the entangled bias stays above a constant threshold. This rules out the possibility of using these games to answer our motivating question. A previously studied set of XOR games, known not to give a positive answer to the question, are those for which there is a quantum strategy that attains value 1 using a so-called Schmidt state. We generalize this class to mod-$m$ games and show that their classical value is always at least $\frac{1}{m} + \frac{m-1}{m} t^{1-t}$. Secondly, for free XOR games, in which the input distribution is of product form, we show $β(G) \geq β^*(G)^{2^t}$ where $β(G)$ and $β^*(G)$ are the classical and entangled biases of the game respectively. We also introduce so-called line games, an example of which is a slight modification of the Magic Square game, and show that they can not give a positive answer to the question either. Finally we look at two-player unique games and show that if the entangled value is $1-ε$ then the classical value is at least $1-\mathcal{O}(\sqrt{ε\log k})$ where $k$ is the number of outputs in the game. Our proofs use semidefinite-programming techniques, the Gowers inverse theorem and hypergraph norms.

arXiv:1811.11068•Leibniz international proceedings in informatics•Nov 27, 2018•2 citations
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 HHH, 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 ddd and succeed with probability 1−O(d−c)1-O(d^{-c})1−O(d−c) for some c≥0.13c\geq 0.13c≥0.13. On the other hand, we show that any strategy using an entangled state of local dimension ddd has success probability at most 1−Ω(d−2)1-Ω(d^{-2})1−Ω(d−2). In addition, we show that any strategy restricted to producing answers in a set of cardinality at most ddd has success probability at most 1−Ω(d−2)1-Ω(d^{-2})1−Ω(d−2). Finally, we generalize our construction to derive similar results starting from any game GGG with two questions per player and finite answers sets in which quantum strategies have an advantage.
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.
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).
We prove an explicit upper bound on the amount of entanglement required by any strategy in a two-player cooperative game with classical questions and quantum answers. Specifically, we show that every strategy for a game with n-bit questions and n-qubit answers can be implemented exactly by players who share an entangled state of no more than 5n qubits--a bound which is optimal to within a factor of 5/2. Previously, no upper bound at all was known on the amount of entanglement required even to approximate such a strategy. It follows that the problem of computing the value of these games is in NP, whereas previously this problem was not known to be computable.
We present a two-player communication task that can be solved by a protocol of polylogarithmic cost in the simultaneous message passing model with classical communication and shared entanglement, but requires exponentially more communication in the classical interactive model. Our second result is a two-player nonlocality game with input length nnn and output of polylogarithmic length, that can be won with probability 1-o(1) by players sharing polylogarithmic amount of entanglement. On the other hand, the game is lost with probability Ω(1)Ω(1)Ω(1) by players without entanglement, even if they are allowed to exchange up to k bits in interactive communication for certain k∈Ω(n1/4)k\inΩ(n^{1/4})k∈Ω(n1/4). These two results give almost the strongest possible (and the strongest known) indication of nonlocal properties of two-party entanglement.
We bound separations between the entangled and classical values for several classes of nonlocal ttt-player games. Our motivating question is whether there is a family of ttt-player XOR games for which the entangled bias is 111 but for which the classical bias goes down to 000, for fixed ttt. Answering this question would have important consequences in the study of multi-party communication complexity, as a positive answer would imply an unbounded separation between randomized communication complexity with and without entanglement. Our contribution to answering the question is identifying several general classes of games for which the classical bias can not go to zero when the entangled bias stays above a constant threshold. This rules out the possibility of using these games to answer our motivating question. A previously studied set of XOR games, known not to give a positive answer to the question, are those for which there is a quantum strategy that attains value 1 using a so-called Schmidt state. We generalize this class to mod-mmm games and show that their classical value is always at least 1m+m−1mt1−t\frac{1}{m} + \frac{m-1}{m} t^{1-t}m1​+mm−1​t1−t. Secondly, for free XOR games, in which the input distribution is of product form, we show β(G)≥β∗(G)2tβ(G) \geq β^*(G)^{2^t}β(G)≥β∗(G)2t where β(G)β(G)β(G) and β∗(G)β^*(G)β∗(G) are the classical and entangled biases of the game respectively. We also introduce so-called line games, an example of which is a slight modification of the Magic Square game, and show that they can not give a positive answer to the question either. Finally we look at two-player unique games and show that if the entangled value is 1−ε1-ε1−ε then the classical value is at least 1−O(εlog⁡k)1-\mathcal{O}(\sqrt{ε\log k})1−O(εlogk​) where kkk is the number of outputs in the game. Our proofs use semidefinite-programming techniques, the Gowers inverse theorem and hypergraph norms.