Квантовый алгоритм для решения задачи дискретного логарифмирования: различия между версиями

'''Задача 1 (Дискретное логарифмирование)'''

В ходе своих революционных исследований Шор [9] предложил эффективный квантовый алгоритм для поиска дискретного логарифма в любой группе G; его алгоритм работает за время, полиномиальное относительно размера входных данных в битах.

Алгоритм Шора [9] для решения задачи дискретного логарифмирования использует эффективную квантовую процедуру для реализации унитарного преобразования, известного как квантовое преобразование Фурье. Его исходный алгоритм давал эффективную процедуру выполнения ''квантового преобразования Фурье'' только над группами вида <math>\mathbb{Z}_r</math>, где r – «гладкое» целое число; тем не менее, он показал, что этого достаточно для решения задачи дискретного логарифмирования в общем случае. В данной статье приводится более современное описание алгоритма Шора. В частности, используется результат Хейлз и Холлгрена [5], который показывает, что квантовое преобразование Фурье над любой конечной циклической группой <math>\mathbb{Z}_r</math> может быть эффективно аппроксимировано с обратно-экспоненциальной точностью.

Описание алгоритма приведено ниже. Предполагается знакомство с квантовой нотацией. Достаточное представление о квантовых вычислениях можно найти в книге Нильсена и Чуаня [8]. Пусть <math>(G, a, b, \bar{r})</math> – экземпляр задачи дискретного логарифмирования, где <math>\bar{r}</math> – заданная верхняя граница на порядок a в G. То есть существует положительное целое число <math>r \le \bar{r}</math>, такое, что <math>a^r = 1</math>. Используя эффективный квантовый алгоритм поиска порядка, также разработанный Шором [9], можно предположить, что порядок a в G известен и представляет собой наименьшее положительное целое число r, удовлетворяющее <math>a^r = 1</math>. Время выполнения алгоритма Шора для поиска порядка составляет <math>O((log \; \bar{r})^3)</math>. Пусть <math>\epsilon > 0</math>. Алгоритм дискретного логарифмирования работает на трех регистрах, из которых первые два имеют длину по t кубитов, где <math>t := O(log \; r + log(1 / \epsilon))</math>, а третий регистр достаточно велик, чтобы хранить элемент G. Пусть U обозначает унитарное преобразование <math>U: |x \rangle |y \rangle |z \rangle \mapsto |x |rangle |y \rangle |z \bigoplus (b^x \; a^y) \rangle</math>, где <math>\bigoplus</math> обозначает побитовое исключающее ИЛИ. Если имеется доступ к обратимому оракулу для групповых операций в G, U может быть реализовано обратимо за время <math>O(t^3)</math> путем многократного возведения в квадрат.