Universal gaps for XOR games from estimates on tensor norm ratios

Abstract

We define and study XOR games in the framework of general probabilistic theories, which encompasses all physical models whose predictive power obeys minimal requirements. The bias of an XOR game under local or global strategies is shown to be given by a certain injective or projective tensor norm, respectively. The intrinsic (i.e.\ model-independent) advantage of global over local strategies is thus connected to a universal function $r(n,m)$ called 'projective-injective ratio'. This is defined as the minimal constant $\rho$ such that $\Vert \cdot {\Vert }_{X{\otimes }_{\pi }Y}\le \rho \Vert \cdot {\Vert }_{X{\otimes }_{\epsilon }Y}$ holds for all Banach spaces of dimensions $\dim X=n$ and $\dim Y=m$, where $X{\otimes }_{\pi }Y$ and $X{\otimes }_{\epsilon }Y$ are the projective and injective tensor products. By requiring that $X=Y$, one obtains a symmetrised version of the above ratio, denoted by $r_s(n)$. We prove that $r(n,m)\ge 19/18$ for all $n,m\ge 2$, implying that injective and projective tensor products are never isometric. We then study the asymptotic behaviour of $r(n,m)$ and $r_s(n)$, showing that, up to log factors: $r_s(n)$ is of the order $\sqrt{n}$ (which is sharp); $r(n,n)$ is at least of the order $n^{1/6}$; and $r(n,m)$ grows at least as $\min \{n,m{\}}^{1/8}$. These results constitute our main contribution to the theory of tensor norms. In our proof, a crucial role is played by an '${\ell }_1$/${\ell }_2$/${\ell }_{\infty }$ trichotomy theorem' based on ideas by Pisier, Rudelson, Szarek, and Tomczak-Jaegermann. The main operational consequence we draw is that there is a universal gap between local and global strategies in general XOR games, and that this grows as a power of the minimal local dimension. In the quantum case, we are able to determine this gap up to universal constants. As a corollary, we obtain an improved bound on the scaling of the maximal quantum data hiding efficiency against local measurements.

arXiv comment45 pages, 2 figures; In v2 many auxiliary results have been improved substantially: Propositions 12-13 outline a connection with 1-summing norms; Lemma 18 now gives explicit constants; Eq. (75)-(76) contain new information about the 2-dimensional case

References in corpus (16)

• Non-local correlations as an information theoretic resource
• Quantum Theory From Five Reasonable Axioms
• A limit on nonlocality in any world in which communication complexity is not trivial
• A derivation of quantum theory from physical requirements
• A generalized no-broadcasting theorem
• All Entangled Quantum States Are Nonlocal
• No quantum advantage for nonlocal computation
• Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding
• Exponential Decay of Correlations Implies Area Law
• Higher-order interference and single-system postulates characterizing quantum theory
• Generalized Probabilistic Theories Without the No-Restriction Hypothesis
• Ultimate data hiding in quantum mechanics and beyond
• Survey on Nonlocal Games and Operator Space Theory
• Incompatible measurements in a class of general probabilistic theories
• Non-classical correlations in quantum mechanics and beyond
• On the nontrivial projection problem

Cited by in corpus (15)

• General Resource Theories in Quantum Mechanics and Beyond: Operational Characterization via Discrimination Tasks
• Entanglement and superposition are equivalent concepts in any physical theory
• Entangleability of cones
• Quantum data hiding with continuous variable systems
• Incompatibility in general probabilistic theories, generalized spectrahedra, and tensor norms
• Emergent classicality in general multipartite states and channels
• Dense Coding with Locality Restriction for Decoder: Quantum Encoders vs. Super-Quantum Encoders
• Perfect Discrimination in Approximate Quantum Theory of General Probabilistic Theories
• Pseudo standard entanglement structure cannot be distinguished from standard entanglement structure
• Refined diamond norm bounds on the emergence of objectivity of observables
• Maximal gap between local and global distinguishability of bipartite quantum states
• Assemblages and steering in general probabilistic theories
• Measurement incompatibility vs. Bell non-locality: an approach via tensor norms
• A Post-Quantum Associative Memory
• On the topology of some hyperspaces of convex bodies associated to tensor norms