Квантовый алгоритм для решения задачи дискретного логарифмирования: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 40: | Строка 40: | ||
Он может быть реализован за квантовое время <math>O(t \; log(t/ \epsilon) + log^2(1/ \epsilon))</math> с точностью до ошибки <math>\epsilon</math> с использованием одного t-кубитного регистра [5]. Заметим, что для любого <math>k \in \mathbb{Z}_r</math> оператор <math>QFT_{\mathbb{Z}_r}</math> преобразует состояние <math>r^{-1/2} \sum_{x \in \mathbb{Z}_r} e^{2 \pi i k x/r} |x \rangle</math> в состояние <math>|k \rangle</math>. Для любого целого числа <math>l, 0 \le l \le r - 1</math>, определим | Он может быть реализован за квантовое время <math>O(t \; log(t/ \epsilon) + log^2(1/ \epsilon))</math> с точностью до ошибки <math>\epsilon</math> с использованием одного t-кубитного регистра [5]. Заметим, что для любого <math>k \in \mathbb{Z}_r</math> оператор <math>QFT_{\mathbb{Z}_r}</math> преобразует состояние <math>r^{-1/2} \sum_{x \in \mathbb{Z}_r} e^{2 \pi i k x/r} |x \rangle</math> в состояние <math>|k \rangle</math>. Для любого целого числа <math>l, 0 \le l \le r - 1</math>, определим | ||
(1) \; \; | (1) <math> \; \; | \hat{l} \rangle := r^{-1/2} \sum_{k = 0}^{r - 1} e^{-2 \pi i l k/r} |a^k \rangle.</math> | ||
Заметим, что {| | Заметим, что <math>\{ | \hat{l} \rangle \}_{0 \le l \le r - 1}</math> образует ортонормальный базис <math>\mathbb{C} [ \langle a \rangle ]</math>, где <math>\langle a \rangle</math> – подгруппа, порожденная a в G и изоморфная <math>\mathbb{Z}_r</math>, а <math>\mathbb{C} [ \langle a \rangle ]</math> обозначает гильбертово пространство функций от <math>\langle a \rangle</math> над полем комплексных чисел. | ||