Searching for evidence of algorithmic randomness and incomputability in the output of quantum random number generators

Abstract

Ideal quantum random number generators (QRNGs) can produce algorithmically random and thus incomputable sequences, in contrast to pseudo-random number generators. However, the verification of the presence of algorithmic randomness and incomputability is a nontrivial task. We present the results of a search for algorithmic randomness and incomputability in the output from two different QRNGs, performed by applying tests based on the Solovay-Strassen test of primality and the Chaitin-Schwartz theorem. The first QRNG uses measurements of quantum vacuum fluctuations. The second QRNG is based on polarization measurements on entangled single photons; for this generator, we use looped (and thus highly compressible) strings that also allow us to assess the ability of the tests to detect repeated bit patterns. Compared to a previous search for algorithmic randomness, our study increases statistical power by almost 3 orders of magnitude.

9 pages, 5 figures, matches published version

References in corpus (6)

• Real time demonstration of high bitrate quantum random number generation with coherent laser light
• Maximization of Extractable Randomness in a Quantum Random-Number Generator
• Strong Kochen-Specker theorem and incomputability of quantum randomness
• Quantum randomness and value indefiniteness
• Experimental Evidence of Quantum Randomness Incomputability
• Parity-based, bias-free optical quantum random number generation with min-entropy estimation