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

DOI10.1007/S00220-012-1642-5MaRDI QIDQ356692zbMATH OpenOpenAlexWikidataFDO

Authors Jop Briët, Thomas Vidick

Publication date 26 July 2013

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

Full work available at URL https://arxiv.org/abs/1108.5647, https://authors.library.caltech.edu/65493/

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)

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.

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

Cites work

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

Cited in

(35)

• Information causality, Szemerédi-Trotter and algebraic variants of \textsf{CHSH} (extended abtract)
• 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
• scientific article; zbMATH DE number 7559053 (Why is no real title available?)
• 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
• Graph-theoretical bounds on the entangled value of non-local games
• 3XOR games with perfect commuting operator strategies have perfect tensor product strategies and are decidable in polynomial time
• 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
• Quantum query algorithms are completely bounded forms
• New concise upper bounds on quantum violation of general multipartite Bell inequalities
• 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 strategies for simple two-player XOR games
• Quantum one-way versus classical two-way communication in XOR games
• Quantum query algorithms are completely bounded forms
• 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
• scientific article; zbMATH DE number 7559121 (Why is no real title available?)

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)