Non-signaling deterministic models for non-local correlations have to be uncomputable

GONZALO DE LA TORRE; ANTONIO ACIN; GABRIEL SENNO; SANTIAGO FIGUEIRA; ARIEL BENDERSKY

PHYSICAL REVIEW LETTERS

AMER PHYSICAL SOC

Lugar: New York; Año: 2017 vol. 118

0031-9007

Quantum mechanics postulates random outcomes. However, a model making the same outputpredictions but in a deterministic manner would be, in principle, experimentally indistinguishablefrom quantum theory. In this work we consider such models in the context of non-locality on adevice independent scenario. That is, we study pairs of non-local boxes that produce their outputsdeterministically. It is known that, for these boxes to be non-local, at least one of the boxes´ outputhas to depend on the other party´s input via some kind of hidden signaling. We prove that, if thedeterministic mechanism is also algorithmic, there is a protocol that, with the sole knowledge of anyupper bound on the time complexity of such algorithm, extracts that hidden signaling and uses itfor the communication of information.