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

Перейти к навигации Перейти к поиску
Строка 35: Строка 35:
Обозначим за <math>\mathbb{C} [\mathbb{Z}_r]</math> гильбертово пространство функций от <math>\mathbb{Z}_r</math> над полем комплексных чисел. Вычислительный базис <math>\mathbb{C} [\mathbb{Z}_r]</math> состоит из дельта-функций <math>\{ |l \rangle \}_{0 \le l \le r - 1}</math>, где <math>| \rangle</math> – функция, которая обращает элемент <math>l</math> в 1, а остальные элементы <math>\mathbb{Z}_r</math> в 0. Обозначим за <math>QFT_{\mathbb{Z}_r}</math> ''квантовое преобразование Фурье'' над циклической группой <math>\mathbb{Z}_r</math>, определенное как следующий унитарный оператор над <math>\mathbb{C} [\mathbb{Z}_r]</math>:
Обозначим за <math>\mathbb{C} [\mathbb{Z}_r]</math> гильбертово пространство функций от <math>\mathbb{Z}_r</math> над полем комплексных чисел. Вычислительный базис <math>\mathbb{C} [\mathbb{Z}_r]</math> состоит из дельта-функций <math>\{ |l \rangle \}_{0 \le l \le r - 1}</math>, где <math>| \rangle</math> – функция, которая обращает элемент <math>l</math> в 1, а остальные элементы <math>\mathbb{Z}_r</math> в 0. Обозначим за <math>QFT_{\mathbb{Z}_r}</math> ''квантовое преобразование Фурье'' над циклической группой <math>\mathbb{Z}_r</math>, определенное как следующий унитарный оператор над <math>\mathbb{C} [\mathbb{Z}_r]</math>:


<math>QFT_{\mathbb{Z}_r} : |x \rangle \mapsto r^{-1/2} \sum_{y \in \mathbb{Z}_r} e^{-2 \pi i x y/r} |y \rangle</math>.
<math>QFT_{\mathbb{Z}_r} : |x \rangle \mapsto r^{-1/2} \sum_{y \in \mathbb{Z}_r} e^{-2 \pi i x y/r} |y \rangle.</math>




Оно может быть реализовано за квантовое время 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, определим
Он может быть реализован за квантовое время <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) \; \; \; <math>| \hat{l} \rangle := r^{-1/2} \sum_{k = 0}^{r - 1} e^{-2 \pi i l k/r} |a^k \rangle.</math>




Источник — http://pco.iis.nsk.su/wega/index.php/Квантовый_алгоритм_для_решения_задачи_дискретного_логарифмирования