Квантовые генераторы случайных чисел, экстракция доказуемо случайных битовых последовательностей из траекторий цепи Маркова

И.М. Арбеков^†^а, С.Н. Молотков^‡^{а, б, в, г}
^аАкадемия криптографии Российской Федерации, а/я 100, Москва, 119331, Российская Федерация
^бИнститут физики твердого тела имени Ю.А. Осипьяна РАН, ул. Академика Осипьяна 2, Черноголовка, Московская обл., 142432, Российская Федерация
^вФакультет вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова, Ленинские горы д. 1, стр. 52, Москва, 119991, Российская Федерация
^гЦентр квантовых технологий Московского государственного университета имени М.В. Ломоносова, Ленинские горы 1, стр. 35, Москва, 119991, Российская Федерация

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

Текст pdf (464 Кб)

Скачивая файл я соглашаюсь с условиями использования.

English fulltext is available at DOI: 10.3367/UFNe.2024.02.039658

Ключевые слова: квантовые генераторы случайных чисел, цепи Маркова, случайные битовые последовательности
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/
Web of Science

001343554500006
ADS NASA

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