© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1806.08762 · Physica Scripta

Experimentally probing the algorithmic randomness and incomputability of quantum randomness

Alastair A. Abbott, Cristian S Calude, Michael J Dinneen, Nan Huang

Published Nov 23, 2018• 28 citations

Abstract

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.

DOI: 10.1088/1402-4896/aaf36a

Related papers

Algorithmic Randomness and Quantum Random Number Generation

José Manuel Agüero Trejo

In this Thesis, we develop the only class of QRNGs, to date, that has been proved to be better than any PRNG. This type of QRNG is based on a located form of the Kochen-Specker Theorem. This certification is unique because i) the assumptions used have been experimentally validated, ii) the robustness of measurements was proved theoretically, iii) the quality of quantum random digits generated with this class of QRNG was experimentally shown to be better than that of the best PRNGs, demonstrating for the first time the strong effects of incomputability on the outputs of a quantum random number generator. Finally, we propose a method using high-quality randomness for inverting a class of one-way functions in a pre-given time.

•Jan 1, 2024•0 citations

Quantum Random Numbers: Certication and Generation

Alastair A. Abbott

In this thesis we study the generation of randomness from quantum mechanical sources: quantum random number generators (QRNGs). Such devices are thought to provide a better quality of randomness than is possible with classical devices, but the issue is in need of more rigorous study. In Chapter 1 we provide the necessary background for the thesis from both computability and probability theory. We then present and extend some recent results providing a more theoretical grounding for the indeterminism in quantum mechanics. In particular, we show that sequences of quantum random bits are incomputable in the strongest sense: no bit can be provably computed in advance. In Chapter 2 we study in detail the use of von Neumann normalisation for QRNGs producing both finite strings and infinite sequences of bits; such normalisation methods are necessary in order to counter for experimental imperfections. We show that, in the case of a constantly biased source, this normalisation gives the desired uniform distribution. The effect of this normalisation on the (in)computability of the generated sequences is studied, and it is shown that algorithmic randomness and Borel normality are preserved, but e-randomness (and thus incomputability) is, in general, not. Experimental bounds for the extent of departure from the uniform distribution in the non-ideal case of a slowly drifting bias are derived. In Chapter 3 we propose a new QRNG which uses entangled photon pairs and is certified to produce incomputable bits by value indefiniteness; this is the first QRNG with explicit certification by a physical principle. The effects of various experimental imperfections are discussed in detail, and care is taken to make the proposed QRNG as robust as is possible to these. A robust method based on XORing the produced bitstrings together is proposed to further improve the quality of the distribution produced by the QRNG. Various improvements and optimisations to this scheme are discussed.

•Jan 1, 2011•0 citations

How Random Is Quantum Randomness? An Experimental Approach

Cristian S. Calude, Michael J. Dinneen, Monica E. Bad Dumitrescu +1 more

Our aim is to experimentally study the possibility of distinguishing between quantum sources of randomness--recently proved to be theoretically incomputable--and some well-known computable sources of pseudo-randomness. Incomputability is a necessary, but not sufficient "symptom" of "true randomness". We base our experimental approach on algorithmic information theory which provides characterizations of algorithmic random sequences in terms of the degrees of incompressibility of their finite prefixes. Algorithmic random sequences are incomputable, but the converse implication is false. We have performed tests of randomness on pseudo-random strings (finite sequences) of length $2^{32}$ generated with software (Mathematica, Maple), which are cyclic (so, strongly computable), the bits of $π$, which is computable, but not cyclic, and strings produced by quantum measurements (with the commercial device Quantis and by the Vienna IQOQI group). Our empirical tests indicate quantitative differences, some statistically significant, between computable and incomputable sources of "randomness".

arXiv:0912.4379•Dec 22, 2009•2 citations

Realization of a Quantum Random Generator Certified with the Kochen-Specker Theorem

Anatoly Kulikov, Markus Jerger, Anton Potočnik +2 more

Random numbers are required for a variety of applications from secure communications to Monte Carlo simulation. Yet randomness is an asymptotic property, and no output string generated by a physical device can be strictly proven to be random. We report an experimental realization of a quantum random number generator (QRNG) with randomness certified by quantum contextuality and the Kochen-Specker theorem. The certification is not performed in a device-independent way but through a rigorous theoretical proof of each outcome being value indefinite even in the presence of experimental imperfections. The analysis of the generated data confirms the incomputable nature of our QRNG.

arXiv:1709.03687•Physical Review Letters•Dec 11, 2017•36 citations

Quantum Random Number Generators : Benchmarking and Challenges

David Cirauqui, Miguel Ángel García-March, Guillem Guigó i Corominas +5 more

We discuss the current state of the art of Quantum Random Number Generators (QRNG) and their possible applications in the search for quantum advantages. To this aim, we first discuss a possible way of benchmarking QRNG by applying them to the computation of complicated and hard to realize classical simulations, such as critical dynamics in two-dimensional Ising lattices. These are performed with the help of computing devices based on field-programmable gate arrays (FPGAs) or graphic processing units (GPUs). The results obtained for QRNG are compared with those obtained by classical pseudo-random number generators (PRNG) of various qualities. Monte Carlo simulations of critical dynamics in moderate lattice sizes (128$\times$128) start to be sensitive to the correlations present in pseudo-random numbers sequences, allowing us to detect them. By comparing our analysis with that of Ref. [PRE {\bf 93}, 022113 (2016)], we estimate the requirements for QRNGs in terms of speed, rapidity of access, and efficiency to achieve the objective of quantum advantage with respect to the best PRNGs. We discuss the technical challenges associated with this objective.

arXiv:2206.05328•Jun 10, 2022•5 citations

Quantum Random Number Generator-Based Cryptographic Algorithm Design

Jincheng Zhang

This paper explores the design of cryptographic algorithms leveraging the inherent randomness of quantum random number generators (QRNGs). Traditional cryptographic algorithms often rely on pseudo-random number generators (PRNGs), which are deterministic and therefore vulnerable to attacks if their internal state is compromised. QRNGs, on the other hand, derive their randomness from quantum mechanical phenomena, offering a fundamentally unpredictable source of numbers. This research investigates the application of QRNGs to enhance cryptographic security, focusing on constructing algorithms that exploit this unique property. The core claim is that utilizing QRNG characteristics allows for the design of more secure cryptographic algorithms. The proposed mechanism involves capitalizing on the non-deterministic nature of QRNGs to build algorithms with heightened security levels. This approach presents a novel security guarantee method by incorporating true randomness into cryptographic processes. We examine specific algorithm designs and analyze their security implications compared to traditional PRNG-based approaches. The paper concludes with a discussion on the challenges and future directions of utilizing QRNGs in cryptography.

•Sep 1, 2026•0 citations

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.

In this Thesis, we develop the only class of QRNGs, to date, that has been proved to be better than any PRNG. This type of QRNG is based on a located form of the Kochen-Specker Theorem. This certification is unique because i) the assumptions used have been experimentally validated, ii) the robustness of measurements was proved theoretically, iii) the quality of quantum random digits generated with this class of QRNG was experimentally shown to be better than that of the best PRNGs, demonstrating for the first time the strong effects of incomputability on the outputs of a quantum random number generator. Finally, we propose a method using high-quality randomness for inverting a class of one-way functions in a pre-given time.

In this thesis we study the generation of randomness from quantum mechanical sources: quantum random number generators (QRNGs). Such devices are thought to provide a better quality of randomness than is possible with classical devices, but the issue is in need of more rigorous study. In Chapter 1 we provide the necessary background for the thesis from both computability and probability theory. We then present and extend some recent results providing a more theoretical grounding for the indeterminism in quantum mechanics. In particular, we show that sequences of quantum random bits are incomputable in the strongest sense: no bit can be provably computed in advance. In Chapter 2 we study in detail the use of von Neumann normalisation for QRNGs producing both finite strings and infinite sequences of bits; such normalisation methods are necessary in order to counter for experimental imperfections. We show that, in the case of a constantly biased source, this normalisation gives the desired uniform distribution. The effect of this normalisation on the (in)computability of the generated sequences is studied, and it is shown that algorithmic randomness and Borel normality are preserved, but e-randomness (and thus incomputability) is, in general, not. Experimental bounds for the extent of departure from the uniform distribution in the non-ideal case of a slowly drifting bias are derived. In Chapter 3 we propose a new QRNG which uses entangled photon pairs and is certified to produce incomputable bits by value indefiniteness; this is the first QRNG with explicit certification by a physical principle. The effects of various experimental imperfections are discussed in detail, and care is taken to make the proposed QRNG as robust as is possible to these. A robust method based on XORing the produced bitstrings together is proposed to further improve the quality of the distribution produced by the QRNG. Various improvements and optimisations to this scheme are discussed.

Our aim is to experimentally study the possibility of distinguishing between quantum sources of randomness--recently proved to be theoretically incomputable--and some well-known computable sources of pseudo-randomness. Incomputability is a necessary, but not sufficient "symptom" of "true randomness". We base our experimental approach on algorithmic information theory which provides characterizations of algorithmic random sequences in terms of the degrees of incompressibility of their finite prefixes. Algorithmic random sequences are incomputable, but the converse implication is false. We have performed tests of randomness on pseudo-random strings (finite sequences) of length

2^{32}

generated with software (Mathematica, Maple), which are cyclic (so, strongly computable), the bits of

π

, which is computable, but not cyclic, and strings produced by quantum measurements (with the commercial device Quantis and by the Vienna IQOQI group). Our empirical tests indicate quantitative differences, some statistically significant, between computable and incomputable sources of "randomness".

Random numbers are required for a variety of applications from secure communications to Monte Carlo simulation. Yet randomness is an asymptotic property, and no output string generated by a physical device can be strictly proven to be random. We report an experimental realization of a quantum random number generator (QRNG) with randomness certified by quantum contextuality and the Kochen-Specker theorem. The certification is not performed in a device-independent way but through a rigorous theoretical proof of each outcome being value indefinite even in the presence of experimental imperfections. The analysis of the generated data confirms the incomputable nature of our QRNG.

We discuss the current state of the art of Quantum Random Number Generators (QRNG) and their possible applications in the search for quantum advantages. To this aim, we first discuss a possible way of benchmarking QRNG by applying them to the computation of complicated and hard to realize classical simulations, such as critical dynamics in two-dimensional Ising lattices. These are performed with the help of computing devices based on field-programmable gate arrays (FPGAs) or graphic processing units (GPUs). The results obtained for QRNG are compared with those obtained by classical pseudo-random number generators (PRNG) of various qualities. Monte Carlo simulations of critical dynamics in moderate lattice sizes (128$\times$128) start to be sensitive to the correlations present in pseudo-random numbers sequences, allowing us to detect them. By comparing our analysis with that of Ref. [PRE {\bf 93}, 022113 (2016)], we estimate the requirements for QRNGs in terms of speed, rapidity of access, and efficiency to achieve the objective of quantum advantage with respect to the best PRNGs. We discuss the technical challenges associated with this objective.

This paper explores the design of cryptographic algorithms leveraging the inherent randomness of quantum random number generators (QRNGs). Traditional cryptographic algorithms often rely on pseudo-random number generators (PRNGs), which are deterministic and therefore vulnerable to attacks if their internal state is compromised. QRNGs, on the other hand, derive their randomness from quantum mechanical phenomena, offering a fundamentally unpredictable source of numbers. This research investigates the application of QRNGs to enhance cryptographic security, focusing on constructing algorithms that exploit this unique property. The core claim is that utilizing QRNG characteristics allows for the design of more secure cryptographic algorithms. The proposed mechanism involves capitalizing on the non-deterministic nature of QRNGs to build algorithms with heightened security levels. This approach presents a novel security guarantee method by incorporating true randomness into cryptographic processes. We examine specific algorithm designs and analyze their security implications compared to traditional PRNG-based approaches. The paper concludes with a discussion on the challenges and future directions of utilizing QRNGs in cryptography.