4501
правка
Квантовый алгоритм для решения задачи дискретного логарифмирования: различия между версиями
Материал из WEGA
Квантовый алгоритм для решения задачи дискретного логарифмирования (посмотреть исходный код)
Версия от 19:46, 15 января 2023
, 15 января 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 48: | Строка 48: | ||
'''Алгоритм 1 (Дискретное логарифмирование)''' | '''Алгоритм 1 (Дискретное логарифмирование)''' | ||
Дано: элементы a | Дано: элементы <math>a, b \in G</math>, квантовая схема для U, порядок r для a в G. | ||
Требуется: найти с постоянной вероятностью дискретный логарифм s от b по основанию a в G. | Требуется: найти с постоянной вероятностью дискретный логарифм s от b по основанию a в G. | ||
Время выполнения: суммарно O( | Время выполнения: суммарно <math>O(t^3)</math> базовых вентильных операций, включая четыре вызова <math>QFT_{\mathbb{Z}_r}</math> и один вызов U. | ||
'''Процедура:''' | '''Процедура:''' | ||
1. Повторить шаги (a) | |||
(a) | 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) | |||
(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> к первым двум регистрам; | Применить <math>QFT_{\mathbb{Z}_r}</math> к первым двум регистрам; | ||
(c) | (c) | ||
