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

Квантовый алгоритм для решения задачи дискретного логарифмирования (посмотреть исходный код)

Версия от 00:15, 16 января 2023

406 байт добавлено , 16 января 2023

→‎Основные результаты

Irina

4501

правка

@@ Строка 54: / Строка 54: @@
 Время выполнения: суммарно <math>O(t^3)</math> базовых вентильных операций, включая четыре вызова <math>QFT_{\mathbb{Z}_r}</math> и один вызов U.
+   '''Процедура:'''
+. Повторить шаги (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)
+   Измерить первые два регистра;
+. Если <math>l_1</math> не совпадает с <math>l_2</math>, прервать вычисление.
+. Пусть <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>.
-'''Процедура:'''
-. Повторить шаги (a)–(e) дважды, получив <math>(sl_1</math> mod r, <math>l_1)</math> и <math>(sl_2</math> mod r, <math>l_2)</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>.
-(a) <math>|0 \rangle |0 \rangle |0 \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>.
-(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)
-Измерить первые два регистра;
-. Если <math>l_1</math> не совпадает с <math>l_2</math>, прервать вычисление.
-. Пусть <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(c) можно записать как

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

Квантовый алгоритм для решения задачи дискретного логарифмирования (посмотреть исходный код)

Версия от 00:15, 16 января 2023

Навигация

Поиск