Robust Bell inequalities from communication complexity

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

doi:10.22331/q-2018-06-07-72

Robust Bell inequalities from communication complexity

Sophie Laplante¹, Mathieu Laurière², Alexandre Nolin¹, Jérémie Roland³, and Gabriel Senno⁴

¹IRIF, Université Paris-Diderot, Paris, France
²ORFE, Princeton University, Princeton, NJ 08544, USA
³Université Libre de Bruxelles, Brussels, Belgium
⁴ICFO-Institut de Ciencies Fotoniques, The Barcelona Institute of Science and Technology, 08860 Castelldefels (Barcelona), Spain

Published:	2018-06-07, volume 2, page 72
Eprint:	arXiv:1606.09514v3
Doi:	https://doi.org/10.22331/q-2018-06-07-72
Citation:	Quantum 2, 72 (2018).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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 that 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 for the quantum violation of these Bell inequalities 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. This makes the Bell inequality resistant to the detection loophole, while a normalized Bell inequality is resistant to general local noise. 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 bound techniques. 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.

► BibTeX data

@article{Laplante2018robustbell,
  doi = {10.22331/q-2018-06-07-72},
  url = {https://doi.org/10.22331/q-2018-06-07-72},
  title = {Robust {B}ell inequalities from communication complexity},
  author = {Laplante, Sophie and Lauri{\`{e}}re, Mathieu and Nolin, Alexandre and Roland, J{\'{e}}r{\'{e}}mie and Senno, Gabriel},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {2},
  pages = {72},
  month = jun,
  year = {2018}
}

► References

[1] S. Aaronson and A. Ambainis. Quantum search of spatial regions. Theory of Computing, 1: 47–79, 2005. 10.4086/toc.2005.v001a004.
https://doi.org/10.4086/toc.2005.v001a004

[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. 10.1103/PhysRevA.65.052325.
https://doi.org/10.1103/PhysRevA.65.052325

[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. 10.1103/PhysRevA.46.5375.
https://doi.org/10.1103/PhysRevA.46.5375

[4] L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory. In Proc. 27th FOCS, pages 337–347. IEEE, 1986. 10.1109/SFCS.1986.15.
https://doi.org/10.1109/SFCS.1986.15

[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. 10.1007/s00037-007-0220-2.
https://doi.org/10.1007/s00037-007-0220-2

[6] J. S. Bell. On the Einstein Podolsky Rosen paradox. Physics, 1: 195, 1964. 10.1103/PhysicsPhysiqueFizika.1.195.
https://doi.org/10.1103/PhysicsPhysiqueFizika.1.195

[7] C. Branciard and N. Gisin. Quantifying the nonlocality of Greenberger-Horne-Zeilinger quantum correlations by a bounded communication simulation protocol. Physical Review Letters, 107 (2): 020401, 2011. 10.1103/PhysRevLett.107.020401.
https://doi.org/10.1103/PhysRevLett.107.020401

[8] J. B. Brask and R. Chaves. Bell scenarios with communication. Journal of Physics A: Mathematical and Theoretical, 50 (9): 094001, 2017. 10.1088/1751-8121/aa5840.
https://doi.org/10.1088/1751-8121/aa5840

[9] G. Brassard, R. Cleve, and A. Tapp. Cost of exactly simulating quantum entanglement with classical communication. Physical Review Letters, 83 (9): 1874, 1999. 10.1103/PhysRevLett.83.1874.
https://doi.org/10.1103/PhysRevLett.83.1874

[10] N. Brunner, D. Cavalcanti, A. Salles, and P. Skrzypczyk. Bound nonlocality and activation. Physical Review Letters, 106: 020402, 2011. 10.1103/PhysRevLett.106.020402.
https://doi.org/10.1103/PhysRevLett.106.020402

[11] H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs classical communication and computation. In Proc. 30th STOC, pages 63–68, 1998. 10.1145/276698.276713.
https://doi.org/10.1145/276698.276713

[12] 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. 10.4086/toc.2012.v008a027.
https://doi.org/10.4086/toc.2012.v008a027

[13] 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. 10.1073/pnas.1507647113.
https://doi.org/10.1073/pnas.1507647113

[14] 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. URL http://dl.acm.org/citation.cfm?id=2230916.2230924.
http://dl.acm.org/citation.cfm?id=2230916.2230924

[15] T. Durt, D. Kaszlikowski, and M. Żukowski. Violations of local realism with quantum systems described by ${N}$-dimensional Hilbert spaces up to ${N}=16$. Physical Review A, 64 (2): 024101, 2001. 10.1103/PhysRevA.64.024101.
https://doi.org/10.1103/PhysRevA.64.024101

[16] M. Forster, S. Winkler, and S. Wolf. Distilling nonlocality. Physical Review Letters, 102: 120401, 2009. 10.1103/PhysRevLett.102.120401.
https://doi.org/10.1103/PhysRevLett.102.120401

[17] R. Gallego, L. E. Würflinger, A. Acín, and M. Navascués. Operational framework for nonlocality. Physical Review Letters, 109: 070401, 2012. 10.1103/PhysRevLett.109.070401.
https://doi.org/10.1103/PhysRevLett.109.070401

[18] 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. URL https://www.revistas.usp.br/resenhasimeusp/article/view/74836.
https://www.revistas.usp.br/resenhasimeusp/article/view/74836

[19] P. Harsha and R. Jain. A strong direct product theorem for the tribes function via the smooth-rectangle bound. In Proc. 33rd FSTTCS, volume 24, pages 141–152, 2013. ISBN 978-3-939897-64-4. 10.4230/LIPIcs.FSTTCS.2013.141.
https://doi.org/10.4230/LIPIcs.FSTTCS.2013.141

[20] R. Jain and H. Klauck. The partition bound for classical communication complexity and query complexity. In Proc. 25th CCC, pages 247–258, 2010. 10.1109/CCC.2010.31.
https://doi.org/10.1109/CCC.2010.31

[21] T. S. Jayram, R. Kumar, and D. Sivakumar. Two applications of information complexity. In Proc. 35th STOC, pages 673–682, 2003. ISBN 1-58113-674-9. 10.1145/780542.780640.
https://doi.org/10.1145/780542.780640

[22] M. Junge and C. Palazuelos. Large violation of Bell inequalities with low entanglement. Communications in Mathematical Physics, 306 (3): 695–746, 2011. 10.1007/s00220-011-1296-8.
https://doi.org/10.1007/s00220-011-1296-8

[23] 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, 2010a. 10.1007/s00220-010-1125-5.
https://doi.org/10.1007/s00220-010-1125-5

[24] 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, 2010b. 10.1103/PhysRevLett.104.170405.
https://doi.org/10.1103/PhysRevLett.104.170405

[25] M. Junge, T. Oikhberg, and C. Palazuelos. Reducing the number of questions in nonlocal games. Journal of Mathematical Physics, 57 (10): 102203, 2016. 10.1063/1.4965831.
https://doi.org/10.1063/1.4965831

[26] D. Kaszlikowski, P. Gnaciński, M. Żukowski, W. Miklaszewski, and A. Zeilinger. Violations of local realism by two entangled $\mathit{N}$-dimensional systems are stronger than for two qubits. Physical Review Letters, 85: 4418–4421, 2000. 10.1103/PhysRevLett.85.4418.
https://doi.org/10.1103/PhysRevLett.85.4418

[27] 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. 10.1137/130928273.
https://doi.org/10.1137/130928273

[28] B. Klartag and O. Regev. Quantum one-way communication can be exponentially stronger than classical communication. In Proc. 43rd STOC, pages 31–40, 2011. ISBN 978-1-4503-0691-1. 10.1145/1993636.1993642.
https://doi.org/10.1145/1993636.1993642

[29] 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. 10.1007/978-3-662-43948-7_58.
https://doi.org/10.1007/978-3-662-43948-7_58

[30] E. Kushilevitz and N. Nisan. Communication complexity. Cambridge University Press, 1997. ISBN 978-0-521-56067-2. 10.1017/CBO9780511574948.
https://doi.org/10.1017/CBO9780511574948

[31] S. Laplante, V. Lerays, and J. Roland. Classical and quantum partition bound and detector inefficiency. In Proc. 39th ICALP, pages 617–628, 2012. 10.1007/978-3-642-31594-7_52.
https://doi.org/10.1007/978-3-642-31594-7_52

[32] S. Laplante, M. Laurière, A. Nolin, J. Roland, and G. Senno. Robust Bell Inequalities from Communication Complexity. In Anne Broadbent, editor, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), volume 61 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:24, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-019-4. 10.4230/LIPIcs.TQC.2016.5. URL http://drops.dagstuhl.de/opus/volltexte/2016/6686.
https://doi.org/10.4230/LIPIcs.TQC.2016.5
http://drops.dagstuhl.de/opus/volltexte/2016/6686

[33] W. Laskowski, T. Paterek, M. Żukowski, and Č Brukner. Tight multipartite Bell's inequalities involving many measurement settings. Physical Review Letters, 93 (20): 200401, 2004. 10.1103/PhysRevLett.93.200401.
https://doi.org/10.1103/PhysRevLett.93.200401

[34] N. Linial and A. Shraibman. Lower bounds in communication complexity based on factorization norms. Random Structures & Algorithms, 34 (3): 368–394, 2009. ISSN 1098-2418. 10.1002/rsa.20232.
https://doi.org/10.1002/rsa.20232

[35] S. Massar. Nonlocality, closing the detection loophole, and communication complexity. Physical Review A, 65: 032121, 2002. 10.1103/PhysRevA.65.032121.
https://doi.org/10.1103/PhysRevA.65.032121

[36] S. Massar, S. Pironio, J. Roland, and B. Gisin. Bell inequalities resistant to detector inefficiency. Physical Review A, 66: 052112, 2002. 10.1103/PhysRevA.66.052112.
https://doi.org/10.1103/PhysRevA.66.052112

[37] 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. 10.1086/psaprocbienmeetp.1992.1.192771.
https://doi.org/10.1086/psaprocbienmeetp.1992.1.192771

[38] K. Maxwell and E. Chitambar. Bell inequalities with communication assistance. Physical Review A, 89 (4): 042108, 2014. 10.1103/PhysRevA.89.042108.
https://doi.org/10.1103/PhysRevA.89.042108

[39] D. N. Mermin. Extreme quantum entanglement in a superposition of macroscopically distinct states. Physical Review Letters, 65 (15): 1838, 1990. 10.1103/PhysRevLett.65.1838.
https://doi.org/10.1103/PhysRevLett.65.1838

[40] 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. 10.1103/PhysRevA.74.062109.
https://doi.org/10.1103/PhysRevA.74.062109

[41] M. A Nielsen and I. Chuang. Quantum computation and quantum information. AAPT, 2002. 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[42] C. Palazuelos and Z. Yin. Large bipartite Bell violations with dichotomic measurements. Physical Review A, 92: 052313, 2015. 10.1103/PhysRevA.92.052313.
https://doi.org/10.1103/PhysRevA.92.052313

[43] 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. 10.1007/s00220-008-0418-4.
https://doi.org/10.1007/s00220-008-0418-4

[44] S. Pironio. Violations of Bell inequalities as lower bounds on the communication cost of nonlocal correlations. Physical Review A, 68 (6): 062102, 2003. 10.1103/PhysRevA.68.062102.
https://doi.org/10.1103/PhysRevA.68.062102

[45] R. Raz. Exponential separation of quantum and classical communication complexity. In Proc. 31st STOC, pages 358–367, 1999. ISBN 1-58113-067-8. 10.1145/301250.301343.
https://doi.org/10.1145/301250.301343

[46] A. A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106 (2): 385 – 390, 1992. ISSN 0304-3975. 10.1016/0304-3975(92)90260-M.
https://doi.org/10.1016/0304-3975(92)90260-M

[47] A. A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67 (1): 145, 2003. 10.1070/IM2003v067n01ABEH000422.
https://doi.org/10.1070/IM2003v067n01ABEH000422

[48] A. A. Sherstov. The communication complexity of gap Hamming distance. Theory of Computing, 8 (1): 197–208, 2012. 10.4086/toc.2012.v008a008.
https://doi.org/10.4086/toc.2012.v008a008

[49] M. Steiner. Towards quantifying non-local information transfer: finite-bit non-locality. Physics Letters A, 270 (5): 239–244, 2000. 10.1016/S0375-9601(00)00315-7.
https://doi.org/10.1016/S0375-9601(00)00315-7

[50] B. F. Toner and D. Bacon. Communication cost of simulating Bell correlations. Physical Review Letters, 91 (18): 187904, 2003. 10.1103/PhysRevLett.91.187904.
https://doi.org/10.1103/PhysRevLett.91.187904

[51] 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. 10.1007/BF01663472.
https://doi.org/10.1007/BF01663472

[52] A. C. C. Yao. Some complexity questions related to distributed computing. In Proc. 11th STOC, pages 209–213, 1979. 10.1145/800135.804414.
https://doi.org/10.1145/800135.804414

[53] A. C. C. Yao. Lower bounds by probabilistic arguments. In Proc. 24th FOCS, pages 420–428. IEEE, 1983. 10.1109/SFCS.1983.30.
https://doi.org/10.1109/SFCS.1983.30

[54] A. C. C. Yao. Quantum circuit complexity. In Proc. 34th FOCS, pages 352–361. IEEE, 1993. 10.1109/SFCS.1993.366852.
https://doi.org/10.1109/SFCS.1993.366852

Cited by

[1] Jef Pauwels, Stefano Pironio, Emmanuel Zambrini Cruzeiro, and Armin Tavakoli, "Adaptive Advantage in Entanglement-Assisted Communications", Physical Review Letters 129 12, 120504 (2022).

[2] Zhih-Ahn Jia, Lu Wei, Yu-Chun Wu, and Guang-Can Guo, "Quantum Advantages of Communication Complexity from Bell Nonlocality", Entropy 23 6, 744 (2021).

[3] Ashley Montanaro, "Quantum states cannot be transmitted efficiently classically", Quantum 3, 154 (2019).

[4] Debashis Saha and Anubhav Chaturvedi, "Preparation contextuality as an essential feature underlying quantum communication advantage", Physical Review A 100 2, 022108 (2019).

[5] Armin Tavakoli, Marek Żukowski, and Časlav Brukner, "Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?", Quantum 4, 316 (2020).

[6] Ashley Montanaro, "Quantum states cannot be transmitted efficiently classically", arXiv:1612.06546, (2016).

[7] Gabriel Senno, Ariel Bendersky, and Santiago Figueira, "Randomness and Non-Locality", Fluctuation and Noise Letters 15 3, 1640005-200 (2016).

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-08 09:00:31) and SAO/NASA ADS (last updated successfully 2023-06-08 09:00:32). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.