Lower bounds on the entanglement needed to play XOR non-local games

Abstract

We give an explicit family of XOR games with O(n)-bit questions requiring 2^n ebits to play near-optimally. More generally we introduce a new technique for proving lower bounds on the amount of entanglement required by an XOR game: we show that near-optimal strategies for an XOR game G correspond to approximate representations of a certain C^*-algebra associated to G. Our results extend an earlier theorem of Tsirelson characterising the set of quantum strategies which implement extremal quantum correlations.

20 pages, no figures. Corrected abstract, body of paper unchanged

References in corpus (4)

• Testing the Hilbert space dimension
• Large violation of Bell inequalities with low entanglement
• Unbounded violation of tripartite Bell inequalities
• A generalized Grothendieck inequality and entanglement in XOR games

Cited by in corpus (24)

• Self-testing of quantum systems: a review
• Geometry of the set of quantum correlations
• Analytic and nearly optimal self-testing bounds for the Clauser-Horne-Shimony-Holt and Mermin inequalities
• Self-testing of binary observables based on commutation
• Entropic uncertainty from effective anti-commutators
• Survey on Nonlocal Games and Operator Space Theory
• Quantum Proofs
• Experimentally Robust Self-testing for Bipartite and Tripartite Entangled States
• Binary Constraint System Games and Locally Commutative Reductions
• Matrices with high completely positive semidefinite rank
• A two-player dimension witness based on embezzlement, and an elementary proof of the non-closure of the set of quantum correlations
• Entanglement in non-local games and the hyperlinear profile of groups
• Complexity of causal order structure in distributed quantum information processing and its trade-off with entanglement
• Trade-offs in multi-party Bell inequality violations in qubit networks
• Completely positive semidefinite rank
• A generalization of CHSH and the algebraic structure of optimal strategies
• A three-player coherent state embezzlement game
• Correlation matrices, Clifford algebras, and completely positive semidefinite rank
• Quantum advantage in temporally flat measurement-based quantum computation
• Self-testing in a constrained prepare-measure scenario sans assuming quantum dimension
• The membership problem for constant-sized quantum correlations is undecidable
• Counterexamples in self-testing
• Bounding conditional entropy of bipartite states with Bell operators
• The structure of optimal and nearly-optimal quantum strategies for non-local XOR games