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:1012.5043 · Theory of Computing

Near-Optimal and Explicit Bell Inequality Violations

Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf

Published Jan 1, 2012• 18 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4086/toc.2012.v008a027

Related papers

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•47 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

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

Bell Violations through Independent Bases Games

Oded Regev

In a recent paper, Junge and Palazuelos presented two two-player games exhibiting interesting properties. In their first game, entangled players can perform notably better than classical players. The quantitative gap between the two cases is remarkably large, especially as a function of the number of inputs to the players. In their second game, entangled players can perform notably better than players that are restricted to using a maximally entangled state (of arbitrary dimension). This was the first game exhibiting such a behavior. The analysis of both games is heavily based on non-trivial results from Banach space theory and operator space theory. Here we present two games exhibiting a similar behavior, but with proofs that are arguably simpler, using elementary probabilistic techniques and standard quantum information arguments. Our games also give better quantitative bounds.

arXiv:1101.0576•Jan 3, 2011•4 citations

Bell violations through independent bases games

Oded Regev

In a recent paper, Junge and Palazuelos presented two two-player games exhibiting interesting properties. In their first game, entangled players can perform notably better than classical players. The quantitative gap between the two cases is remarkably large, especially as a function of the number of inputs to the players. In their second game, entangled players can perform notably better than players that are restricted to using a maximally entangled state (of arbitrary dimension). This was the first game exhibiting such a behavior. The analysis of both games is heavily based on non-trivial results from Banach space theory and operator space theory. Here we provide alternative proofs of these two results. Our proofs are arguably simpler, use elementary probabilistic techniques and standard quantum information arguments, and also give better quantitative bounds.

Quantum Information and Computation•Jan 1, 2012•20 citations

Violations of Bell inequalities as lower bounds on the communication cost of nonlocal correlations

Stefano Pironio

To reproduce in a local hidden variables theory correlations that violate Bell inequalities, communication must occur between the parties. We show that the amount of violation of a Bell inequality imposes a lower bound on the average communication needed to produce these correlations. Moreover, for every probability distribution there exists an optimal inequality for which the degree of violation gives the minimal average communication. As an example, to produce using classical resources the correlations that maximally violate the Clauser-Horne-Shimony-Holt inequality, $\sqrt{2}\ensuremath{-}1\ensuremath{\simeq}0.4142$ bits of communication are necessary and sufficient. For Bell tests performed on two entangled states of dimension $d>~3$ where each party has the choice between two measurements, our results suggest that more communication is needed to simulate outcomes obtained from certain nonmaximally entangled states than maximally entangled ones.

arXiv:quant-ph/0304176•Physical Review A•Dec 4, 2003•70 citations
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.
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.
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).
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​.
In a recent paper, Junge and Palazuelos presented two two-player games exhibiting interesting properties. In their first game, entangled players can perform notably better than classical players. The quantitative gap between the two cases is remarkably large, especially as a function of the number of inputs to the players. In their second game, entangled players can perform notably better than players that are restricted to using a maximally entangled state (of arbitrary dimension). This was the first game exhibiting such a behavior. The analysis of both games is heavily based on non-trivial results from Banach space theory and operator space theory. Here we present two games exhibiting a similar behavior, but with proofs that are arguably simpler, using elementary probabilistic techniques and standard quantum information arguments. Our games also give better quantitative bounds.
In a recent paper, Junge and Palazuelos presented two two-player games exhibiting interesting properties. In their first game, entangled players can perform notably better than classical players. The quantitative gap between the two cases is remarkably large, especially as a function of the number of inputs to the players. In their second game, entangled players can perform notably better than players that are restricted to using a maximally entangled state (of arbitrary dimension). This was the first game exhibiting such a behavior. The analysis of both games is heavily based on non-trivial results from Banach space theory and operator space theory. Here we provide alternative proofs of these two results. Our proofs are arguably simpler, use elementary probabilistic techniques and standard quantum information arguments, and also give better quantitative bounds.
To reproduce in a local hidden variables theory correlations that violate Bell inequalities, communication must occur between the parties. We show that the amount of violation of a Bell inequality imposes a lower bound on the average communication needed to produce these correlations. Moreover, for every probability distribution there exists an optimal inequality for which the degree of violation gives the minimal average communication. As an example, to produce using classical resources the correlations that maximally violate the Clauser-Horne-Shimony-Holt inequality, $\sqrt{2}\ensuremath{-}1\ensuremath{\simeq}0.4142$ bits of communication are necessary and sufficient. For Bell tests performed on two entangled states of dimension d> 3d>~3d> 3 where each party has the choice between two measurements, our results suggest that more communication is needed to simulate outcomes obtained from certain nonmaximally entangled states than maximally entangled ones.