Nonsignaling Deterministic Models for Nonlocal Correlations have to be Uncomputable

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.

Figure 1

Schematic representation of the scenario considered. Two distant observers, Alice and Bob, run a Bell test by implementing measurements on two systems. The observed correlations are described by a hidden-signaling mechanism plus computable functions determining the outputs given the inputs at each round $n$.

Figure 2

Suppose we want to learn a $\{0,1\}$-valued function $f$ and let $\{s_i{\}}_{i\in \mathbb{N}}$ be a computable enumeration of programs computing $\{0,1\}$-valued functions, which run in time $O(t)$. The $i$th row represents the sequence $s_i(0),s_i(1),s_i(2),\dots$. After seeing $f(0)=1$, $f(1)=0$, and $f(2)=1$, the guess for the target function is defined as (the index of) the first program whose outputs match those values (in the example, the guess is $s_6$).