Определение массивов квантовых гейтов требует реализации обратимых вычислений. Другими словами, зная квантовое состояние на выходных проводах гейта, можно однозначно сказать, какое состояние было на входе. Это отражение того факта, что несмотря на макроскопическую стрелу времени, законы физики оказываются полностью обратимыми. Как может показаться, все, построенное по законам физики, должно быть обратимым. Однако, классические компьютеры обходят это утверждение благодаря диссипации энергии, что делает такой компьютер термодинамически необратимым. В квантовом компьютере это оказывается невозможно, так как суперпозиция квантовых состояний должна поддерживаться в течение всего вычисления. Это требует дополнительных затрат при проведении классических вычислений на квантовом компьютере, какие иногда требуется производить в подпрограммах квантовых вычислений.

В силу обратимости квантовых вычислений, детерминированные вычисления осуществимы на квантовом компьютере только если их сделать обратимыми. К счастью, уже показано, что любые детерминированные вычисления могут быть сделаны обратимыми [Lecerf, 1963, Bennett, 1973]. Действительно, обратимые массивы классических гейтов (или обратимые ациклические схемы) были изучены. Наряду с ре-
Рис. 1. Таблица истинности для гейтов Тоффоли и Фредкина.

зультатом, заключающимся в том, что любое классическое вычисление может быть осуществлено с помощью гейтов NAND, существует также универсальные гейты для обратимых вычислений. Два из таких гейтов носят название гейта Тоффоли [Toffoli, 1980] и гейта Фредкина [Fredkin and Toffoli, 1982] (см. рис. 1).

Гейт Тоффоли представляет собой просто контролируемый NOT, То есть, последний бит изменяет свое значение тогда и только тогда, когда значение первого бита равно единице. В этом гейте, если значение третьего бита на входе будет равно единице, то на выходе в третьем бите будет результат действия операции NAND первых двух битов. Так как NAND является универсальным гейтом для квантовых вычислений, то и гейт Тоффоли является таким универсальным гейтом. В гейте Фредкина последние два бита меняются местами, если значение первого бита равно нулю, и остаются неприкосновенными, если в первом бите содержится единица. Для гейта Фредкина, если на вход третьего бита подается ноль, то во втором бите получается результат действия операции AND содержимого первых двух битов; и если на входе последних двух битов подать ноль и единицу соответственно, то во втором бите на выходе будет результат действия операции NOT первого бита. Поэтому и операция AND, и операция NOT реализуются с помощью гейта Фредкина, показывая, что этот гейт является универсальным.

Используя результаты работ по обратимым вычислениям [Lecerf, 1963, Bennett, 1973], мы можем эффективно вычислять любую полиномиальную по времени функцию $F(x)$, до тех пор, пока входные данные $x$ сохраняются в компьютере. Мы можем сделать это вычисление необратимым с помощью приспособленных для этого методов. Этот результат может быть легко распространен на работу массива из гейтов [Toffoli, 1980, Fredkin and Toffoli, 1982]. Если заменить AND, OR и NOT гейты на гейты Тоффоли или на гейты Фредкина, то необходимо добавить в обоих случаях один входной бит, содержащий соответствующее значение, и один выходной бит, необходимый для того, чтобы сделать вычисление обратимым. Несмотря на то что дополнительные входные биты не приводят к сложностям при конструировании квантового компьютера, дополнительные выходные биты приводят к трудностям, так как, если их значения не обращать снова в ноль, они будут влиять на интерференционную картину квантовых вычислений. Метод Беннетта по обращению таких битов в ноль показан в верхней половине таблицы на рис. 2. Оказывается, массив необратимых гейтов можно превратить в массив обратимых гейтов следующим образом: во-первых, будем дублировать значения входных битов столько раз, сколько это понадобится (так как значение входного бита может использоваться в массиве гейтов более одного раза); во-вторых, сохраняя одну из копий входных битов, заменяем необратимые гейты гейтами Тоффоли и Фредкина, а дополнительные выходные биты записываем в регистр RECORD. Эти выходные биты сохраняют достаточное количество записей производимых операций, чтобы сделать вычисление массива гейтов обратимыми. Выход функции $F(x)$ будет вычислен один раз, результат скопирован в регистр, заполненный ранее нулями, и теперь можно стереть первоначальное значение регистров OUTPUT и RECORD.
Рис. 2. Метод Беннетта, с помощью которого можно сделать вычисления обратимыми.

Для того, чтобы стереть $x$ и переписать на его место $F(x)$, в дополнение к полиномиальному по времени алгоритму вычисления функции $F$ нам необходимо иметь полиномиальный по времени алгоритм вычисления $x$ по $F(x)$, другими словами, нам необходимо, чтобы $F$ была взаимнооднозначной функцией, и чтобы $F$, как и $F^{-1}$, были бы вычислимы за полиномиальное время. Метод таких вычислений представлен в таблице на рис. 2. Это вычисление разбито на два этапа. Первый аналогичен изложенному выше: $x$ преобразуется в $(x, F(x))$. О втором этапе, показанном в нижней части таблицы на рис. 2 , заметим, что если у нас есть необратимый полиномиальный по времени метод вычисления $F^{-1}$, мы можем использовать ту же технику обратимого отображения $F(x)$ в $\left(F(x), F^{-1}(F(x))\right)=(F(x), x)$. Однако, так как это вычисление обратимо, обратив его, мы можем получить из $(x, F(x))$ значение $F(x)$. Объединяя две эти части, получим значение $x$ по $F(x)$.

Из вышеприведенного обсуждения видно, что приведение вычисления к обратимому ведет к умножению на постоянную величину для времени, и также такой метод использует столько же места в памяти, сколько и используемого времени. И если классическое вычисление требует гораздо меньшего использования места, чем времени, то приведение алгоритма к обратимому виду таким способом будет вести к резкому увеличению требуемой памяти. Существуют методы, делающие вычисления обратимыми, не затрачивая так много оперативного пространства, но требующие гораздо большего времени на исполнение вычислений, можно найти в работах [Bennett, 1989, Levine and Sherman, 1990]. В то время, как не существует общего метода, который не ведет к увеличению потребностей либо в памяти, либо во времени исполнения, существуют специальные алгоритмы, которые могут быть сделаны обратимыми без больших затрат используемых пространственных или временных ресурсов. В конце этого раздела мы покажем, как это сделать для алгоритма возведения в степень по модулю, которая является необходимой подпрограммой для квантовой факторизации.

Уязвимым местом квантового алгоритма факторизации целого числа, то есть, той частью алгоритма, которая потребляет большую часть времени и места, является возведение числа в степень по модулю. Эта задача заключается в следующем: пусть даны $n, x$, и $r$, необходимо найти $x^{r} \bmod n$. Лучший классический метод, с помощью которого это можно сделать, заключается в следующем: надо повторно возводить в квадрат число $x \bmod n$ до тех пор, пока не получим $x^{2^{i}}(\bmod n)$, где $i \leqslant \log _{2} r$, затем умножаем на степени по модулю $n$, получим $x^{2^{r}}(\bmod n)$. Если мы работаем с $l$-битным числом, нам потребуется $O(l)$ возведений в квадрат и умножений $l$-битных чисел по $(\bmod n)$. Асимптотически лучшим классическим алгоритмом умножения для массивов гейтов является алгоритм Шёнхаге-Штрассена [Schönhage and Strassen, 1971, Knuth, 1981, Schönhage, 1982]. По этому алгоритму можно построить массив гейтов, выполняющих умножение целых чисел, использующий $O(l \log l \log \log l)$ гейтов для перемножения двух $l$-битных чисел. Таким образом, асимптотически возведение в степень по модулю требует $O\left(l^{2} \log l \log \log l\right)$ шагов. Приведение алгоритма к обратимому виду, потребует такое же количество памяти. Однако, мы можем повторно использовать место, занимаемое в части алгоритма, где производится повторяющееся возведение в квадрат, и, следовательно, существенно сократить количество требуемой памяти, необходимой для перемножения двух $l$-битных чисел. Один простой (хотя и не самый универсальный) метод сокращения требуемого пространства будет дан позже, в конце этого раздела. Таким образом, возведение в степень по модулю может быть осуществлено за $O\left(l^{2} \log l \log \log l\right)$ шагов, требуя $O(l \log l \log \log l)$ свободного пространства.

Несмотря на то что алгоритм Шёнхаге-Штрассена является наилучшим из известных алгоритмов перемножения двух целых чисел для больших $l$, это не справедливо для малых $l$. Для небольших чисел лучшим массивом гейтов, осуществляющих умножение, по существу является тот, который реализует элементарное перемножение бинарных чисел на бумаге, которому учат в школе. Этот метод требует $O\left(l^{2}\right)$ шагов для перемножения двух $l$-битных чисел, и, следовательно, возведение в степень по модулю требует $O\left(l^{3}\right)$ шагов в соответствии с этим методом. Этот массив гейтов можно сделать обратимым, используя при этом лишь $O(l)$ свободной памяти.

Сейчас мы предложим метод построения массива квантовых гейтов, который использует только $O(l)$ свободного пространства и вычисляет за $O\left(l^{3}\right)$ шагов $\left(a, x^{a}(\bmod n)\right)$ по $a$, где $a, x$, и $n-l$-битные числа, при этом $x$ и $n$ сравнительно простые числа. Это тот случай, где $x$ и $n$ являются относительно простыми числами, достаточен для факторизации и алгоритмов дискретного логарифма. Подробный анализ этого метода по существу, дающий точное число квантовых гейтов, достаточное для факторизации, был дан Бекманом(Beckman et al., [1996]). Основной используемый конструктивный блок представляет собой массив гейтов, который берет число $b$ на входе, дает $b+c(\bmod n)$ на выходе. Заметим, что здесь $b$ поступает в массив гейтов на вход, в то время как $c$ и $n$ встроены в структуру массива квантовых гейтов. Так как сложение по $(\bmod n)$ вычислимо по классическим алгоритмам в $O(\log n)$ шагов, такой обратимый массив квантовых гейтов может состоять только из $O(\log n)$ гейтов и $O(\log n)$ рабочих битов, используя методы, ранее описанные в этом разделе.

Техника, используемая нами для вычисления $x^{a}(\bmod n)$ в сущности та же, что и в классическом методе. В начале мы повторяющимися возведениями в квадрат вычислим $x^{2^{i}}(\bmod n)$ для всех $i<l$. Затем, чтобы получить $x^{a}(\bmod n)$, мы будем домножать степени $x^{2^{i}}(\bmod n)$, где $2^{i}$ соответствует бинарной реализации числа $a$. В нашем алгоритме факторизации числа $n$ необходимо вычислить только $x^{a}(\bmod n)$, где $a$ представляет собой суперпозицию состояний, в то время, как $x$ есть некое целое число. Это все сильно упрощает, так как в используемых нами обратимых квантовых гейтах числа $a$ трактуются как входные данные, а $x$ и $n$ встроены в структуру массива гейтов. Таким образом, мы можем использовать алгоритм, описывающийся следующим псевдокодом:
power $:=1$
for $i=0$ to $l-1$
if $\left(a_{i}==1\right)$ then
power $:=$ power $* x^{2^{i}} \bmod n$
endif
endfor
Здесь $a_{i}$ означает $i$-й бит числа $a$ в бинарном представлении, где биты перенумерованы справа налево и самый правый бит $a$ есть $a_{0}$. Переменная $a$ остается неизменной по своему значению и величина $x^{a}(\bmod n)$ соответствует выходным данным с переменной power. Таким образом, такая программа преобразует пару значений $(a, 1)$ в $\left(a, x^{a}(\bmod n)\right)$.
Этот псевдокод может быть легко реализован через массив гейтов. Единственное затруднение может вызвать четвертая строчка, где мы умножаем переменную power на $x^{2^{i}}(\bmod n)$. Для того чтобы это сделать, нам необходимо использовать довольно сложный массив гейтов в качестве подпрограммы. Напомним, что $x^{2^{i}} \bmod n$ может быть классически вычислена и после этого встроена в структуру квантовых гейтов. Таким образом, чтобы реализовать эту строчку, нам необходимо иметь обратимый массив квантовых гейтов, в котором $b$ являлось бы входными данными, $b c(\bmod n)$ было на выходе, причем структура массива гейтов зависит от $c$ и $n$. Конечно, этот шаг может быть обратим только тогда, когда $\operatorname{gcd}(c, n)=1$, или, другими словами, когда $c$ и $n$ не имеют общих делителей, так как в противном случае два различных значения $b$ будут отображаться в одно и то же значение $b c(\bmod n)$. К счастью, этот случай нам и нужен для алгоритма факторизации.

Мы покажем, как построить такой массив гейтов в два этапа. Первый этап в точности соответствует возведению в степень путем последовательного умножения, которое реализуется путем последовательного сложения по модулю $n$. Псевдокод этого этапа такой:
result $:=0$
for $i=0$ to $l-1$
if $\left(b_{i}==1\right)$ then
result $:=$ result $+2^{i} c(\bmod n)$
endif
endfor
Снова напомним, что $2^{i} c(\bmod n)$ может быть вычислен заранее и встроен в структуру массива гейтов.

Вышеприведенный псевдокод использует $b$ в качестве начальных данных, а на выходе дает $(b, b c(\bmod n))$. Чтобы получить желаемый результат, нам теперь необходимо обнулить $b$. Напомним, что $\operatorname{gcd}(c, n)=1$, таким образом, справедливо соотношение: $c^{-1}(\bmod n)$ при $c c^{-1} \equiv 1(\bmod n)$. Домножение на такое $c^{-1}$ можно использовать для того, чтобы обратно получить из $b c(\bmod n)$ следующее: $\left(b c(\bmod n), b c c^{-1}(\bmod n)\right)=(b c(\bmod n), b)$. Это только обратная величина операции, которая нам нужна, и, так как мы работаемс обратимым вычислением, используя эту операцию, мы можем снова восстановить значение $b$. Псевдокод этой операции следующий:
for $i=0$ to $l-1$
if $\left(\right.$ result $\left._{i}==1\right)$ then
$b:=b-2^{i} c^{-1}(\bmod n)$
endif
endfor
Как и раньше, result ${ }_{i}-i$-й бит числа result.
Заметим, что на этой стадии вычисления $b$ должно быть равно 0 . Однако мы не можем просто обнулить $b$, так как это будет необратимой операцией, и, следовательно, недопустимой для квантового компьютера. Вместо этого мы используем достаточно сложную последовательность операций, приводящих к $b=0$, и которая фактически зависит от умножения, являясь группой $(\bmod n)$. С этой точки зрения, мы можем сделать некоторую хитрость: мы могли бы измерить величину $b$ и посмотреть, не равна ли она нулю. Если нет, то тогда мы знаем, что где-то в наших квантовых вычислениях произошла ошибка, и, таким образом, полученные результаты ничего не стоят и нам необходимо прервать вычисления и начать их сначала. Однако, если мы нашли, что величина $b$ равна нулю, то она точно (так как мы ее только что измерили) будет равна нулю. Такое измерение может перевести квантовое вычисление в такое состояние, при котором всякая ненулевая амплитуда обращается в нуль. Более того, так как вероятность обнаружить данное состояние пропорционально квадрату амплитуды этого состояния, возводя в степень по модулю и измереряя $b$ каждый раз, когда мы знаем, что $b$ должно равняться нулю, мы можем добится более высокой вероятности получить правильный ответ, чем такие же вычисления, совершенные без многократных измерений $b$. Этот эффект носит название квантового цепного пса (quantum wathdog) или квантового эффекта Зенона [Peres, 1993]. Приведенный выше аргумент на самом деле не показывает, действительно ли выгодно производить повторные измерения величины $b$, так как это потребует дополнительных затрат (временных, а возможно, и каких-либо иных) на проведение такого измерения. Когда такая система будет создана, можно будет аналитически и экспериментально проверить полезность таких измерений по отношению к затратам на них. Вобщем, я надеюсь, что такие частичные измерения являются перспективными в попытках стабилизации квантовых вычислений.

Подводя итог, скажем, что алгоритм Шёнхаге-Штрассена применим для перемножения больших целых чисел, а для маленьких чисел более применим алгоритм умножения столбиком. Также существуют алгоритмы, находящиеся по эффективности между первыми двумя, и они хороши для чисел средней длины [Karatsuba and Ofman, 1962, Knuth, 1981, Schönhage et al., 1994]. Пока неясно, какой из алгоритмов наиболее приемлем для чисел определенной длины. Несмотря на то, что в некотором смысле для классических вычислений это нам известно [Schönhage et al., 1994], используемые данные, по которым можно сказать, какой алгоритм лучше работает на классическом компьютере, могут привести к недоразумениям по двум причинам: во-первых, классическому компьютеру не нужно быть обратимым, а ограничения, накладываемые в процессе приведения алгоритма к обратному виду, зависят от самого алгоритма; во-вторых, существующие компьютеры в основном перемножают 32 -х или 64 -х разрядные числа, заключенные в аппаратной части компьютера, и это может поднять оптимальную планку быстродействия алгоритма, так как некий алгоритм умножения может быть лучшим образом подстроен под устройство компьютера, чем другие. Таким образом, для того чтобы программы на квантовом компьютере работали более эффективно, необходимо нацелиться на наилучшую реализацию элементарных алгебраических операций на таком квантовом компьютере. Имеет место один любопытный факт. Алгоритм Шёнхаге-Штрассена быстрого перемножения использует быстрое преобразование Фурье, которое также является базисом для всех ныне известных быстрых алгоритмов для квантового компьютера. Можно спрогнозировать, что само по себе умножение целых чисел может быть сильно ускорено на квантовом компьютере, и возможно, это еще более асимптотически ускорит факторизацию целых чисел на квантовом компьютере, и возможно, это приведет к тому, что взлом системы RSA на квантовом компьютере будет производиться асимптотически быстрее, чем кодирование RSA на классическом компьютере.