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

I.M. Arbekov^†^a, S.N. Molotkov^‡^{a, b, c, d}
^aAcademy of Cryptography of the Russian Federation, PO Box 100, Moscow, 119331, Russian Federation
^bOsipyan Institute of Solid State Physics, Russian Academy of Sciences, Akademika Osip'yana str. 2, Chernogolovka, Moscow Region, 142432, Russian Federation
^cFaculty of Computational Mathematics and Cybernetics of Lomonosov Moscow State University, Leninskie Gory 1, build. 52, Moscow, 119991, Russian Federation
^dQuantum Technology Center of Lomonosov Moscow State University, Leninskie Gory 1, build. 35, Moscow, 119991, Russian Federation

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.

Keywords: quantum random number generators, Markov chains, random bit sequences
PACS: 02.50.−r, 03.67.−a, 42.50.Ex (all)
DOI: 10.3367/UFNe.2024.02.039658
URL: https://ufn.ru/en/articles/2024/9/h/
Web of Science

001343554500006
Scopus

2-s2.0-85193290439
ADS NASA

2024PhyU...67..919A
Citation: Arbekov I M, Molotkov S N "Quantum random number generators, extraction of provably random bit sequences from Markov chain trajectories" Phys. Usp. 67 919–937 (2024)

BibTexBibNote ® (generic)BibNote ® (RIS)MedlineRefWorks

Received: 25th, December 2023, revised: 20th, February 2024, accepted: 27th, February 2024

Оригинал: Арбеков И М, Молотков С Н «Квантовые генераторы случайных чисел, экстракция доказуемо случайных битовых последовательностей из траекторий цепи Маркова» УФН 194 974–993 (2024); DOI: 10.3367/UFNr.2024.02.039658