Еще с доевклидовых времен известно, что любое целое число $n$ может быть однозначно представлено в виде произведения простых чисел. Математики тоже начали исследовать вопрос о том, как разложить число на простые множители немногим позже. Однако, только в 70 -е годы они внедрили парадигмы вычислительной математики в теорию чисел и обнаружили, какое время асимптотически требуют алгоритмы факторизации [Adleman, 1994]. Этот результат чрезвычайно важен для изучения эффективности факторизационных алгоритмов. Наилучший факторизационный алгоритм [Lenstra et al., 1990, Lenstra and Lenstra, 1993] тратит на представление числа в виде простых множителей асимптотически $\exp \left(c(\log n)^{1 / 3}(\log \log n)^{2 / 3}\right)$ шагов при любой константе $c$. В силу того, что входные данные, число $n$, длиной только $\log n$ бит, этот алгоритм является экспоненциальным по времени. Наш квантовый факторизационный алгоритм требует асимптотически $O\left((\log n)^{2}(\log \log n)(\log \log \log n)\right)$ шагов квантового компьютера, вместе с полиномиальным (в единицах $\log n$ ) количеством постпроцедурных шагов классического компьютера, необходимых для конвертации выходных данных квантового компьютера в факторы числа $n$. Конечно, такие постпроцедурные шаги можно было бы осуществить и на квантовом компьютере, но нет причин не использовать классический компьютер, если он для этой задачи более эффективен.

Вместо того чтобы дать напрямую алгоритм факторизации числа $n$ для квантового компьютера, мы предложим алгоритм нахождения на квантовом компьютере порядка $r$ числа $x$ в мультипликативной группе вычетов по $\bmod n$; другими словами, нахождения наименьшего целого числа $r$ такого, что $x^{r} \equiv 1(\bmod n)$. Как известно, используя рандомизацию, разложение на простые множители может быть сведено к задаче о нахождении такого порядка [Miller, 1976]. Сейчас мы коротко опишем эту процедуру.
Для разложения нечетного числа $n$ на простые множители используется алгоритм нахождения порядка $r$ числа $x$. Выберем произвольное число $x(\bmod n)$, найдем его порядок $r$ и вычислим $\operatorname{gcd}\left(x^{r / 2}-1, n\right)$. Здесь $\operatorname{gcd}(a, b)$ – наибольший общий делитель чисел $a$ и $b$, то есть наибольшее целое число, на которое нацело можно разделить и $a$, и $b$. Алгоритм Евклида [Knuth, 1981], который может быть использован при вычислении $\operatorname{gcd}(a, b)$, полиномиален по времени. Так как $\left(x^{r / 2}-1\right)\left(x^{r / 2}+1\right)=x^{r}-1 \equiv 0(\bmod n), \operatorname{gcd}\left(x^{r / 2}-1, n\right)$ оказывается нетривиальным делителем числа $n$, только если $r$ является нечетным, иначе $x^{r / 2} \equiv-1(\bmod n)$ и получаются лишь тривиальные множители 1 и $n$. Используя этот критерий, можно показать, что эта процедура, использующая произвольные числа $x(\bmod n)$, приводит к нахождению множителя $n$ с вероятностью не менее $1-1 / 2^{k-1}$, где $k$ – число различных нечетных факторов числа $n$. Коротко рассмотрим доказательство этого факта.

Предположим, что $n=\prod_{i=1}^{k} p_{i}^{a_{i}}$. Пусть $r_{i}$ – порядок числа $x$ $\left(\bmod p_{i}^{a_{i}}\right)$. Тогда $r$ есть наименьшее общее кратное всех $r_{i}$. Рассмотрим наивысшую степень 2 , на которую делятся все $r_{i}$. Алгоритм не работает только тогда, когда эти степени 2 согласованы: если все они равны 1 , тогда $r$ – нечетное и $r / 2$ не существует; если они все равны друг другу и больше 1 , тогда $x^{r / 2} \equiv-1(\bmod n)$, так как $x^{r / 2} \equiv-1\left(\bmod p_{i}^{\alpha_{i}}\right)$ для любого $i$. В силу Китайской теоремы об остатке [Knuth, 1981, Hardy and Wright, 1979, Теорема 121], случайный выбор $x(\bmod n)$ есть тоже самое, что случайный выбор для каждого $i$ числа $x_{i}\left(\bmod p_{i}^{a_{i}}\right)$, где $x \equiv x_{i}$ $\left(\bmod p_{i}^{a_{i}}\right)$. Мультипликативная группа вычетов по $\left(\bmod p^{\alpha}\right)$ для любой нечетной степени $p^{\alpha}$ является циклической [Knuth, 1981], таким образом, для любой нечетной простой степени $p_{i}^{a_{i}}$ имеется вероятность не более $1 / 2$ того, что выбор $x_{i}$ имеет любую частную степень двойки как наибольший делитель этого порядка $r_{i}$. Поэтому каждая такая степень 2 обладает не более, чем $50 \%$ вероятностью в согласии с предыдущей, таким образом, все $k$ из них согласуются с вероятностью более $1 / 2^{k-1}$, и имеет место не менее $1-1 / 2^{k-1}$ вероятности того, что $x$ мы выбрали правильно. Поэтому такая схема будет работать, пока $n-$ нечетное число и не является простой степенью. Нахождение факторов для простых степеней – задача эффективно решаемая классическими методами.
Теперь мы опишем алгоритм нахождения порядка $x(\bmod n)$ на квантовом компьютере. Этот алгоритм использует два квантовых регистра, в которых содержатся целые числа в бинарном представлении. Также нам еще понадобится некоторое количество рабочего пространства. Это рабочее пространство необходимо обнулять после каждой подпрограммы нашего алгоритма, поэтому мы не будем включать его при описании состояния нашей машины.

Пусть даны $x$ и $n$, необходимо найти порядок числа $x$, то есть наименьшее $r$, такое, что $x^{r} \equiv 1(\bmod n)$. Мы поступим следующим образом. Во-первых, мы найдем такое $q$, степень 2 , чтобы $n^{2} \leqslant q<2 n^{2}$. Мы не будем включать числа $n, x$ или $q$ в описание состояния нашей машины, так как их значения никогда не меняются. Нам не нужно даже держать их значения в памяти, мы можем заключить их значения в структуру массива квантовых гейтов.

Теперь переведем первый регистр в равномерную суперпозицию состояний, представляющих числа $a(\bmod q)$. Машина перейдет в состояние
\[
\frac{1}{q^{1 / 2}} \sum_{a=0}^{q-1}|a\rangle|0\rangle .
\]

Этот шаг относительно прост, так как его можно выполнить, переведя каждый бит первого регистра в суперпозицию $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$.

На следующем шаге мы вычислим $x^{a}(\bmod n)$ во втором регистре, как это предлагалось сделать в §3. Так как $a$ находится в первом регистре, это можно сделать обратимым образом. После этого наша машина перейдет в состояние
\[
\frac{1}{q^{1 / 2}} \sum_{a=0}^{q-1}|a\rangle\left|x^{a} \quad(\bmod n)\right\rangle .
\]

Теперь применим преобразование Фурье $A_{q}$ к первому регистру, как это было описано в § 4 , отображая состояние $|a\rangle$ в
\[
\frac{1}{q^{1 / 2}} \sum_{c=0}^{q-1} \exp (2 \pi i a c / q)|c\rangle .
\]

—————————————————————-
0009ru_fiz_kvanr_book17_no phtoo_page-0229.jpg.txt

228
П. Шор
Здесь используется унитарная матрица с внутренними элементами $(a, c)$, равными $\frac{1}{q^{1 / 2}} \exp (2 \pi i a c / q)$. Теперь состояние нашей машины такое
\[
\frac{1}{q} \sum_{a=0}^{q-1} \sum_{c=0}^{q-1} \exp (2 \pi i a c / q)|c\rangle\left|x^{a} \quad(\bmod n)\right\rangle .
\]

И наконец, мы производим измерение состояния машины. Было бы достаточно измерить значение только $|c\rangle$ в первом регистре, но для полной ясности мы произведем измерение и $|c\rangle$, и $\left|x^{a}(\bmod n)\right\rangle$. Теперь мы вычислим вероятность того, что наша машина находится в определенном состоянии $\left|c, x^{k}(\bmod n)\right\rangle$, где предположим, что $0 \leqslant k<r$. Суммируя вероятности всевозможных исходов, приводящих к состоянию $\left|c, x^{k}(\bmod n)\right\rangle$, мы найдем, что эта вероятность равна
\[
\left|\frac{1}{q} \sum_{a: x^{a} \equiv x^{k}} \exp (2 \pi i a c / q)\right|^{2},
\]

где сумма ведется по всем $a, 0 \leqslant a<q$, таким, что $x^{a} \equiv x^{k}(\bmod n)$. Так как $r$ – порядок числа $x$, суммирование производится по всем $a$, удовлетворяющим $a \equiv k(\bmod r)$. Запишем теперь $a=b r+k$ и найдем, что приведенная выше вероятность имеет вид
\[
\left|\frac{1}{q} \sum_{b=0}^{\lfloor(q-k-1) / r\rfloor} \exp (2 \pi i(b r+k) c / q)\right|^{2} .
\]

Мы опустили член типа $\exp (2 \pi i k c / q)$, так как он может быть вынесен из под суммы и по модулю равен 1. Также мы можем заменить $r c$ на $\{r c\}_{q}$, где $\{r c\}_{q}$ – остаток, сравнимый с $r c(\bmod q)$ и изменяющийся в пределах $-q / 2<\{r c\}_{q} \leqslant q / 2$. Таким образом, получим следующее выражение
\[
\left|\frac{1}{q} \sum_{b=0}^{\lfloor(q-k-1) / r\rfloor} \exp \left(2 \pi i b\{r c\}_{q} / q\right)\right|^{2} .
\]
Теперь мы покажем, что если $\{r c\}_{q}$ достаточно мало, все амплитуды в этой сумме будут иметь примерно одно направление (то есть иметь приблизительно одну и ту же фазу), делая, таким образом, сумму большой. Превращая сумму в интегра.т, получим
\[
\begin{array}{l}
\frac{1}{q} \int_{0}^{\lfloor q-k-1 / r\rfloor} \exp \left(2 \pi i b\{r c\}_{q} / q\right) d b+ \\
\quad+O\left(\frac{\lfloor(q-k-1) / r\rfloor}{q}\left(\exp \left(2 \pi i\{r c\}_{q} / q\right)-1\right)\right) .
\end{array}
\]

Если $\left|\{r c\}_{q}\right| \leqslant r / 2$, то ошибка в приведенном выше выражении, как это легко видеть, будет ограничена $O(1 / q)$. Теперь мы покажем, что если $\left|\{r c\}_{q}\right| \leqslant r / 2$, приведенный выше интеграл будет велик, и, таким образом, вероятность получения состояния $\left|c, x^{k}(\bmod n)\right\rangle$ будет также велика. Заметим, что это условие зависит только от $c$ и не зависит от $k$. Подставив $u=r b / q$ в этот интеграл, получим
\[
\frac{1}{r} \int_{0}^{\frac{r}{q}\lfloor q-k-1 / r\rfloor} \exp \left(2 \pi i \frac{\{r c\}_{q}}{r} u\right) d u .
\]

Так как $k<r$, аппроксимируя верхний предел в интеграле единицей, в приведенном выше выражении мы лишь допустим ошибку порядка $O(1 / q)$. Сделав это, получим интеграл
\[
\frac{1}{r} \int_{0}^{1} \exp \left(2 \pi i \frac{\{r c\}_{q}}{r} u\right) d u .
\]

Полагая $\{r c\}_{q} / r$ изменяющимся между $-\frac{1}{2}$ и $\frac{1}{2}$, абсолютная величина интеграла (5.10), как это нетрудно видеть, минимизируется, когда $\{r c\}_{q} / r= \pm \frac{1}{2}$, в этом случае абсолютная величина выражения (5.10) равна $2 /(\pi r)$. Квадрат этой величины – нижняя граница для вероятности того, что мы обнаружим данное состояние $\left|c, x^{k}(\bmod n)\right\rangle$
при $\{r c\}_{q} \leqslant r / 2$. Следовательно, эта вероятность является асимптотической нижней границей равной $4 /\left(\pi^{2} r^{2}\right)$, и таким образом, не меньше, чем $1 / 3 r^{2}$ для достаточно больших $n$.

Рис. 3. Вероятность $\mathrm{P}$ обнаружить величину $c$ между 0 и 255 при $q=256$ и $r=10$.

Вероятность обнаружить данное состояние $\left|c, x^{k}(\bmod n)\right\rangle$ будет, таким образом, по крайней мере $1 / 3 r^{2}$, если
\[
\frac{-r}{2} \leqslant\{r c\}_{q} \leqslant \frac{r}{2},
\]

то есть, для такого $d$, как
\[
\frac{-r}{2} \leqslant r c-d q \leqslant \frac{r}{2} .
\]

Деля все на $r q$, переписываем выражение как
\[
\left|\frac{c}{q}-\frac{d}{r}\right| \leqslant \frac{1}{2 q} .
\]
Мы знаем $c$ и $q$. Так как $q>n^{2}$, то существует не более одного отношения $d / r$ при $r<n$, удовлетворяющее вышеприведенному неравенству. Таким образом, мы можем для $d / r$ оценку снизу путем округления $c / q$ до самого близкого отношения, имеющего знаменатель меньший, чем $n$. Такое отношение может быть найдено за полиномиальное время, используя непрерывное разложение дробей для $c / q$, которое дает все наилучшие аппроксимации $c / q$ дробями [Hardy and Wright, 1979, Chapter X, Knuth, 1981].

Точная вероятность, которая дается уравнением (5.7), для случая $r=10$ и $q=256$, представлена в виде графика на рис. 3 . Значение $r=10$ может возникнуть при факторизации числа 33 , если, например, $x$ равно 5 . Здесь $q$ взято меньшее, чем $33^{2}$, чтобы сделать значения $c$ на графике различными. Это не изменяет функциональную структуру $\mathrm{P}(c)$. Заметим, что высокая вероятность обнаружить число $c$ наблюдается вблизи значений $q / r=256 / 10$, умноженным на целое число.

Если известен нижний предел $d / r$, и если $d$ и $r$ взаимно просты, то это даст нам $r$. Подсчитаем теперь число состояний $\left|c, x^{k}(\bmod n)\right\rangle$, которые дадут нам возможность вычислить $r$ таким способом. Имеется $\phi(r)$ возможных значений $d$, взаимно простых с $r$, где $\phi(r)-\phi$-функция Эйлера (тотиент) [Knuth 1981, Hardy and Wright 1979, §5.5]. Каждое такое отношение $d / r$ близко к одному определенному отношению $c / q$, причем $|c / q-d / r| \leqslant 1 / 2 q$. Так же имеется $r$ возможных значений величины $x^{k}$, так как $r$ – порядок числа $x$. Поэтому есть $r \phi(r)$ состояний $\left|c, x^{k}(\bmod n)\right\rangle$, которые позволят вычислить $r$. Так как каждое такое состояние обнаруживается по крайней мере с вероятностью $1 / 3 r^{2}$, мы получим $r$ с вероятностью не меньшей $\phi(r) / 3 r$. Используя теорему, что $\phi(r) / r>\delta / \log \log r$ для некоторой константы $\delta$ [Hardy and Wright, 1979, Теорема 328], можно показать, что мы найдем $r$ с вероятностью не меньшей $\delta / \log \log r$ при одном измерении, и повторяя этот эксперимент всего лишь $O(\log \log r)$ раз, мы получим очень большую вероятность успеха.

В действительности, предполагая, что квантовые вычисления более дороги, чем классические, кажется стоящим переделать вышеприведенный алгоритм так, чтобы в нем использовалось меньше квантовых вычислений и больше классических постпроцедур. Во-первых, если мы обнаружили состояние $|c\rangle$, было бы правильным попробовать проверить также числа, близкие к $c$, такие как $c \pm 1, c \pm 2, \ldots$, так как для них также имеется весьма весомый шанс оказаться близкими $\mathrm{k}$ отношению $q d / r$. Во-вторых, если $c / q \approx d / r$, а $d$ и $r$ имеют общий множитель, вероятно, он будет маленьким числом. Поэтому, если обнаруженная величина $c / q$ может быть округлена до $d^{\prime} / r^{\prime}$ в нижнем пределе, в качестве кандидата на $r$ было бы неплохо рассмотреть не только $r^{\prime}$, но также умноженные на небольшие целые числа, типа $2 r^{\prime}, 3 r^{\prime}, \ldots$, посмотреть, не являются ли они действительно порядком числа $x$. Хотя первый прием может только уменьшить число попыток, требуемых для того, чтобы найти $r$ на постоянный множитель, второй прием в состоянии уменьшить число таких попыток для сложных $n$ с $O(\log \log n)$ до $O(1)$, если будут рассмотрены первые $(\log n)^{1+\varepsilon}$ умножений $r^{\prime}$ на целые числа [Odylzko, 1995]. Третий способ заключается в следующем. Пусть найдены два кандидата на роль $r$, скажем $r_{1}$ и $r_{2}$, рассмотрим тогда в качестве кандидата наименьшее общее кратное $r_{1}$ и $r_{2}$. Этот третий способ также способен сократить число требуемых попыток на постоянный множитель [Knill, 1995], и возможно он сработает в ситуациях, когда предыдущие два способа окажутся несостоятельными.

Заметим, что в этом алгоритме нахождения порядка числа мы не использовали многие особенности умножения по $\bmod n$. Действительно, если имеется перестановка $f$, отображающая множество $\{0,1,2, \ldots$, $n-1\}$ в себя, такая, что ее $k$-я итерация, $f^{(k)}(a)$, вычислима за время, полиномиальное по $\log n$ и $\log k$, тот же алгоритм будет способен найти порядок элемента $a$ относительно $f$, другими словами, минимальное $r$, такое, что $f^{(r)}(a)=a$.