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 pseudorandom
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, certified by the Kochen-Specker Theorem.
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.
