Conferencia

Laplante, S.; Laurière, M.; Nolin, A.; Roland, J.; Senno, G.; Broadbent A. "Robust bell inequalities from communication complexity" (2016) 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016. 61
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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. © Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, and Gabriel Senno; licensed under Creative Commons License CC-BY.

Registro:

Documento: Conferencia
Título:Robust bell inequalities from communication complexity
Autor:Laplante, S.; Laurière, M.; Nolin, A.; Roland, J.; Senno, G.; Broadbent A.
Filiación:IRIF, Université Paris-Diderot, Paris, France
Université Libre de Bruxelles, Brussels, Belgium
CONICET, Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave:Bell inequalities; Communication complexity; Detector efficiency; Nonlocality; Bells; Computational complexity; Quantum computers; Quantum cryptography; Quantum theory; Bell inequalities; Bell-inequality violations; Classical communication; Communication complexity; Detector efficiency; Nonlocalities; Quantum communication complexity; Quantum distribution; Quantum communication
Año:2016
Volumen:61
DOI: http://dx.doi.org/10.4230/LIPIcs.TQC.2016.5
Título revista:11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016
Título revista abreviado:Leibniz Int. Proc. Informatics, LIPIcs
ISSN:18688969
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_18688969_v61_n_p_Laplante

Referencias:

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

Citas:

---------- APA ----------
Laplante, S., Laurière, M., Nolin, A., Roland, J., Senno, G. & Broadbent A. (2016) . Robust bell inequalities from communication complexity. 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016, 61.
http://dx.doi.org/10.4230/LIPIcs.TQC.2016.5
---------- CHICAGO ----------
Laplante, S., Laurière, M., Nolin, A., Roland, J., Senno, G., Broadbent A. "Robust bell inequalities from communication complexity" . 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016 61 (2016).
http://dx.doi.org/10.4230/LIPIcs.TQC.2016.5
---------- MLA ----------
Laplante, S., Laurière, M., Nolin, A., Roland, J., Senno, G., Broadbent A. "Robust bell inequalities from communication complexity" . 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016, vol. 61, 2016.
http://dx.doi.org/10.4230/LIPIcs.TQC.2016.5
---------- VANCOUVER ----------
Laplante, S., Laurière, M., Nolin, A., Roland, J., Senno, G., Broadbent A. Robust bell inequalities from communication complexity. Leibniz Int. Proc. Informatics, LIPIcs. 2016;61.
http://dx.doi.org/10.4230/LIPIcs.TQC.2016.5