4446
правок
Квантовый алгоритм для решения задачи дискретного логарифмирования: различия между версиями
Материал из WEGA
Квантовый алгоритм для решения задачи дискретного логарифмирования (посмотреть исходный код)
Версия от 15:05, 15 января 2023
, 15 января 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 36: | Строка 36: | ||
Оно может быть реализовано за квантовое время O(flog(f/e) + Iog2(l/e)) с точностью до ошибки e с использованием одного т-кубитного регистра [5. Заметим, что для любого k 2 Zr; | Оно может быть реализовано за квантовое время O(flog(f/e) + Iog2(l/e)) с точностью до ошибки e с использованием одного т-кубитного регистра [5. Заметим, что для любого k 2 Zr; <math>QFT_{\mathbb{Z}_r}</math> преобразует состояние r~m J2xeZr e27Zikxlr\x) в состояние jki. Для любого целого числа l; 0 < l < r - 1, определим | ||
| Строка 48: | Строка 48: | ||
Требуется: найти с постоянной вероятностью дискретный логарифм s от b по основанию a в G. | Требуется: найти с постоянной вероятностью дискретный логарифм s от b по основанию a в G. | ||
Время выполнения: суммарно O(t3) базовых вентильных операций, включая четыре вызова | Время выполнения: суммарно O(t3) базовых вентильных операций, включая четыре вызова <math>QFT_{\mathbb{Z}_r}</math> и один вызов U. | ||
| Строка 56: | Строка 56: | ||
Инициализация; | Инициализация; | ||
(b) | (b) | ||
Применить | Применить <math>QFT_{\mathbb{Z}_r}</math> к первым двум регистрам; | ||
(c) | (c) | ||
Применить U | Применить U | ||
(d) | (d) | ||
Применить | Применить <math>QFT_{\mathbb{Z}_r}</math> к первым двум регистрам; | ||
(e) 7! (sl mod r; l) | (e) 7! (sl mod r; l) | ||
Измерить первые два регистра; | Измерить первые два регистра; | ||
| Строка 74: | Строка 74: | ||
Применение | Применение <math>QFT_{\mathbb{Z}_r}</math> к первым двум регистрам дает состояние вышеприведенного алгоритма на шаге 1(d). Измерение первых двух регистров дает (sl mod r; l) для равномерно распределенного l; 0 < l < r - 1 на шаге 1(e). С помощью элементарной теории чисел можно показать, что если целые числа l\, h равномерно и независимо выбраны между 0 и 1-1, то они будут совпадать с постоянной вероятностью. В этом случае найдутся целые числа k1, k2 такие, что k1 l1 + k2 l2 = 1, что приведет к нахождению дискретного логарифма s на шаге 3 алгоритма с постоянной вероятностью. Поскольку фактически можно применить только e-приближенную версию <math>QFT_{\mathbb{Z}_r}</math>, можно задать e достаточно малой константой, и это все равно даст правильный дискретный логарифм s на шаге 3 алгоритма с постоянной вероятностью. Вероятность успеха алгоритма Шора для задачи дискретного логарифма можно увеличить по крайней мере до 3/4, повторив его постоянное число раз. | ||
