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

Оно может быть реализовано за квантовое время O(flog(f/e) + Iog2(l/e)) с точностью до ошибки e с использованием одного т-кубитного регистра [5. Заметим, что для любого k 2 Zr; QFTZr преобразует состояние r~m J2xeZr e27Zikxlr\x) в состояние jki. Для любого целого числа l; 0 < l < r - 1, определим

Время выполнения: суммарно O(t3) базовых вентильных операций, включая четыре вызова QFTZr и один вызов U.

Применить QFTZ к первым двум регистрам;

Применить QFTZ к первым двум регистрам;

Применение QFTZr к первым двум регистрам дает состояние вышеприведенного алгоритма на шаге 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-приближенную версию QFTZr, можно задать e достаточно малой константой, и это все равно даст правильный дискретный логарифм s на шаге 3 алгоритма с постоянной вероятностью. Вероятность успеха алгоритма Шора для задачи дискретного логарифма можно увеличить по крайней мере до 3/4, повторив его постоянное число раз.