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

Описание алгоритма приведено ниже. Предполагается знакомство с квантовой нотацией. Достаточное представление о квантовых вычислениях можно найти в книге Нильсена и Чуаня [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 \to |x |rangle |y \rangle |z \cdot (b^x \; a^y) \rangle</math>, где ф обозначает побитовое исключающее ИЛИ. Если имеется доступ к обратимому оракулу для групповых операций в G, U может быть реализовано обратимо за время O(t3) путем многократного возведения в квадрат.

Пусть C [Zr] обозначает гильбертово пространство функций от Zr до комплексных чисел. Вычислительный базис C[Zr] состоит из дельта-функций {|l)}o</<r-i, где |) – функция, которая обращает элемент l в 1, а остальные элементы Zr в 0. Обозначим за QFTZr квантовое преобразование Фурье над циклической группой Zr, определенное как следующий унитарный оператор на C [Zr]: