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} ^{a }Academy of Cryptography of the Russian Federation, PO Box 100, Moscow, 119331, Russian Federation ^{b }Osipyan Institute of Solid State Physics, Russian Academy of Sciences, Akademika Osip'yana str. 2, Chernogolovka, Moscow Region, 142432, Russian Federation ^{c }Faculty of Computational Mathematics and Cybernetics of Lomonosov Moscow State University, Leninskie Gory 1, build. 52, Moscow, 119991, Russian Federation ^{d }Quantum Technology Center of Lomonosov Moscow State University, Leninskie Gory 1, build. 35, Moscow, 119991, Russian Federation

The paper investigates one of the main problems in the construction of quantum
random number generators — obtaining a provably random
output sequence from the results of physical measurements
— the initial sequence generated by a physical
random number generator. The questions of the fundamental
possibility and the conditions under which it is possible to "reach out" to randomness,
as well as what is meant by provable randomness, are discussed.
Methods of extraction of provably random bit sequences
from stationary Markov chains of finite order are considered, i.e. under the assumption
on the ultimate depth of dependence of the results of physical measurements on
prehistory, which is an adequate approximation to the real situation.
The extraction of the output provably random
bit sequence from the initial sequence
of physical measurement results using the effective
arithmetic coding method of V.F. Babkin is demonstrated. It is shown that even from the primary
sequences of the results of physical measurements, which are
dependent (correlated) to any finite depth (prehistory),
it is possible to provably obtain random bit sequences. The goal
set by the authors was to show the connection of various
approximations that are used in the development and description of methods
for obtaining random bit sequences with fundamental
physical limitations of Nature. The mathematical proofs are brought
to practical algorithms that are used in real
random number generators. The necessary mathematical proofs are presented
at an intuitive level for the physical audience, they do not require
prior specialized knowledge and are available to undergraduate
university students.

Keywords: quantum random number generators, Markov chains, random bit sequences DOI:10.3367/UFNe.2024.02.039658 Citation: Arbekov I M, Molotkov S N "Quantum random number generators, extraction of provably random bit sequences from Markov chain trajectories" Phys. Usp., accepted

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