Explicit lower and upper bounds on the entangled value of multiplayer XOR games

DOI10.1007/S00220-012-1642-5zbMATH Open1277.91028arXiv1108.5647OpenAlexW3099631965WikidataQ59792701 ScholiaQ59792701MaRDI QIDQ356692FDOQ356692

Authors: Jop Briët, Thomas Vidick 

Publication date: 26 July 2013

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

Abstract: XOR games are the simplest model in which the nonlocal properties of entanglement manifest themselves. When there are two players, it is well known that the bias --- the maximum advantage over random play --- of entangled players can be at most a constant times greater than that of classical players. Recently, P'{e}rez-Garc'{i}a et al. [Comm. Math. Phys. 279 (2), 2008] showed that no such bound holds when there are three or more players: the advantage of entangled players over classical players can become unbounded, and scale with the number of questions in the game. Their proof relies on non-trivial results from operator space theory, and gives a non-explicit existence proof, leading to a game with a very large number of questions and only a loose control over the local dimension of the players' shared entanglement. We give a new, simple and explicit (though still probabilistic) construction of a family of three-player XOR games which achieve a large quantum-classical gap (QC-gap). This QC-gap is exponentially larger than the one given by P'{e}rez-Garc'{i}a et. al. in terms of the size of the game, achieving a QC-gap of order $sqrtN$ with $N^2$ questions per player. In terms of the dimension of the entangled state required, we achieve the same (optimal) QC-gap of $sqrtN$ for a state of local dimension $N$ per player. Moreover, the optimal entangled strategy is very simple, involving observables defined by tensor products of the Pauli matrices. Additionally, we give the first upper bound on the maximal QC-gap in terms of the number of questions per player, showing that our construction is only quadratically off in that respect. Our results rely on probabilistic estimates on the norm of random matrices and higher-order tensors which may be of independent interest.

Full work available at URL: https://arxiv.org/abs/1108.5647

Recommendations

• A correlation-function Bell inequality with improved visibility for 3 qubits
• Near-optimal and explicit Bell inequality violations
• Monogamy of non-local quantum correlations
• Extreme quantum entanglement in a superposition of macroscopically distinct states
• Constructing quantum games from a system of Bell's inequalities
• Symmetries of the Bell correlation inequalities
• On the relation between Bell's inequalities and nonlocal games
• NOVEL BELL INEQUALITIES FOR n QUBITS DISTRIBUTED BETWEEN m < n PARTIES
• Tests of Bell inequalities

zbMATH Keywords

probabilistic methodentangled strategyfinite entanglementGrothendieck constantGrothendieck inequalityKhinchine inequalitymaximal QC-gapmultiplayer XOR gamesQC-gapunbounded gapsupper bound on quantum violation

Mathematics Subject Classification ID

Quantum coherence, entanglement, quantum correlations (81P40) (n)-person games, (n>2) (91A06) Games involving topology, set theory, or logic (91A44)

Cites Work

• Proposed experiment to test local hidden-variable theories
• Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
• Quantum analogues of the Bell inequalities. The case of two spatially separated domains
• Near-optimal and explicit Bell inequality violations
• Title not available (Why is that?)
• Extreme quantum entanglement in a superposition of macroscopically distinct states
• Grothendieck’s Theorem, past and present
• A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
• Invertibility of symmetric random matrices
• A new upper bound for the complex Grothendieck constant
• Title not available (Why is that?)
• Title not available (Why is that?)
• Estimates of moments and tails of Gaussian chaoses
• Title not available (Why is that?)
• Representations of function algebras, abstract operator spaces, and Banach space geometry
• Rank-one quantum games
• On the best constants in noncommutative Khintchine-type inequalities
• Unbounded violation of tripartite Bell inequalities
• Local quasi hidden variable modelling and violations of Bell-type inequalities by a multipartite quantum state
• Title not available (Why is that?)
• Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
• Unique games with entangled provers are easy
• The Grothendieck Constant is Strictly Smaller than Krivine's Bound
• Unbounded violations of bipartite Bell inequalities via operator space theory
• Large violation of Bell inequalities with low entanglement

Cited In (35)

• Universal gaps for XOR games from estimates on tensor norm ratios
• Specifying nonlocality of a pure bipartite state and analytical relations between measures for bipartite nonlocality and entanglement
• Title not available (Why is that?)
• Linear game non-contextuality and Bell inequalities -- a graph-theoretic approach
• Lower bounds on the entanglement needed to play XOR non-local games
• Quantum XOR games
• Polynomials in operator space theory
• 3XOR games with perfect commuting operator strategies have perfect tensor product strategies and are decidable in polynomial time
• Graph-theoretical bounds on the entangled value of non-local games
• Random constructions in Bell inequalities: a survey
• A lower bound on the value of entangled binary games
• Failure of the trilinear operator space Grothendieck theorem
• Hardness amplification for entangled games via anchoring
• Near-optimal and explicit Bell inequality violations
• Erratum to: ``Three-player entangled XOR games are NP-hard to approximate
• Provable Advantage for Quantum Strategies in Random Symmetric XOR Games
• Classical versus quantum communication in XOR games
• On the relation between completely bounded and \((1,{cb})\)-summing maps with applications to quantum XOR games
• New concise upper bounds on quantum violation of general multipartite Bell inequalities
• Quantum query algorithms are completely bounded forms
• On the power of quantum entanglement in multipartite quantum XOR games
• Quantum strategies are better than classical in almost any XOR game
• Communication and information complexity
• Nonlocal Quantum XOR Games for Large Number of Players
• Quantum query algorithms are completely bounded forms
• Quantum strategies for simple two-player XOR games
• Quantum one-way versus classical two-way communication in XOR games
• Survey on nonlocal games and operator space theory
• Reducing the number of questions in nonlocal games
• Three-player entangled XOR games are NP-hard to approximate
• Unbounded Bell violations for quantum genuine multipartite non-locality
• Small violations of Bell inequalities for multipartite pure random states
• Connes' embedding problem and winning strategies for quantum XOR games
• Title not available (Why is that?)
• Information causality, Szemerédi-Trotter and algebraic variants of \textsf{CHSH} (extended abtract)

This page was built for publication: Explicit lower and upper bounds on the entangled value of multiplayer XOR games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q356692)