4446
правок
Квантовый алгоритм для решения задачи дискретного логарифмирования: различия между версиями
Материал из WEGA
Квантовый алгоритм для решения задачи дискретного логарифмирования (посмотреть исходный код)
Версия от 00:15, 16 января 2023
, 16 января 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 54: | Строка 54: | ||
Время выполнения: суммарно <math>O(t^3)</math> базовых вентильных операций, включая четыре вызова <math>QFT_{\mathbb{Z}_r}</math> и один вызов U. | Время выполнения: суммарно <math>O(t^3)</math> базовых вентильных операций, включая четыре вызова <math>QFT_{\mathbb{Z}_r}</math> и один вызов U. | ||
'''Процедура:''' | |||
1. Повторить шаги (a)–(e) дважды, получив <math>(sl_1</math> mod r, <math>l_1)</math> и <math>(sl_2</math> mod r, <math>l_2)</math>. | |||
(a) <math>|0 \rangle |0 \rangle |0 \rangle</math> | |||
Инициализация; | |||
(b) <math> \mapsto r^{-1} \sum_{x, y \in \mathbb{Z}_r} |x \rangle |y \rangle |0 \rangle</math> | |||
Применить <math>QFT_{\mathbb{Z}_r}</math> к первым двум регистрам; | |||
(c) <math> \mapsto r^{-1} \sum_{x, y \in \mathbb{Z}_r} |x \rangle |y \rangle |b^x a^y \rangle</math> | |||
Применить U | |||
(d) <math> \mapsto r^{-1/2} \sum_{l = 0}^{r - 1} |sl mod r \rangle |l \rangle |\hat{l} \rangle</math> | |||
Применить <math>QFT_{\mathbb{Z}_r}</math> к первым двум регистрам; | |||
(e) <math> \mapsto</math> (sl mod r, l) | |||
Измерить первые два регистра; | |||
2. Если <math>l_1</math> не совпадает с <math>l_2</math>, прервать вычисление. | |||
3. Пусть <math>k_1, k_2</math> - целые числа, такие, что <math>k_1 l_1 + k_2 l_2 = 1</math>. Вывести <math>s = k_1(sl_1) + k_2(sl_2) mod r</math>. | |||
Работа алгоритма поясняется ниже. Из равенства (1) легко увидеть, что <math>|b^x a^y \rangle = r^{-1/2} \sum_{l = 0}^{r - 1} e^{2 \pi i l (sx + y)/r} | \hat{l} \rangle </math>. | |||
Таким образом, состояние приведенного выше алгоритма на шаге 1(c) можно записать как <math>r^{-1} \sum_{x, y \in \mathbb{Z}_r} |x \rangle |y \rangle |b^x a^y \rangle = r^{-3/2} \sum_{l = 0}^{r - 1} \sum_{x, y \in \mathbb{Z}_r} e^{2 \pi i l (sx + y)/r} |x \rangle |y \rangle | \hat{l} \rangle</math>. | |||
( | |||
( | |||
