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

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