Document Open Access Logo

Robust Bell Inequalities from Communication Complexity

Authors Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, Gabriel Senno

PDF
Thumbnail PDF

File

LIPIcs.TQC.2016.5.pdf
  • Filesize: 0.57 MB
  • 24 pages

Document Identifiers

Author Details

Sophie Laplante
Mathieu Laurière
Alexandre Nolin
Jérémie Roland
Gabriel Senno

Cite AsGet BibTex

Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, and Gabriel Senno. Robust Bell Inequalities from Communication Complexity. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.TQC.2016.5

Abstract

The question of how large Bell inequality violations can be, for quantum distributions, has been the object of much work in the past several years. We say a Bell inequality is normalized if its absolute value does not exceed 1 for any classical (i.e. local) distribution. Upper and (almost) tight lower bounds have been given in terms of number of outputs of the distribution, number of inputs, and the dimension of the shared quantum states. In this work, we revisit normalized Bell inequalities together with another family: inefficiency-resistant Bell inequalities. To be inefficiency-resistant, the Bell value must not exceed 1 for any local distribution, including those that can abort. Both these families of Bell inequalities are closely related to communication complexity lower bounds. We show how to derive large violations from any gap between classical and quantum communication complexity, provided the lower bound on classical communication is proven using these lower bounds. This leads to inefficiency-resistant violations that can be exponential in the size of the inputs. Finally, we study resistance to noise and inefficiency for these Bell inequalities.
Keywords
  • Communication complexity
  • Bell inequalities
  • nonlocality
  • detector efficiency

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Aaronson and A. Ambainis. Quantum search of spatial regions. Theory of Computing, 1:47-79, 2005. Google Scholar
  2. A. Acín, T. Durt, N. Gisin, and J. I. Latorre. Quantum nonlocality in two three-level systems. Physical Review A, 65:052325, 2002. Google Scholar
  3. M. Ardehali. Bell inequalities with a magnitude of violation that grows exponentially with the number of particles. Physical Review A, 46:5375-5378, 1992. Google Scholar
  4. L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory. In Proc. 27th FOCS, pages 337-347. IEEE, 1986. Google Scholar
  5. P. Beame, T. Pitassi, N. Segerlind, and A. Wigderson. A strong direct product theorem for corruption and the multiparty communication complexity of disjointness. Computational Complexity, 15(4):391-432, 2006. Google Scholar
  6. J. S. Bell. On the Einstein Podolsky Rosen paradox. Physics, 1:195, 1964. Google Scholar
  7. G. Brassard, R. Cleve, and A. Tapp. Cost of exactly simulating quantum entanglement with classical communication. Physical Review Letters, 83(9):1874, 1999. Google Scholar
  8. N. Brunner, D. Cavalcanti, A. Salles, and P. Skrzypczyk. Bound nonlocality and activation. Physical Review Letters, 106:020402, 2011. Google Scholar
  9. H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs classical communication and computation. In Proc. 30th STOC, pages 63-68, 1998. Google Scholar
  10. H. Buhrman, Ł. Czekaj, A. Grudka, Mi. Horodecki, P. Horodecki, M. Markiewicz, F. Speelman, and S. Strelchuk. Quantum communication complexity advantage implies violation of a Bell inequality. Proceedings of the National Academy of Sciences, 113(12):3191-3196, 2016. Google Scholar
  11. H. Buhrman, O. Regev, G. Scarpa, and R. de Wolf. Near-optimal and explicit Bell inequality violations. Theory of Computing, 8(1):623-645, 2012. Google Scholar
  12. J. Degorre, M. Kaplan, S. Laplante, and J. Roland. The communication complexity of non-signaling distributions. Quantum information &computation, 11(7-8):649-676, 2011. Google Scholar
  13. M. Forster, S. Winkler, and S. Wolf. Distilling nonlocality. Physical Review Letters, 102:120401, 2009. Google Scholar
  14. R. Gallego, L. E. Würflinger, A. Acín, and M. Navascués. Operational framework for nonlocality. Physical Review Letters, 109:070401, 2012. Google Scholar
  15. A. Grothendieck. Résumé de la théorie métrique des produits tensoriels topologiques. Boletim da Sociedade de Matemática de São Paulo, 8:1-79, 1953. Google Scholar
  16. P. Harsha and R. Jain. A Strong Direct Product Theorem for the Tribes Function via the Smooth-Rectangle Bound. In Procs. 33rd FSTTCS, volume 24, pages 141-152, 2013. Google Scholar
  17. R. Jain and H. Klauck. The partition bound for classical communication complexity and query complexity. In Proc. 25th CCC, pages 247-258, 2010. Google Scholar
  18. T. S. Jayram, R. Kumar, and D. Sivakumar. Two applications of information complexity. In Proc. 35th STOC, pages 673-682, 2003. Google Scholar
  19. M. Junge and C. Palazuelos. Large violation of Bell inequalities with low entanglement. Communications in Mathematical Physics, 306(3):695-746, 2011. Google Scholar
  20. M. Junge, C. Palazuelos, D. Pérez-García, I. Villanueva, and M. M. Wolf. Operator space theory: A natural framework for Bell inequalities. Physical Review Letters, 104:170405, 2010. Google Scholar
  21. M. Junge, C. Palazuelos, D. Pérez-García, I. Villanueva, and M. M. Wolf. Unbounded violations of bipartite Bell inequalities via operator space theory. Communications in Mathematical Physics, 300(3):715-739, 2010. Google Scholar
  22. D. Kaszlikowski, P. Gnaciński, M. Żukowski, W. Miklaszewski, and A. Zeilinger. Violations of local realism by two entangled N-dimensional systems are stronger than for two qubits. Physical Review Letters, 85:4418-4421, 2000. Google Scholar
  23. I. Kerenidis, S. Laplante, V. Lerays, J. Roland, and D. Xiao. Lower bounds on information complexity via zero-communication protocols and applications. SIAM Journal on Computing, 44(5):1550-1572, 2015. Google Scholar
  24. B. Klartag and O. Regev. Quantum one-way communication can be exponentially stronger than classical communication. In Proc. 43th STOC, pages 31-40, 2011. Google Scholar
  25. G. Kol, S. Moran, A. Shpilka, and A. Yehudayoff. Approximate nonnegative rank is equivalent to the smooth rectangle bound. In Automata, Languages, and Programming, pages 701-712. Springer, 2014. Google Scholar
  26. E. Kushilevitz and N. Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  27. S. Laplante, V. Lerays, and J. Roland. Classical and quantum partition bound and detector inefficiency. In Proc. 39th ICALP, pages 617-628, 2012. Google Scholar
  28. W. Laskowski, T. Paterek, M. Żukowski, and Č Brukner. Tight multipartite Bell’s inequalities involving many measurement settings. Physical Review Letters, 93(20):200401, 2004. Google Scholar
  29. N. Linial and A. Shraibman. Lower bounds in communication complexity based on factorization norms. Random Structures &Algorithms, 34(3):368-394, 2009. Google Scholar
  30. S. Massar. Nonlocality, closing the detection loophole, and communication complexity. Physical Review A, 65:032121, 2002. Google Scholar
  31. S. Massar, S. Pironio, J. Roland, and B. Gisin. Bell inequalities resistant to detector inefficiency. Physical Review A, 66:052112, 2002. Google Scholar
  32. T. Maudlin. Bell’s inequality, information transmission, and prism models. In PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, pages 404-417. JSTOR, 1992. Google Scholar
  33. D. N. Mermin. Extreme quantum entanglement in a superposition of macroscopically distinct states. Physical Review Letters, 65(15):1838, 1990. Google Scholar
  34. K. Nagata, W. Laskowski, and T. Paterek. Bell inequality with an arbitrary number of settings and its applications. Physical Review A, 74(6):062109, 2006. Google Scholar
  35. C. Palazuelos and Z. Yin. Large bipartite Bell violations with dichotomic measurements. Physical Review A, 92:052313, 2015. Google Scholar
  36. D. Pérez-García, M. M. Wolf, C. Palazuelos, I. Villanueva, and M. Junge. Unbounded violation of tripartite Bell inequalities. Communications in Mathematical Physics, 279(2):455-486, 2008. Google Scholar
  37. S. Pironio. Violations of Bell inequalities as lower bounds on the communication cost of nonlocal correlations. Physical Review A, 68(6):062102, 2003. Google Scholar
  38. R. Raz. Exponential separation of quantum and classical communication complexity. In Proc. 31th STOC, pages 358-367, 1999. Google Scholar
  39. A. A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106(2):385-390, 1992. Google Scholar
  40. A. A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145, 2003. Google Scholar
  41. A. A. Sherstov. The communication complexity of gap hamming distance. Theory of Computing, 8(1):197-208, 2012. Google Scholar
  42. M. Steiner. Towards quantifying non-local information transfer: finite-bit non-locality. Physics Letters A, 270(5):239-244, 2000. Google Scholar
  43. B. F. Toner and D. Bacon. Communication cost of simulating Bell correlations. Physical Review Letters, 91(18):187904, 2003. Google Scholar
  44. B. S. Tsirel’son. Quantum analogues of the Bell inequalities. the case of two spatially separated domains. Journal of Soviet Mathematics, 36(4):557-570, 1987. Google Scholar
  45. A. C. C. Yao. Some complexity questions related to distributed computing. In Proc. 11th STOC, pages 209-213, 1979. Google Scholar
  46. A. C. C. Yao. Lower bounds by probabilistic arguments. In Proc. 24th FOCS, pages 420-428. IEEE, 1983. Google Scholar
  47. A. C. C. Yao. Quantum circuit complexity. In Proc. 34th FOCS, pages 352-361. IEEE, 1993. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact