Universal Gaps for XOR Games from Estimates on Tensor Norm Ratios

Thumbnail Image
Full text at PDC
Publication Date
Advisors (or tutors)
Journal Title
Journal ISSN
Volume Title
Google Scholar
Research Projects
Organizational Units
Journal Issue
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 ρ such that ∥⋅∥X⊗πY⩽ρ∥⋅∥X⊗εY holds for all Banach spaces of dimensions dimX=n and dimY=m, where X⊗πY and X⊗εY are the projective and injective tensor products. By requiring that X=Y, one obtains a symmetrised version of the above ratio, denoted by rs(n). We prove that r(n,m)⩾19/18 for all n,m⩾2, implying that injective and projective tensor products are never isometric. We then study the asymptotic behaviour of r(n, m) and rs(n), showing that, up to log factors: rs(n) is of the order n−−√ (which is sharp); r(n, n) is at least of the order n1/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 ‘ℓ1/ℓ2/ℓ∞ 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.
1. Bell, J.S.: On the Einstein–Podolsky–Rosen paradox. Physics 1(3), 195–200 (1964) 2. Hartkämper, A., Neumann, H.: Foundations of Quantum Mechanics and Ordered Linear Spaces: Advanced Study Institute held in Marburg 1973. Springer, Berlin (1974) 3. Barrett, J.: Information processing in generalized probabilistic theories. Phys. Rev. A 75(3), 032304 (2007) 4. Lami, L.: Non-classical correlations in quantum mechanics and beyond. Ph.D. thesis, Universitat Autònoma de Barcelona (2017). Preprint arXiv:1803.02902 5. Palazuelos, C., Vidick, T.: Survey on nonlocal games and operator space theory. J. Math. Phys. 57(1), 015220 (2016) 6. Tomczak-Jaegermann, N.: The weak distance between finite-dimensional Banach spaces. Math. Nachr. 119, 291–307 (1984) 7. Rudelson, M.: Estimates of the weak distance between finite-dimensional Banach spaces. Isr. J. Math. 89(1–3), 189–204 (1995) 8. Pisier, G.: Counterexamples to a conjecture of Grothendieck. Acta Math. 151(1), 181–208 (1983) 9. Segal, I.E.: Postulates for general quantum mechanics. Ann. Math. 48(4), 930–948 (1947) 10. Mackey, G.: Mathematical Foundations of Quantum Mechanics. Benjamin, New York (1963) 11. Ludwig, G.: Versuch einer axiomatischen Grundlegung der Quantenmechanik und allgemeinerer physikalischer Theorien. Z. Phys. 181(3), 233–260 (1964) 12. Ludwig, G.: An Axiomatic Basis for Quantum Mechanics: Derivation of Hilbert Space Structure, vol.1. Springer, Berlin (1985) 13. Ludwig, G.: Attempt of an axiomatic foundation of quantum mechanics and more general theories II. Commun. Math. Phys. 4(5), 331–348 (1967) 14. Ludwig, G.: Attempt of an axiomatic foundation of quantum mechanics and more general theories III. Commun. Math. Phys. 9(1), 1–12 (1968) 15. Dähn, G.: Attempt of an axiomatic foundation of quantum mechanics and more general theories IV. Commun. Math. Phys. 9(3), 192–211 (1968) 16. Stolz, P.: Attempt of an axiomatic foundation of quantum mechanics and more general theories V. Commun. Math. Phys. 11(4), 303–313 (1969) 17. Davies, E.B., Lewis, J.T.: An operational approach to quantum probability. Commun. Math. Phys. 17(3), 239–260 (1970) 18. Edwards, C.M.: The operational approach to algebraic quantum theory I. Commun. Math. Phys. 16(3), 207–230 (1970) 19. Hardy, L.: Quantum theory from five reasonable axioms (2001). Preprint arXiv:quant-ph/0101012 20. D’Ariano, G.M.: On the missing axiom of quantum mechanics. AIP Conf. Proc. 810(1), 114–130 (2006) 21. Wilce, A.: Four and a half axioms for finite-dimensional quantum probability. In: Ben-Menahem, Y., Hemmo, M. (eds.) Probability in Physics. Springer, pp. 281–298 (2012) 22. Masanes, L., Müller, M.P.: A derivation of quantum theory from physical requirements. New J. Phys. 13(6), 063001 (2011) 23. Barnum, H., Müller, M.P., Ududec, C.: Higher-order interference and single-system postulates charac- terizing quantum theory. New J. Phys. 16(12), 123029 (2014) 24. Popescu, S., Rohrlich, D.: Quantum nonlocality as an axiom. Found. Phys. 24(3), 379–385 (1994) 25. Barrett, J., Linden, N., Massar, S., Pironio, S., Popescu, S., Roberts, D.: Nonlocal correlations as an information-theoretic resource. Phys. Rev. A 71, 022101 (2005) 26. Brassard, G., Buhrman, H., Linden, N., Méthot, A.A., Tapp, A., Unger, F.: Limit on nonlocality in any world in which communication complexity is not trivial. Phys. Rev. Lett. 96, 250401 (2006) 27. Linden, N., Popescu, S., Short, A.J., Winter, A.: Quantum nonlocality and beyond: limits from nonlocal computation. Phys. Rev. Lett. 99, 180502 (2007) 28. Barnum, H., Barrett, J., Leifer, M., Wilce, A.: Generalized no-broadcasting theorem. Phys. Rev. Lett. 99(24), 240501 (2007) 29. Barnum, H., Gaebler, C.P., Wilce, A.: Ensemble steering, weak self-duality, and the structure of probabilistic theories. Found. Phys. 43(12), 1411–1427 (2009) 30. Barnum, H., Barrett, J., Leifer, M., Wilce, A.: Teleportation in general probabilistic theories. Proc. Sympos. Appl. Math. 71, 25–48 (2012) 31. Jenˇcová. Incompatible measurements in a class of general probabilistic theories. Phys. Rev. A 98, 012133 (2018) 32. Lami, L., Palazuelos, C., Winter, A.: Ultimate data hiding in quantum mechanics and beyond. Commun. Math. Phys. 361(2), 661–708 (2018) 33. Janotta, P., Lal, R.: Generalized probabilistic theories without the no-restriction hypothesis. Phys. Rev. A 87, 052131 (2013) 34. Ellis, A.J.: The duality of partially ordered normed linear spaces. J. Lond. Math. Soc. 1(1), 730–744 (1964) 35. Ellis, A.J.: Linear operators in partially ordered normed vector spaces. J. Lond. Math. Soc. 1(1), 323–332(1966) 36. Edwards, D.A.: On the homeomorphic affine embedding of a locally compact cone into a Banach dual space endowed with the vague topology. Proc. Lond. Math. Soc. 3(3), 399–414 (1964) 37. Boyd, S.P., Vandenberghe, L.: Convex Optimization. Berichte über verteilte Messysteme. Cambridge University Press, Cambridge (2004) 38. Kläy, M., Randall, C., Foulis, D.: Tensor products and probability weights. Int. J. Theor. Phys. 26(3),199–219 (1987) 39. Wilce, A.: Tensor products in generalized measure theory. Int. J. Theor. Phys. 31(11), 1915–1928 (1992) 40. Grothendieck, A.: Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. São Paulo 8, 1–79 (1953) 41. Defant, A., Floret, K.: Tensor Norms and Operator Ideals, vol. 176. Elsevier, Hoboken (1992) 42. Ryan, R.A.: Introduction to Tensor Products of Banach Spaces. Springer, Berlin (2013) 43. Cleve, R., Hoyer, P., Toner, B., Watrous, J.: Consequences and limits of nonlocal strategies. In: 19th IEEE Annual Conference on Computational Complexity, 2004. Proceedings, pp. 236–249. IEEE (2004) 44. Clauser, J.F., Horne, M.A., Shimony, A., Holt, R.A.: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 880–884 (1969) 45. Tsirel’son, B.S.: Quantum analogues of the Bell inequalities. The case of two spatially separated domains. J. Sov. Math. 36(4), 557–570 (1987) 46. Buscemi, F.: All entangled quantum states are nonlocal. Phys. Rev. Lett. 108, 200401 (2012) 47. Regev, O., Vidick, T.: Quantum XOR games. ACM Trans. Comput. Theory 7(4), 15:1–15:43 (2015) 48. Pisier, G.: Un théorème sur les opérateurs linéaires entre espaces de Banach qui se factorisent par un espace de Hilbert. Ann. Sci. École Norm. Sup. (4) 13(1), 23–43 (1980) 49. Bourgain, J., Milman, V.D.: Distances between normed spaces, their subspaces and quotient spaces. Integral Equ. Oper. Theory 9(1), 31–46 (1986) 50. Szarek, S.J., Tomczak-Jaegermann, N.: On the nontrivial projection problem. Adv. Math. 221(2), 331–342 (2009) 51. Brandão, F.G.S.L., Horodecki, M.: Exponential decay of correlations implies area law. Commun. Math. Phys. 333(2), 761–798 (2015) 52. Matthews, W., Wehner, S., Winter, A.: Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding. Commun. Math. Phys. 291(3), 813–843 (2009) 53. Tomczak-Jaegermann, N.: Banach–Mazur Distances and Finite-Dimensional Operator Ideals. Pitman Monographs and Surveys in Pure and Applied Mathematics, vol. 38. Longman Scientific & Technical, Harlow (1989). copublished in the United States with John Wiley & Sons, Inc., New York 54. Gluskin, E.D.: Diameter of the Minkowski compactum is approximately equal to n. Funct. Anal. Appl. 15(1), 57–58 (1981) 55. Stromquist, W.: The maximum distance between two-dimensional Banach spaces. Math. Scand. 48(2), 205–225 (1981) 56. Lindenstrauss, J., Tzafriri, L.: Classical Banach Spaces I and II, vol. 97. Springer, Berlin (1977) 57. Nordlander, G.: The modulus of convexity in normed linear spaces. Ark. Mat. 4(15–17), 1960 (1960) 58. Junge, M., Palazuelos, C., Villanueva, I.: Classical versus quantum communication in XOR games. Quantum Inf. Process. 17(5), 36 (2018). Art. 117 59. Pisier, G.: The Volume of Convex Bodies and Banach Space Geometry. Cambridge Tracts in Mathematics, vol. 94. Cambridge University Press, Cambridge (1989) 60. Aubrun, G., Szarek, S.J.: Alice and Bob Meet Banach. Mathematical Surveys and Monographs, vol. 223. American Mathematical Society, Providence (2017). The interface of asymptotic geometric analysis and quantum information theory 61. Latała, R., Oleszkiewicz, K.: Gaussian measures of dilatations of convex symmetric sets. Ann.Probab. 27(4), 1922–1938 (1999) 62. Ball, K.: An elementary introduction to modern convex geometry. In: Flavors of Geometry. Mathematical Sciences Research Institute Publications, vol. 31, pp. 1–58. Cambridge Univ. Press, Cambridge (1997) 63. Vershynin, R.: John’s decompositions: selecting a large part. Isr. J. Math. 122, 253–277 (2001) 64. Gordon, Y.: On p-absolutely summing constants of Banach spaces. Isr. J. Math. 7, 151–163 (1969) 65. König, H., Tomczak-Jaegermann, N.: Bounds for projection constants and 1-summing norms. Trans. Am. Math. Soc. 320(2), 799–823 (1990) 66. Grünbaum, B.: Projection constants. Trans. Am. Math. Soc. 95(3), 451–465 (1960) 67. Haagerup, U.: The Grothendieck inequality for bilinear forms on C∗-algebras. Adv. Math. 56(2), 93–116 (1985) 68. Pisier, G.: Grothendieck’s theorem for noncommutative C∗-algebras, with an appendix on Grothendieck’s constants. J. Funct. Anal. 29(3), 397–415 (1978)