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

arXiv:2311.00908

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 Nov 2, 2023• 0 citations
arXivHTMLPDF

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.48550/arxiv.2311.00908

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.

Theoretical Computer Science•May 14, 2024•2 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

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 Information Theory

Kazuyuki Fujii

What are the information processing capabilities of physical systems?As recently as the first half of the 20 th century this question did not even have a definite meaning.What is information, and how would one process it?It took the development of theories of computing (in the 1930s) and information (late in the 1940s) for us to formulate mathematically what it means to compute or communicate.Yet these theories were abstract, based on axiomatic mathematics: what did physical systems have to do with these axioms?Rolf Landauer had the essential insight -"Information is physical" -that information is always encoded in the state of a physical system, whose dynamics on a microscopic level are well-described by quantum physics.This means that we cannot discuss information without discussing how it is represented, and how nature dictates it should behave.Wigner considered the situation from another perspective when he wrote about "the unreasonable effectiveness of mathematics in the natural sciences".Why are the computational techniques of mathematics so astonishingly useful in describing the physical world [1]?One might begin to suspect foul play in the universe's operating principles.Interesting insights into the physics of information accumulated through the 1970s and 1980s -most sensationally in the proposal for a "quantum computer".If we were to mark a particular year in which an explosion of interest took place in information physics, that year would have to be 1994, when Shor showed that a problem of practical interest (factorisation of integers) could be solved easily on a quantum computer.But the applications of information in physics -and vice versa -have been far more widespread than this popular discovery.These applications range from improved experimental technology, more sophisticated measurement techniques, methods for characterising the quantum/classical boundary, tools for quantum chaos, and deeper insight into quantum theory and nature.In this thesis I present a short review of ideas in quantum information theory.The first chapter contains introductory material, sketching the central ideas of probability and information theory.Quantum mechanics is presented at the level of advanced undergraduate knowledge, together with some useful tools for quantum mechanics of open systems.In the second chapter I outline how classical information is represented in quantum systems and what this means for agents trying to extract information from these systems.The final chapter presents a new resource: quantum information.This resource has some bewildering applications which have been discovered in the last ten years, and continually presents us with unexpected insights into quantum theory and the universe.ii This thesis is dedicated to my mother.iii This thesis was begun as an intrepid adventure.It caught

Institute of Electrical and Electronics Engineers eBooks•Jan 1, 2009•533 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

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
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".
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.
What are the information processing capabilities of physical systems?As recently as the first half of the 20 th century this question did not even have a definite meaning.What is information, and how would one process it?It took the development of theories of computing (in the 1930s) and information (late in the 1940s) for us to formulate mathematically what it means to compute or communicate.Yet these theories were abstract, based on axiomatic mathematics: what did physical systems have to do with these axioms?Rolf Landauer had the essential insight -"Information is physical" -that information is always encoded in the state of a physical system, whose dynamics on a microscopic level are well-described by quantum physics.This means that we cannot discuss information without discussing how it is represented, and how nature dictates it should behave.Wigner considered the situation from another perspective when he wrote about "the unreasonable effectiveness of mathematics in the natural sciences".Why are the computational techniques of mathematics so astonishingly useful in describing the physical world [1]?One might begin to suspect foul play in the universe's operating principles.Interesting insights into the physics of information accumulated through the 1970s and 1980s -most sensationally in the proposal for a "quantum computer".If we were to mark a particular year in which an explosion of interest took place in information physics, that year would have to be 1994, when Shor showed that a problem of practical interest (factorisation of integers) could be solved easily on a quantum computer.But the applications of information in physics -and vice versa -have been far more widespread than this popular discovery.These applications range from improved experimental technology, more sophisticated measurement techniques, methods for characterising the quantum/classical boundary, tools for quantum chaos, and deeper insight into quantum theory and nature.In this thesis I present a short review of ideas in quantum information theory.The first chapter contains introductory material, sketching the central ideas of probability and information theory.Quantum mechanics is presented at the level of advanced undergraduate knowledge, together with some useful tools for quantum mechanics of open systems.In the second chapter I outline how classical information is represented in quantum systems and what this means for agents trying to extract information from these systems.The final chapter presents a new resource: quantum information.This resource has some bewildering applications which have been discovered in the last ten years, and continually presents us with unexpected insights into quantum theory and the universe.ii This thesis is dedicated to my mother.iii This thesis was begun as an intrepid adventure.It caught
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.