Robust Bell inequalities from communication complexity

Sophie Laplante1, Mathieu Laurière2, Alexandre Nolin1, Jérémie Roland3, and Gabriel Senno4

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

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.

Share

► BibTeX data

► 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 (beta)

Crossref's cited-by service has no data on citing works. Unfortunately not all publishers provide suitable citation data.