Abstract The nature of randomness and constructive and provable methods to obtain (extract) it from observations of physical systems are discussed. True randomness, which exists only in a microcosm in the quantum-mechanical description of physical systems, is a fundamental property of quantum systems, which manifests itself in the outcomes of measurements upon quantum systems. The classical description of physical systems does not include any randomness and, in fact, it is introduced ‘manually’ by means of uncertainty — unknown initial conditions. Methods to really ‘feel’ quantum randomness are discussed using the example of a quantum device, a random number generator. Issues related to the ‘proof’ of randomness — testing of numerical sequences — are reviewed, and logical constructions that underlie such testing are analyzed. A mathematical apparatus is used to this end, which does not require special academic training, so standard knowledge from university courses on quantum mechanics and probability theory is sufficient. The authors aim to track a unified logical path from the origin of randomness in the quantum domain to its extraction, physical implementation, and testing.
Abstract The nature of randomness and constructive and provable methods to obtain (extract) it from observations of physical systems are discussed. True randomness, which exists only in a microcosm in the quantum-mechanical description of physical systems, is a fundamental property of quantum systems, which manifests itself in the outcomes of measurements upon quantum systems. The classical description of physical systems does not include any randomness and, in fact, it is introduced ‘manually’ by means of uncertainty — unknown initial conditions. Methods to really ‘feel’ quantum randomness are discussed using the example of a quantum device, a random number generator. Issues related to the ‘proof’ of randomness — testing of numerical sequences — are reviewed, and logical constructions that underlie such testing are analyzed. A mathematical apparatus is used to this end, which does not require special academic training, so standard knowledge from university courses on quantum mechanics and probability theory is sufficient. The authors aim to track a unified logical path from the origin of randomness in the quantum domain to its extraction, physical implementation, and testing.
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.
Pseudo-random number generators are widely used in many branches of science, mainly in applications related to Monte Carlo methods, although they are deterministic in design and, therefore, unsuitable for tackling fundamental problems in security and cryptography. The natural laws of the microscopic realm provide a fairly simple method to generate non-deterministic sequences of random numbers, based on measurements of quantum states. In practice, however, the experimental devices on which quantum random number generators are based are often unable to pass some tests of randomness. In this review, we briefly discuss two such tests, point out the challenges that we have encountered and finally present a fairly simple method that successfully generates non-deterministic maximally random sequences.
Abstract This is a review of the issue of randomness in quantum mechanics, with special emphasis on its ambiguity; for example, randomness has different antipodal relationships to determinism, computability, and compressibility. Following a (Wittgensteinian) philosophical discussion of randomness in general, I argue that deterministic interpretations of quantum mechanics (like Bohmian mechanics or ’t Hooft’s Cellular Automaton interpretation) are strictly speaking incompatible with the Born rule. I also stress the role of outliers, i.e. measurement outcomes that are not 1-random. Although these occur with low (or even zero) probability, their very existence implies that the no-signaling principle used in proofs of randomness of outcomes of quantum-mechanical measurements (and of the safety of quantum cryptography) should be reinterpreted statistically, like the second law of thermodynamics. In three appendices I discuss the Born rule and its status in both single and repeated experiments, review the notion of 1-randomness (or algorithmic randomness) that in various guises was investigated by Kolmogorov and others and treat Bell’s (Physics 1:195–200, 1964) Theorem and the Free Will Theorem with their implications for randomness.
Abstract Quantum physics can be exploited to generate true random numbers, which have important roles in many applications, especially in cryptography. Genuine randomness from the measurement of a quantum system reveals the inherent nature of quantumness—coherence, an important feature that differentiates quantum mechanics from classical physics. The generation of genuine randomness is generally considered impossible with only classical means. On the basis of the degree of trustworthiness on devices, quantum random number generators (QRNGs) can be grouped into three categories. The first category, practical QRNG, is built on fully trusted and calibrated devices and typically can generate randomness at a high speed by properly modelling the devices. The second category is self-testing QRNG, in which verifiable randomness can be generated without trusting the actual implementation. The third category, semi-self-testing QRNG, is an intermediate category that provides a tradeoff between the trustworthiness on the device and the random number generation speed.
Random number generators are indispensable for a multi- tude of tasks; from electronic games to secure communications. Most gen- erators have been made either in software or determinist hardwired de- vices such as the Linear-Feedback-Shift-Registers; while gaining in costs or speed, the “random” sequences generated are actually deterministic, obeying clear generating algorithms, despite all randomness appearance of their outputs. From the other side, Nature presents a multitude of sources of true randomness that can be explored. Commercial random generators exist based on physical processes as the source of randomness. Difficulties are always present to extract Nature’s randomness. This paper presents guidelines for construction of a fast (telecommunication speed) Physical Random Number Generator. It discusses the fundamental physical ele- ments involved, technicalities of signal recording and its limitations, and the final bit extraction. The need for randomness tests is emphasized and the impossibility of guaranteeing true randomness of a finite sequence is discussed.
Generating random bits is a difficult task, which is important for physical systems simulation, cryptography, and many applications that rely on high-quality random bits. Our contribution is to show how to generate provably random bits from uncertain events whose outcomes are routinely recorded in the form of massive data sets. These include scientific data sets, such as in astronomics, genomics, as well as data produced by individuals, such as internet search logs, sensor networks, and social network feeds. We view the generation of such data as the sampling process from a big source, which is a random variable of size at least a few gigabytes. Our view initiates the study of big sources in the randomness extraction literature. Previous approaches for big sources rely on statistical assumptions about the samples. We introduce a general method that provably extracts almost-uniform random bits from big sources and extensively validate it empirically on real data sets. The experimental findings indicate that our method is efficient enough to handle large enough sources, while previous extractor constructions are not efficient enough to be practical. Quality-wise, our method at least matches quantum randomness expanders and classical world empirical extractors as measured by standardized tests.