4501
правка
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
Строка 30: | Строка 30: | ||
Описание алгоритма приведено ниже. Предполагается знакомство с квантовой нотацией. Достаточное представление о квантовых вычислениях можно найти в книге Нильсена и Чуаня [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 \ | Описание алгоритма приведено ниже. Предполагается знакомство с квантовой нотацией. Достаточное представление о квантовых вычислениях можно найти в книге Нильсена и Чуаня [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> путем многократного возведения в квадрат. | ||
Обозначим за <math>\mathbb{C} [\mathbb{Z}_r]</math> гильбертово пространство функций от <math>\mathbb{Z}_r</math> над полем комплексных чисел. Вычислительный базис <math>\mathbb{C} [\mathbb{Z}_r]</math> состоит из дельта-функций <math>\{ |l \rangle \}_{0 \le l \le r - 1}</math>, где <math>| \rangle</math> – функция, которая обращает элемент <math>l</math> в 1, а остальные элементы <math>\mathbb{Z}_r</math> в 0. Обозначим за <math>QFT_{\mathbb{Z}_r}</math> ''квантовое преобразование Фурье'' над циклической группой <math>\mathbb{Z}_r</math>, определенное как следующий унитарный оператор над <math>\mathbb{C} [\mathbb{Z}_r]</math>: | Обозначим за <math>\mathbb{C} [\mathbb{Z}_r]</math> гильбертово пространство функций от <math>\mathbb{Z}_r</math> над полем комплексных чисел. Вычислительный базис <math>\mathbb{C} [\mathbb{Z}_r]</math> состоит из дельта-функций <math>\{ |l \rangle \}_{0 \le l \le r - 1}</math>, где <math>| \rangle</math> – функция, которая обращает элемент <math>l</math> в 1, а остальные элементы <math>\mathbb{Z}_r</math> в 0. Обозначим за <math>QFT_{\mathbb{Z}_r}</math> ''квантовое преобразование Фурье'' над циклической группой <math>\mathbb{Z}_r</math>, определенное как следующий унитарный оператор над <math>\mathbb{C} [\mathbb{Z}_r]</math>: | ||
<math>QFT_{\mathbb{Z}_r} : |x \rangle \mapsto r^{-1/2} \sum_{y \in \mathbb{Z}_r} e^{-2 \pi i x y/r} |y \rangle</math>. | |||
правка