Source-linked AI summary
Near-Optimal and Explicit Bell Inequality Violations
Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf
TL;DR
The paper studies how strongly entangled quantum correlations in two-player games can exceed classical strategies. It presents two fully explicit games, achieving strong Bell inequality violations through Hidden Matching and Unique Games constructions, with near-linear performance that is almost optimal under the stated measures.
Problem
The paper asks how much correlations from entangled quantum systems can exceed the winning probabilities achievable by classical strategies in two-player games.
Source: §1 · p. 2Method
The authors construct two explicit games inspired by Hidden Matching and Unique Games, analyzing their entangled and classical values using communication-complexity and quantum-rounding techniques.
Source: §1 · p. 3, §1.1 · p. 4Results
The first game has Bell violation √n/logn and can be won with certainty using entanglement, while the second reaches n/(logn)^2, almost optimal up to a polylogarithmic factor.
Source: §1 · p. 3Takeaways & Limitations
The constructions provide fully explicit strong Bell inequality violations, with the stronger game achieving near-linear violation in the number of outputs and entanglement dimension.
Source: §1 · p. 3The stronger KV game has entangled success probability 1/(logn)^2, which is low enough that experimental false positives may obscure it and require about (logn)^2 repetitions.
Source: §1.3 · p. 6
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces two fully explicit two-player games exhibiting strong Bell inequality violations, combining quantum nonlocality with ideas from communication complexity and Unique Games. The Hidden Matching game supports certainty with entanglement, while the Khot–Vishnoi game achieves a near-linear violation that is nearly optimal.
1 Introduction
- Entangled strategies use shared states and local measurements without communication, and their advantage is quantified by comparing entangled and classical winning probabilities.The entangled value is the supremum over such strategies, while the classical value restricts players to non-entangled strategies.Source: §1 · pp. 2–3
- The paper gives two fully explicit games with strong Bell inequality violations, improving earlier probabilistic constructions while using ideas from communication complexity and Unique Games.Earlier constructions established strong violations but were probabilistic and mathematically less accessible.Source: §1 · p. 3
1.1 The Hidden Matching game
- The Hidden Matching analysis uses the KKL inequality to show that short messages cannot predict many matching-edge parities, yielding an explicit violation of Ω(√n/logn).The game has n possible outputs for each player, and its violation matches the order achieved by earlier work.Source: §1.1 · pp. 4–5
- The Hidden Matching game achieves certainty with logn EPR-pairs, while every classical strategy differs from probability 1/2 by at most O((logn)/√n).The classical bound follows by reducing a non-local strategy to a logn-bit communication protocol and applying the Hidden Matching lower bound.Source: §1.1 · pp. 4–5
1.2 The Khot-Vishnoi game
- The Khot–Vishnoi construction refines and simplifies earlier quantum-rounding work, which produced n^ε violations with n possible outputs and n-dimensional entanglement.The paper argues that nearly optimal violations can be obtained using this method.Source: §1.2 · p. 5
- The Khot–Vishnoi game combines an integrality gap with quantum rounding: n-dimensional entanglement wins with probability Ω(1/(logn)^2), versus O(1/n) classically.Setting η = 1/2 − 1/logn gives the stated probabilities and an Ω(n/(logn)^2) Bell violation.Source: §1.2 · p. 6
- The Khot–Vishnoi violation is optimal up to polylogarithmic factors in both local entanglement dimension and the number of possible outputs.The game uses n-dimensional maximally entangled states and has n possible outputs per player.Source: §1.2 · pp. 5–6
1.3 Discussion and open problems
- Experimental assessment should consider absolute winning probabilities: Khot–Vishnoi’s entangled probability is 1/(logn)^2, whereas Hidden Matching can be won with certainty.The paper also leaves open whether the Khot–Vishnoi violation can approach the O(n) upper bound and whether strong violations are possible with linear input sets.Source: §1.3 · pp. 6–7
2 Preliminaries
Fourier analysis supplies the technical tools, while the formal Bell-inequality framework connects games, strategies, values, and bias-based violations.
2.1 Fourier analysis
- Fourier analysis on the Boolean cube uses parity characters as an orthonormal basis and Fourier coefficients to represent functions.The noise operator adds independent bit noise, acts diagonally in the Fourier basis, and contracts L_p norms; hypercontractivity implies the KKL inequality.Source: §2.1 · pp. 7–8
- The Bonami-Beckner hypercontractive inequality states an L_p-to-L_q norm bound under the condition ρ^2 ≤ (p−1)/(q−1).The KKL inequality is identified as an important consequence of hypercontractivity.Source: §2.1 · p. 8
2.2 A more formal look at Bell violations
- For a game, the Bell functional encodes input distributions and output-acceptance probabilities, and its classical and entangled values optimize the resulting functional.The formal definitions coincide with the game-value definitions when the functional comes from a game.Source: §2.2 · p. 9
- A Bell inequality is an upper bound on the classical value of a Bell functional, while its violation is the ratio of entangled to classical values.Restricting entangled states to local dimension n yields the corresponding dimension-limited value.Source: §2.2 · p. 9
- Bias-based violations around a center p equal the ratio between the entangled and classical deviations from that center.Subtracting p from each acceptance coefficient converts winning probabilities into biases while preserving the relevant ratio.Source: §2.2 · p. 10
3 Hidden Matching game
The Hidden Matching game converts a quantum communication advantage into a nonlocal game: maximally entangled players win with certainty, while classical strategies remain close to random guessing.
3.1 The Hidden Matching problem in communication complexity
- The Hidden Matching problem gives Alice x and Bob a uniformly random perfect matching, and Bob must output a matched pair and its parity.The communication version permits one-way communication from Alice to Bob, while the nonlocal version removes communication.Source: §3.1 · p. 10, §3 · p. 10
- 1 is achievable with logn qubits of one-way communication in the communication version of Hidden Matching.The quantum protocol always outputs the correct parity for Bob’s selected matched pair.Source: §3.1 · pp. 10–11
3.1.1 Limits of classical protocols for HMn
- For every n that is a power of 2 and positive integer c ≤√n, a classical c-bit protocol for HMn wins with probability 1/2+Ω(c/√n).Source: §3.2 · pp. 13–14
3.3 Entangled value for HMNL
- For HM_n, an n-dimensional maximally entangled strategy wins with certainty, while classical winning probability differs from 1/2 by at most O((logn)/√n).Source: §3.3 · pp. 14–15, §3.4 · p. 15
3.4 Classical value for HMNL
- The nonlocal classical value is bounded by 1/2±O((logn)/√n), using a reduction from a nonlocal strategy to a logn-bit communication protocol.An alternative strategy achieves a weaker Ω(1/√n) advantage, and the appendix gives its first-principles analysis.Source: §3.4 · p. 15
4 The Khot-Vishnoi game
The Khot–Vishnoi game uses noisy coset inputs to separate classical and entangled strategies. Hypercontractivity bounds classical success, while quantum rounding with n-dimensional entanglement yields a much larger winning probability.
4.1 The classical value
- A natural classical strategy selects the highest-Hamming-weight element in each coset, with heuristic success approximately 1/n^η/(1−η).The paper presents this calculation for intuition before proving the matching upper bound rigorously.Source: §4.1 · p. 17
- 1/n^η/(1−η) is an upper bound on every classical strategy’s winning probability in the Khot–Vishnoi game.The proof applies hypercontractivity to functions selecting one element from each coset.Source: §4.1 · pp. 16–17
4.2 Lower bound on the entangled value
- (1−2η)^2 is achievable by an entangled strategy using a maximally entangled state of local dimension n.Players measure in orthonormal bases indexed by their input cosets, following quantum rounding ideas of Kempe, Regev, and Toner.Source: §4.2 · pp. 18–19
5 Appendix: An alternative strategy for HMNL
The appendix gives an alternative Hidden Matching strategy based on shared random geometric tests. Its advantage is Ω(1/√n), slightly weaker than the main strategy’s bound.
5 Appendix: An alternative strategy for HMNL
- The alternative HMNL strategy achieves an Ω(1/√n) advantage over random guessing.The players use a shared random unit vector, output a fixed matched pair, and correlate their outputs through inner-product signs.Source: §5 · p. 19