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

Classical Interaction Cannot Replace Quantum Nonlocality

Gavinsky, Dmytro

Published Jan 8, 2009• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.0901.0956

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

arXiv:1402.4145•Feb 17, 2014•0 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.

Quantum Information and Computation•Nov 1, 2015•0 citations

Classical interaction cannot replace a quantum message

Dmitry Gavinsky

We demonstrate a two-player communication problem that can be solved in the one-way quantum model by a 0-error protocol of cost O(log n) but requires exponentially more communication in the classical interactive (bounded error) model.

arXiv:quant-ph/0703215•ACM Symposium on Theory of Computing (STOC)•May 17, 2008•20 citations

Classical vs. quantum communication in XOR games

Marius Junge, Carlos Palazuelos, Ignacio Villanueva

In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games $G$ when Alice and Bob are allowed to use a limited amount of one-way classical communication $ω_{o.w.-c}(G)$ (resp. one-way quantum communication $ω_{o.w.-c}^*(G)$), where $c$ denotes the number of bits (resp. qubits). The key quantity here is the quotient $ω_{o.w.-c}^*(G)/ω_{o.w.-c}(G)$. We provide a universal way to obtain Bell inequality violations of general Bell functionals from XOR games for which the quotient $ω_{o.w.-c}^*(G)/ω_{o.w.-2c}(G)$ is larger than 1. This allows, in particular, to find (unbounded) Bell inequality violations from communication complexity problems in the same spirit as the recent work by Buhrman et al. (2016). We also provide an example of a XOR game for which the previous quotient is optimal (up to a logarithmic factor) in terms of the amount of information $c$. Interestingly, this game has only polynomially many inputs per player. For the related problem of separating the classical vs quantum communication complexity of a function, the known examples attaining exponential separation require exponentially many inputs per party.

arXiv:1706.02653•Jun 8, 2017•0 citations

Consequences and Limits of Nonlocal Strategies

Richard Cleve, Peter Høyer, Benjamin Toner +1 more

This paper investigates various aspects of the nonlocal effects that can arise when entangled quantum information is shared between two parties. A natural framework for studying nonlocality is that of cooperative games with incomplete information, where two cooperating players may share entanglement. Here nonlocality can be quantified in terms of the values of such games. We review some examples of nonlocality and show that it can profoundly affect the soundness of two-prover interactive proof systems. We then establish limits on nonlocal behavior by upper-bounding the values of several of these games. These upper bounds can be regarded as generalizations of the so-called Tsirelson inequality. We also investigate the amount of entanglement required by optimal and nearly optimal quantum strategies. 1.

•Jan 1, 2004•304 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
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.
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.
In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games GGG when Alice and Bob are allowed to use a limited amount of one-way classical communication ωo.w.−c(G)ω_{o.w.-c}(G)ωo.w.−c​(G) (resp. one-way quantum communication ωo.w.−c∗(G)ω_{o.w.-c}^*(G)ωo.w.−c∗​(G)), where ccc denotes the number of bits (resp. qubits). The key quantity here is the quotient ωo.w.−c∗(G)/ωo.w.−c(G)ω_{o.w.-c}^*(G)/ω_{o.w.-c}(G)ωo.w.−c∗​(G)/ωo.w.−c​(G). We provide a universal way to obtain Bell inequality violations of general Bell functionals from XOR games for which the quotient ωo.w.−c∗(G)/ωo.w.−2c(G)ω_{o.w.-c}^*(G)/ω_{o.w.-2c}(G)ωo.w.−c∗​(G)/ωo.w.−2c​(G) is larger than 1. This allows, in particular, to find (unbounded) Bell inequality violations from communication complexity problems in the same spirit as the recent work by Buhrman et al. (2016). We also provide an example of a XOR game for which the previous quotient is optimal (up to a logarithmic factor) in terms of the amount of information ccc. Interestingly, this game has only polynomially many inputs per player. For the related problem of separating the classical vs quantum communication complexity of a function, the known examples attaining exponential separation require exponentially many inputs per party.
This paper investigates various aspects of the nonlocal effects that can arise when entangled quantum information is shared between two parties. A natural framework for studying nonlocality is that of cooperative games with incomplete information, where two cooperating players may share entanglement. Here nonlocality can be quantified in terms of the values of such games. We review some examples of nonlocality and show that it can profoundly affect the soundness of two-prover interactive proof systems. We then establish limits on nonlocal behavior by upper-bounding the values of several of these games. These upper bounds can be regarded as generalizations of the so-called Tsirelson inequality. We also investigate the amount of entanglement required by optimal and nearly optimal quantum strategies. 1.
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).