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

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.