Near-Optimal and Explicit Bell Inequality Violations

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

Published in Theory of Computing, Volume 8 (2012), Article 27; Received: September 15, 2011, Revised: August 31, 2012, Published: December 27, 2012

References in corpus (3)

• Large violation of Bell inequalities with low entanglement
• Unbounded violation of tripartite Bell inequalities
• Super-activation of quantum non-locality

Cited by in corpus (12)

• Unbounded violation of quantum steering inequalities
• Survey on Nonlocal Games and Operator Space Theory
• Quantum steering inequality with tolerance for measurement-setting-errors: experimentally feasible signature of unbounded violation
• Asymptotic survival of genuine multipartite entanglement in noisy quantum networks depends on the topology
• Belief-Invariant and Quantum Equilibria in Games of Incomplete Information
• Robust Bell inequalities from communication complexity
• Reducing the number of inputs in nonlocal games
• On the tightness of correlation inequalities with no quantum violation
• Property RD and hypercontractivity for orthogonal free quantum groups
• Optimisation of Bell inequalities with invariant Tsirelson bound
• Bound on Bell Inequalities by Fraction of Determinism and Reverse Triangle Inequality
• Unbounded Bell violations for quantum genuine multipartite non-locality