Near-Optimal and Explicit Bell Inequality Violations

by Harry Buhrman, Oded Regev, Giannicola Scarpa, and Ronald de Wolf

Theory of Computing, Volume 8(27), pp. 623-645, 2012

Bibliography with links to cited articles

[1]   Ziv Bar-Yossef, T. S. Jayram, and Iordanis Kerenidis: Exponential separation of quantum and classical one-way communication complexity. SIAM J. Comput., 38(1):366–384, 2008. Preliminary version in STOC’04. [doi:10.1137/060651835]

[2]   John Stewart Bell: On the Einstein Podolsky Rosen paradox. Physics, 1:195–200, 1964.

[3]   Jop Briët, Harry Buhrman, Troy Lee, and Thomas Vidick: Multiplayer XOR games and quantum communication complexity with clique-wise entanglement. Quantum Inf. Comput., 2013. To appear. Preprint (2009) at arXiv.

[4]   Jop Briët and Thomas Vidick: Explicit lower and upper bounds on the entangled value of multiplayer XOR games. Communications in Mathematical Physics, 2013. To appear. Preprint (2011) at arXiv. [doi:10.1007/s00220-012-1642-5]

[5]   John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett., 23(15):880–884, 1969. [doi:10.1103/PhysRevLett.23.880]

[6]   Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay: Perfect parallel repetition theorem for quantum XOR proof systems. Comput. Complexity, 17(2):282–299, 2008. Preliminary version in CCC’07. [doi:10.1007/s00037-008-0250-4]

[7]   Julien Degorre, Marc Kaplan, Sophie Laplante, and Jérémie Roland: The communication complexity of non-signaling distributions. Quantum Inf. Comput., 11(7&8):649–676, 2011. Preliminary version in MFCS’09. Preprint (2008-11) at arXiv. [ACM:2230916.2230924]

[8]   Dejan D. Dukaric: The Hilbertian tensor norm and its connection to quantum information theory. 2010. [arXiv:1008.1948v2]

[9]   Albert Einstein, Boris Podolsky, and Nathan Rosen: Can quantum-mechanical description of physical reality be considered complete? Physical Review, 47(10):777–780, 1935. [doi:10.1103/PhysRev.47.777]

[10]   Dmitry Gavinsky: Classical interaction cannot replace quantum nonlocality. 2009. [arXiv:0901.0956]

[11]   Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf: Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput., 38(5):1695–1708, 2009. Preliminary version in STOC’07. [doi:10.1137/070706550]

[12]   Dmitry Gavinsky, Julia Kempe, Oded Regev, and Ronald de Wolf: Bounded-error quantum state identification and exponential separations in communication complexity. SIAM J. Comput., 39(1):1–24, 2009. Preliminary version in STOC’06. [doi:10.1137/060665798]

[13]   Marius Junge and Carlos Palazuelos: Large violation of Bell inequalities with low entanglement. Communications in Mathematical Physics, 306(3):695–746, 2011. Preprint (2010) at arXiv. [doi:10.1007/s00220-011-1296-8]

[14]   Marius Junge, Carlos Palazuelos, David Pérez-García, Ignacio Villanueva, and Michael M. Wolf: Unbounded violations of bipartite Bell inequalities via operator space theory. Communications in Mathematical Physics, 300(3):715–739, 2010. Preprint (2009) at arXiv. Shorter version appeared in Phys. Rev. Lett. [doi:10.1007/s00220-010-1125-5]

[15]   Jeff Kahn, Gil Kalai, and Nathan Linial: The influence of variables on Boolean functions. In Proc. 29th FOCS, pp. 68–80. IEEE Comp. Soc. Press, 1988. [doi:10.1109/SFCS.1988.21923]

[16]   Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick: Entangled games are hard to approximate. SIAM J. Comput., 40(3):848–877, 2011. Preliminary version in FOCS’08. [doi:10.1137/090751293]

[17]   Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, and Thomas Vidick: Using entanglement in quantum multi-prover interactive proofs. Comput. Complexity, 18(2):273–307, 2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0275-3]

[18]   Julia Kempe, Oded Regev, and Ben Toner: Unique games with entangled provers are easy. SIAM J. Comput., 39(7):3207–3229, 2010. Preliminary version in FOCS’08. Preprint (2007-09) at arXiv. [doi:10.1137/090772885]

[19]   Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017]

[20]   Subhash A. Khot and Nisheeth K. Vishnoi: The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into 1. In Proc. 46th FOCS, pp. 53–62. IEEE Comp. Soc. Press, 2005. [doi:10.1109/SFCS.2005.74]

[21]   Michel Ledoux and Michel Talagrand: Probability in Banach Spaces. Springer, 1991.

[22]   Ryan O’Donnell: Some topics in analysis of Boolean functions. Technical Report 055, 2008. Available at ECCC. Paper for invited talk at STOC’08.

[23]   Carlos Palazuelos: Bounding the largest Bell violation attainable by a quantum state. 2012. [arXiv:1206.3695]

[24]   Carlos Palazuelos: Superactivation of quantum nonlocality. Phys. Rev. Lett., 109(19):190401, Nov 2012. Preprint (2012) at arXiv. [doi:10.1103/PhysRevLett.109.190401]

[25]   David Pérez-García, Michael M. Wolf, Carlos Palazuelos, Ignacio Villanueva, and Marius Junge: Unbounded violations of tripartite Bell inequalities. Communications of Mathematical Physics, 279:455, 2008. Preprint (2012) at arXiv. [doi:10.1007/s00220-008-0418-4]

[26]   Oded Regev: Bell violations through independent bases games. Quantum Inf. Comput., 12(1-2):9–20, 2012. Preprint (2011) at arXiv. [ACM:2231038]

[27]   Boris S. Tsirel’son: Quantum analogues of the Bell inequalities. The case of two spatially separated domains. J. Math. Sciences, 36(4):557–570, 1987. [doi:10.1007/BF01663472]

[28]   Ronald de Wolf: A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing Library, Graduate Surveys, 1:1–20, 2008. [doi:10.4086/]