Experimentally Probing the Algorithmic Randomness and Incomputability of Quantum Randomness

Abstract

The advantages of quantum random number generators (QRNGs) over pseudo-random number generators (PRNGs) are normally attributed to the nature of quantum measurements. This is often seen as implying the superiority of the sequences of bits themselves generated by QRNGs, despite the absence of empirical tests supporting this. Nonetheless, one may expect sequences of bits generated by QRNGs to have properties that pseudo-random sequences do not; indeed, pseudo-random sequences are necessarily computable, a highly nontypical property of sequences. In this paper, we discuss the differences between QRNGs and PRNGs and the challenges involved in certifying the quality of QRNGs theoretically and testing their output experimentally. While QRNGs are often tested with standard suites of statistical tests, such tests are designed for PRNGs and only verify statistical properties of a QRNG, but are insensitive to many supposed advantages of QRNGs. We discuss the ability to test the incomputability and algorithmic complexity of QRNGs. While such properties cannot be directly verified with certainty, we show how one can construct indirect tests that may provide evidence for the incomputability of QRNGs. We use these tests to compare various PRNGs to a QRNG, based on superconducting transmon qutrits and certified by the Kochen-Specker Theorem, to see whether such evidence can be found in practice. While our tests fail to observe a strong advantage of the quantum random sequences due to algorithmic properties, the results are nonetheless informative: some of the test results are ambiguous and require further study, while others highlight difficulties that can guide the development of future tests of algorithmic randomness and incomputability.

arXiv comment20 pages, 6 figures

References in corpus (22)

• Random Numbers Certified by Bell's Theorem
• A simple test for hidden variables in spin-1 system
• Quantum random number generation
• A Fast and Compact Quantum Random Number Generator
• Experimentally testable state-independent quantum contextuality
• Private Randomness Expansion With Untrusted Devices
• Quantum random number generator based on photonic emission in semiconductors
• Optical Quantum Random Number Generator
• Semi-device-independent framework based on natural physical assumptions
• Strong Kochen-Specker theorem and incomputability of quantum randomness
• Quantum randomness and value indefiniteness
• Experimental Evidence of Quantum Randomness Incomputability
• A variant of the Kochen-Specker theorem localising value indefiniteness
• Value-indefinite observables are almost everywhere
• Realization of a quantum random generator certified with the Kochen-Specker theorem
• A Quantum Random Number Generator Certified by Value Indefiniteness
• Kolmogorov complexity of sequences of random numbers generated in Bell's experiments
• On the unpredictability of individual quantum measurement outcomes
• A Non-Probabilistic Model of Relativised Predictability in Physics
• How random are random numbers generated using photons?
• Von Neumann Normalisation of a Quantum Random Number Generator
• Quantumness, Randomness and Computability

Cited by in corpus (10)

• Kochen-Specker Contextuality
• Randomness? What randomness?
• Searching for evidence of algorithmic randomness and incomputability in the output of quantum random number generators
• Quantum randomness is chimeric
• The Golay codes and Quantum Contextuality
• Parity-based, bias-free optical quantum random number generation with min-entropy estimation
• Indistinguishability between quantum randomness and pseudo-randomness under efficiently calculable randomness measures
• Binary Quantum Random Number Generator Based on Value Indefinite Observables
• How Real is Incomputability in Physics?
• Quantum advantage by relational queries about physically realizable equivalence classes