Theory of Computing
-------------------
Title     : Near-Optimal and Explicit Bell Inequality Violations
Authors   : Harry Buhrman, Oded Regev, Giannicola Scarpa, and Ronald de Wolf
Volume    : 8
Number    : 27
Pages     : 623-645
URL       : https://theoryofcomputing.org/articles/v008a027

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.