Artículo

El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Quantum mechanics postulates random outcomes. However, a model making the same output predictions but in a deterministic manner would be, in principle, experimentally indistinguishable from quantum theory. In this work we consider such models in the context of nonlocality on a device-independent scenario. That is, we study pairs of nonlocal boxes that produce their outputs deterministically. It is known that, for these boxes to be nonlocal, at least one of the boxes' outputs has to depend on the other party's input via some kind of hidden signaling. We prove that, if the deterministic mechanism is also algorithmic, there is a protocol that, with the sole knowledge of any upper bound on the time complexity of such an algorithm, extracts that hidden signaling and uses it for the communication of information. © 2017 American Physical Society.

Registro:

Documento: Artículo
Título:Nonsignaling Deterministic Models for Nonlocal Correlations have to be Uncomputable
Autor:Bendersky, A.; Senno, G.; De La Torre, G.; Figueira, S.; Acín, A.
Filiación:Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Buenos Aires, 1428, Argentina
CONICET-Universidad de Buenos Aires, Instituto de Investigación en Ciencias de la Computación (ICC), Buenos Aires, 1428, Argentina
ICFO-Institut de Ciencies Fotoniques, Barcelona Institute of Science and Technology, Castelldefels, Barcelona, 08860, Spain
ICREA, Pg. Lluis Companys 23, Barcelona, 08010, Spain
Palabras clave:Parallel processing systems; Deterministic mechanism; Deterministic models; Model-making; Nonlocal; Nonlocal correlations; Nonlocalities; Time complexity; Upper Bound; Quantum theory
Año:2017
Volumen:118
Número:13
DOI: http://dx.doi.org/10.1103/PhysRevLett.118.130401
Título revista:Physical Review Letters
Título revista abreviado:Phys Rev Lett
ISSN:00319007
CODEN:PRLTA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00319007_v118_n13_p_Bendersky

Referencias:

  • Shimony, A., (1986) Quantum Concepts in Space and Time, pp. 182-203. , edited by R. Penrose and C. J. Isham (Oxford University Press, New York)
  • Toner, B.F., Bacon, D., Communication Cost of Simulating Bell Correlations (2003) Phys. Rev. Lett., 91, p. 187904
  • Bohm, D., A suggested interpretation of the quantum theory in terms of "hidden" variables. i (1952) Phys. Rev., 85, p. 166
  • Regev, O., Toner, B., Simulating quantum correlations with finite communication (2010) SIAM J. Comput., 39, p. 1562
  • Shi, Y., Zhu, Y., Tensor norms and the classical communication complexity of nonlocal quantum measurement (2008) SIAM J. Comput., 38, p. 753
  • Degorre, J., Kaplan, M., Laplante, S., Roland, J., The communication complexity of non-signaling distributions (2011) Quantum Inf. Comput., 11, p. 649
  • Yurtsever, U., Quantum mechanics and algorithmic randomness (2000) Complexity, 6, p. 27
  • Wolf, S., Nonlocality without counterfactual reasoning (2015) Phys. Rev. A, 92, p. 052102
  • Abbott, A.A., Calude, C.S., Conder, J., Svozil, K., Strong Kochen-Specker theorem and incomputability of quantum randomness (2012) Phys. Rev. A, 86, p. 062109
  • Abbott, A.A., Calude, C.S., Svozil, K., A variant of the Kochen-Specker theorem localising value indefiniteness (2015) J. Math. Phys. (N.Y.), 56, p. 102201
  • Clauser, J.F., Horne, M.A., Shimony, A., Holt, R.A., Proposed Experiment to Test Local Hidden-Variable Theories (1969) Phys. Rev. Lett., 23, p. 880
  • Zeugmann, T., Zilles, S., Learning recursive functions: A survey (2008) Theor. Comput. Sci., 397, p. 4
  • Gold, E.M., Language identification in the limit (1967) Inf. Control, 10, p. 447
  • http://link.aps.org/supplemental/10.1103/PhysRevLett.118.130401, See Supplemental Material at, for a proof of the signaling protocol's soundness when using (Equation presented)-randomness; Downey, R.G., Hirschfeldt, D.R., (2010) Algorithmic Randomness and Complexity, , (Springer Science and Business Media, New York)
  • Nies, A., (2009) Computability and Randomness, 51. , (Oxford University Press, Oxford), Vol.
  • Figueira, S., Nies, A., Feasible analysis, randomness, and base invariance (2015) Theor. Comput. Syst., 56, p. 439
  • Lloyd, S., Ultimate physical limits to computation (2000) Nature (London), 406, p. 1047

Citas:

---------- APA ----------
Bendersky, A., Senno, G., De La Torre, G., Figueira, S. & Acín, A. (2017) . Nonsignaling Deterministic Models for Nonlocal Correlations have to be Uncomputable. Physical Review Letters, 118(13).
http://dx.doi.org/10.1103/PhysRevLett.118.130401
---------- CHICAGO ----------
Bendersky, A., Senno, G., De La Torre, G., Figueira, S., Acín, A. "Nonsignaling Deterministic Models for Nonlocal Correlations have to be Uncomputable" . Physical Review Letters 118, no. 13 (2017).
http://dx.doi.org/10.1103/PhysRevLett.118.130401
---------- MLA ----------
Bendersky, A., Senno, G., De La Torre, G., Figueira, S., Acín, A. "Nonsignaling Deterministic Models for Nonlocal Correlations have to be Uncomputable" . Physical Review Letters, vol. 118, no. 13, 2017.
http://dx.doi.org/10.1103/PhysRevLett.118.130401
---------- VANCOUVER ----------
Bendersky, A., Senno, G., De La Torre, G., Figueira, S., Acín, A. Nonsignaling Deterministic Models for Nonlocal Correlations have to be Uncomputable. Phys Rev Lett. 2017;118(13).
http://dx.doi.org/10.1103/PhysRevLett.118.130401