Quantum mechanics and algorithmic randomness
Ulvi Yurtsever · Complexity · 2000
A long sequence of tosses of a classical coin produces an apparently random bit string, but classical randomness is an illusion: the algorithmic information content of a classically-generated bit string lies almost entirely in the description of initial conditions. This letter presents a simple argument that, by contrast, a sequence of bits produced by tossing a quantum coin is, almost certainly, genuinely (algorithmically) random. This result can be interpreted as a strengthening of Bell’s no-hidden-variables theorem, and relies on causality and quantum entanglement in a manner similar to Bell’s original argument. PACS number(s): 03.65.Bz, 03.67.-a, 03.67.Hk ∗ Submitted to Physical Review LettersA long string of (pseudo-)random bits produced by computer passes all practical statistical tests of randomness (provided the algorithm used is sound, see [1]), but it is not truly random: the information content of the string (its “algorithmic complexity”) is bounded by the size of the generating algorithm plus a few