Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Theoretical Computer Science

How real is incomputability in physics?

José Manuel Agüero Trejo, Cristian S. Calude, Michael J. Dinneen, Arkady Fedorov, Anatoly Kulikov, Rohit Navarathna, Karl Svozil

Published May 14, 2024• 2 citations
Publisher

Abstract

A physical system is determined by a finite set of initial conditions and “laws” represented by equations. The system is computable if we can solve the equations in all instances using a “finite body of mathematical knowledge”. In this case, if the laws of the system can be coded into a computer program, then given the initial conditions of the system, one can compute the system's evolution. Are there incomputable physical systems? This question has been theoretically studied in the last 30–40 years. In this paper, we experimentally show for the first time the strong incomputability of a quantum experiment, namely the outputs of a quantum random number generator. Moreover, the experimental results are robust and statistically significant.

DOI
10.1016/j.tcs.2024.114632

Related papers

How Real is Incomputability in Physics?

José Manuel Agüero Trejo, Cristian S. Calude, Michael J. Dinneen +4 more

A physical system is determined by a finite set of initial conditions and "laws" represented by equations. The system is computable if we can solve the equations in all instances using a "finite body of mathematical knowledge". In this case, if the laws of the system can be coded into a computer program, then given the initial conditions of the system, one can compute the system's evolution. Are there incomputable physical systems? This question has been theoretically studied in the last 30-40 years. In this paper, we experimentally show for the first time the strong incomputability of a quantum experiment, namely the outputs of a quantum random number generator. Moreover, the experimental results are robust and statistically significant.

arXiv:2311.00908•Nov 2, 2023•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

Experimentally probing the algorithmic randomness and incomputability of quantum randomness

Alastair A. Abbott, Cristian S Calude, Michael J Dinneen +1 more

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:1806.08762•Physica Scripta•Nov 23, 2018•28 citations

Quantum random number generators, extraction of provably random bit sequences from Markov chain trajectories

Igor M. Arbekov, S. N. Molotkov

One of the main problems in the construction of quantum random number generators Ð obtainment of a provably random output sequence from physical measurements, i.e., from an initial sequence generated by a physical random number generator Ð is investigated.The conceptual feasibility and the conditions under which randomness can be `reached,' as well as the meaning of the `provable randomness' term, are discussed.We consider the methods of extracting provably random bit sequences from stationary Markov chains of finite order, i.e., under the assumption of the finite depth of the dependence of the results of physical measurements on the prehistory, which is an adequate approximation of the real situation.The extraction of the output provably random bit sequence from the initial sequence of the results of physical measurements using V F Babkin's effective arithmetic coding method is demonstrated.It is shown that random bit sequences can be provably obtained even from primary sequences of the results of physical measurements, which are dependent on (correlated to) any finite depth (prehistory).We aim to reveal the connection of various approximations employed in the development and description of methods for obtaining random bit sequences with the basic physical limitations of Nature.The mathematical proofs are detailed to the level of practical algorithms applied in real random number generators.The necessary mathematical propositions are presented at an intuitive level for physicists, do not require prior knowledge in this area, and are comprehensible to undergraduate university students.

Physics-Uspekhi•Feb 1, 2024•4 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

Experimental evidence of quantum randomness incomputability

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

In contrast with software-generated randomness (called pseudo-randomness), quantum randomness can be proven incomputable; that is, it is not exactly reproducible by any algorithm. We provide experimental evidence of incomputability---an asymptotic property---of quantum randomness by performing finite tests of randomness inspired by algorithmic information theory.

arXiv:1004.1521•Physical Review A•Aug 6, 2010•84 citations
A physical system is determined by a finite set of initial conditions and “laws” represented by equations. The system is computable if we can solve the equations in all instances using a “finite body of mathematical knowledge”. In this case, if the laws of the system can be coded into a computer program, then given the initial conditions of the system, one can compute the system's evolution. Are there incomputable physical systems? This question has been theoretically studied in the last 30–40 years. In this paper, we experimentally show for the first time the strong incomputability of a quantum experiment, namely the outputs of a quantum random number generator. Moreover, the experimental results are robust and statistically significant.
A physical system is determined by a finite set of initial conditions and "laws" represented by equations. The system is computable if we can solve the equations in all instances using a "finite body of mathematical knowledge". In this case, if the laws of the system can be coded into a computer program, then given the initial conditions of the system, one can compute the system's evolution. Are there incomputable physical systems? This question has been theoretically studied in the last 30-40 years. In this paper, we experimentally show for the first time the strong incomputability of a quantum experiment, namely the outputs of a quantum random number generator. Moreover, the experimental results are robust and statistically significant.
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 2322^{32}232 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".
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.
One of the main problems in the construction of quantum random number generators Ð obtainment of a provably random output sequence from physical measurements, i.e., from an initial sequence generated by a physical random number generator Ð is investigated.The conceptual feasibility and the conditions under which randomness can be `reached,' as well as the meaning of the `provable randomness' term, are discussed.We consider the methods of extracting provably random bit sequences from stationary Markov chains of finite order, i.e., under the assumption of the finite depth of the dependence of the results of physical measurements on the prehistory, which is an adequate approximation of the real situation.The extraction of the output provably random bit sequence from the initial sequence of the results of physical measurements using V F Babkin's effective arithmetic coding method is demonstrated.It is shown that random bit sequences can be provably obtained even from primary sequences of the results of physical measurements, which are dependent on (correlated to) any finite depth (prehistory).We aim to reveal the connection of various approximations employed in the development and description of methods for obtaining random bit sequences with the basic physical limitations of Nature.The mathematical proofs are detailed to the level of practical algorithms applied in real random number generators.The necessary mathematical propositions are presented at an intuitive level for physicists, do not require prior knowledge in this area, and are comprehensible to undergraduate university students.
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.