Kolmogorov complexity of sequences of random numbers generated in Bell's experiments

Quantum states are the ultimate criterion to produce sequences of random numbers. Spatially spread entangled states allow the generation of correlated random sequences in remote locations. The impossibility of observing a quantum state, without disturbing it, ensures that the messages encoded using these sequences cannot be eavesdropped upon. This is the basis of quantum key distribution. It is then of crucial importance knowing whether the sequences generated in the practice by spatially spread entangled states are truly random, or not. Yet, that knowledge is not immediate. One of the obstacles is the very definition of randomness. “Statistical” randomness is related with the frequency of occurrence of strings of data. “Algorithmic” randomness is related with compressibility of the sequence, which is given by Kolmogorov complexity. Sequences generated by entangled pairs of photons are analyzed, focusing on estimations of their complexity. Standard tests of statistical randomness are also applied.

Figure 1

Reproduction of a portion of the data files of the Innsbruck experiment [21]. The left column ($*\_\mathrm{V}$.dat file) indicates the time photons were detected, in seconds. The right column ($*\_\mathrm{C}$.dat file) indicates the detector that fired and the analyzer's orientation, according to a code. The displayed files belong to the Alice station of run longdist35.

Figure 2

Graphical representation of main data in Table 1. Open circles (full squares) indicate the runs that do not pass (do pass) NIST tests. The horizontal line indicates Bell's limit; the vertical line indicates $K=0.9$.