Исследуется одна из главных проблем в построении квантовых генераторов случайных чисел — получение доказуемо случайной выходной последовательности из результатов физических измерений — исходной последовательности, вырабатываемой физическим генератором случайных чисел. Обсуждаются вопросы о принципиальной возможности и условиях, при которых можно "дотянуться" до случайности, а также то, что понимать под доказуемой случайностью. Рассмотрены методы экстракции доказуемо случайных битовых последовательностей из стационарных цепей Маркова конечного порядка, т.е. в предположении о конечной глубине зависимости результатов физических измерений от предыстории, которое является адекватным приближением к реальной ситуации. Продемонстрировано извлечение выходной доказуемо случайной битовой последовательности из исходной последовательности результатов физических измерений с использованием эффективного метода арифметического кодирования В.Ф. Бабкина. Показано, что даже из первичных последовательностей результатов физических измерений, которые являются зависимыми (коррелированными) на любую конечную глубину (предысторию), можно доказуемо получать случайные битовые последовательности. Цель, которую ставили перед собой авторы, — показать связь различных приближений, которые используются при разработке и описании методов получения случайных битовых последовательностей с фундаментальными физическими ограничениями Природы. Математические доказательства доведены до практических алгоритмов, которые используются в реальных генераторах случайных чисел. Необходимые математические доказательства приводятся на интуитивно понятном для физической аудитории уровне, не требуют предварительных специальных знаний и доступны студентам старших курсов университетов.

Ключевые слова: квантовые генераторы случайных чисел, цепи Маркова, случайные битовые последовательности PACS: 02.50.−r, 03.67.−a, 42.50.Ex (все) DOI: 10.3367/UFNr.2024.02.039658 URL: https://ufn.ru/ru/articles/2024/9/g/ 001343554500006 2024PhyU...67..919A Цитата: Арбеков И М, Молотков С Н "Квантовые генераторы случайных чисел, экстракция доказуемо случайных битовых последовательностей из траекторий цепи Маркова" УФН 194 974–993 (2024) BibTexBibNote ® (generic)BibNote ® (RIS)MedlineRefWorks Поступила: 25 декабря 2023, доработана: 20 февраля 2024, одобрена в печать: 27 февраля 2024 English 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); DOI: 10.3367/UFNe.2024.02.039658