Показанный на рис. 3A AND-гейт производит классическую булеву операцию. Однако ее реализация абсолютно неклассическая, так что ее можно считать прототипом мощных вычислительных процедур (таких, как разложение на простые множители и подобных ей), являющихся уникальной особенностью квантовых вычислений. На рис. 3С показано, как при различных начальных состояниях изображенный на рис. $3 \mathrm{~A}$ AND-гейт эволюционирует через три свои стадии к окончательному ответу (мы следуем вычислению, для которого начальное состояние рабочего кубита равно $|0\rangle$ ).

В любой классической схеме каждое из этих вычислений производится независимо от других по определенному пути от начала вычисления до его конца. В случае же квантовых вычислений эта процедура может быть расщеплена на несколько (в данном случае на два) пути, которые, благодаря квантовому принципу суперпозиции, эволюционируют во времени параллельно. В силу того, что каждый из этих путей обладает определенной фазой (обратите внимание на точки, в которых фазовый сдвиг на $180^{\circ}$ обусловлен эволюцией), окончательный ответ получается после рекомбинации конечных состояний, сопровождаемой конструктивной или деструктивной интерференцией.

В нашем примере состояние $|000\rangle$ преобразуется в себя, как этого требует таблица истинности для AND, потому что два вычислительных пути, приводящих в конце к состоянию $|000\rangle$, имеют одну и ту же фазу (0 вдоль одного пути и $2 \pi$ вдоль другого), и поэтому их взаимное влияние конструктивно. Неправильный результат, например $|010\rangle$, чьи вычислительные пути также доходят до конца, предотвращается, потому что фазы его двух возможных путей противоположны (0 вдоль одного пути и $\pi$ вдоль другого) и, интерферируя, гасят друг друга. Если фазы не будут контролироваться в точности, то в половине случаев будет появляться неправильный результат. Таким образом, мы видим, что квантовые вычисления, вопреки своей чрезвычайной сложности, не определяют промежуточного состояния вычисления, но это состояние может быть определено в конце.

Это общая схема квантовых вычислений была предложена впервые Дойчем [3], а затем с большим эффектом была использована в алгоритме Шора $[2,3]$ для эффективного решения чрезвычайно громоздкой вычислительной проблемы. На рис. 5 показана квантовая вычислительная структура, которую использовал Шор для решения задачи о разложении целого числа на простые сомножители.

На этой диаграмме, также, как на диаграмме на рис. 3 А, описывающей эволюцию AND-гейта, показаны пути изменения во времени состояния квантового вычисления для факторизационной процедуры как функция от времени (время изменяется здесь сверху вниз, также как ранее слева на право).

Как предлагали в более ранних работах Дойч и Джозса [22] (см. также [23]), Шор разделяет кубиты квантового компьютера на два регистра: входной и выходной. Число битов в каждом регистре должно соответствовать числу битов в числе, которое надо факторизовать. Предположим, что в каждом регистре содержится по $k=1000$ битов. Прямоугольник на рис. 5 изображает память гильбертова пространства состояний входного и выходного регистра. Эта диаграмма очень схематична, так как размерность гильбертова пространства огромна: $2^{1000}$ битов для каждого регистра. Заметим, что экспоненциальный рост размерности гильбертова пространства с увеличением числа частиц в системе является одной из причин огромной потенциальной силы квантовых вычислений. Конечно, унитарные матрицы могут быть просто построены и перемножены на обыкновенном цифровом компьютере, но их размеры не могут расти экспоненциально с числом входящих в него компонент [24].

Черным на рис. 5 обозначено мгновенное состояние квантового компьютера на трех основных стадиях вычислительного алгоритма Шора. Первые несколько шагов чрезвычайно просты: пусть начальное
Рис. 5. Схематическое изображение временной эволюции вычислительных путей алгоритма Шора разложения на простые множители. В каждый момент времени состояние вычисления определяется волновой функцией и обозначается черным полем. Некоторые из вычислительных путей схематически набросаны. Большинство вычислительных путей (обозначенных многоточиями) интерферируют деструктивно, и только некоторые (обозначенные сплошными линиями) интерферируют конструктивно.

состояние будет нулевым (все спины направлены вниз). (Классический ввод – информация о числе $N$, которое должно быть факторизовано, пока ждет своей очереди). На первом шаге вычисление расщепляется на $2^{1000}$ вычислительных путей, таким образом волновая функция системы становится линейной суперпозицией всех возможных состояний с одинаковыми фазами. Полученное состояние помещается во входной регистр $x$. Это в высшей степени неклассическое вычисление можно очень просто описать спектроскопическим языком: к каждому из спинов прикладывается импульс, осуществляющий поворот на $90^{\circ}$. Эта операция приводит к волновой функции системы в ожидаемом состоянии.

Второй шаг менее тривиален. Необходимо единожды вычислить следующую классическую булеву функцию
\[
f(x)=c^{x}(\bmod N) .
\]
Значение этой функции надо разместить в выходном регистре $y$. В формуле (5) $x$ – значение входного регистра, рассматриваемое как целое число в бинарном представлении, $N$ – целое число, которое мы факторизуем, и константа $c$ – любое другое целое число, не имеющее общих простых множителей с числом $N$. Под $\bmod N$ мы понимаем арифметику по модулю $N$, в которой результат равен остатку от деления на $N$. Поскольку на входе компьютера заданы все значения аргумента, то в силу принципа суперпозиции единственное вычисление $f(x)$ даст нам все возможные значения на выходном регистре. Чтобы вычислить эту функцию на квантовом компьютере, нужно сначала «скомпилировать» ее в обычном классическом смысле, т. е. задать функцию как последовательность операций в терминах таких примитивных булевых функций, как NOT и AND. Затем следует реализовать эту последовательность как квантовую процедуру, например, с помощью магнитных импульсов.

Здесь не место для подробного объяснения того, почему параллельное вычисление такой частной функции, как $f(x)$, оказывается полезным для проведения процедуры факторизации числа на простые сомножители. Это потребует углубления в сложные технические аспекты из теории чисел, которые хорошо изложены в оригинальной литературе [2], а также в недавнем обзоре [4].

Коротко, в двух словах, скажем, что важнейшей особенностью функции $f(x)$ является ее периодичность по $x$. Если число $N$ простое, то $f(x)$ имеет период $N-1$, в противном случае период короче, и, зная этот период, после прямолинейных (классических) вычислений можно найти один из простых множителей числа $N$.

Шор заметил, что квантовый компьютер очень хорошо приспособлен для нахождения периодов функции $f(x)$. Нужно только произвести преобразование Фурье над входным регистром $x$. (Выходной регистр $y$ остается нетронутым.) Эта третья и последняя стадия вычисления показана на рис. 5. Приведем некоторые точные формулы. Преобразование Фурье применяется к волновой функции
\[
\Psi=\sum_{x=00 \ldots 0}^{11 \ldots 1} c_{x}|x\rangle,
\]

которая принимает вид
\[
\Psi=\sum_{x=00 \ldots 0}^{11 \ldots 1}\left(2^{-k / 2} \sum_{x^{\prime}=00 \ldots 0}^{11 \ldots 1} \exp \left(2 \pi x^{\prime} x / 2^{k} c_{x^{\prime}}\right)\right)|x\rangle .
\]

Рис. 6. Предложенная Копперсмитом [25] схема квантовых гейтов, которые производят преобразование Фурье (третий шаг в процедуре Шора на рис. 5). Также показаны матричные унитарные операторы, соответствующие двум видам квантовых гейтов. Двубитный гейт $X_{n}$ может быть реализован через простую комбинацию XOR-гейтов [12]. $X_{n}$ действует симметрично на эти два бита.
Коэффициенты преобразованной волновой функции являются дискретными преобразованиями Фурье первоначальных коэффициентов. Шор обнаружил, что это преобразование является унитарным и показал, что оно может быть произведено за полиномиальное число шагов по $k$ числу битов во входном регистре (оно соответствует числу битов, необходимых для того, чтобы представить число $N$ в двоичной системе). Копперсмит [25] нашел простую явную конструкцию гейтов (см. рис. 6) для реализации преобразования Фурье, представленного в (7). Она является непосредственной транскрипцией быстрого преобразования Фурье (FFT) Кули-Туки с индивидуальными «факторами подкручивания» (FFT), реализуемыми как двукубитные гейты $X_{i}$. Эта процедура схожа с первыми шагами вычислений, предложенных Шором, которая заключается просто в повороте на $90^{\circ}$ опрокидывающим импульсом значения каждого бита, без гейтов, осуществляющих «подкручивание факторов».
Копперсмит заметил, что эту последовательность операций можно совершить за $k^{2}$ шагов.

Этот последний шаг с использованием быстрого преобразования Фурье является чрезвычайно эффективным способом отыскания периода функции $f(x)$, аналогичным определению периодической структуры кристаллов по результатам рассеяния рентгеновских лучей. Финальное измерение значения регистра $x$ – это измерение положения одного из брегговских максимумов в рассеянии. Это измерение позволяет определить лишь величину, кратную фундаментальному периоду $f(x)$, однако существует прямолинейная теоретико-числовая процедура, позволяющая вычислить сам фундаментальный период.

Предложенная Шором процедура реализуется способом, схожим со способом реализации AND-гейта. Несмотря на то, что промежуточные состояния вычисления, представляющие собой суперпозицию различных путей, не определены, деструктивная интерференция запрещает почти все возможные конечные состояния (также как и в брегговском рассеянии дифракция почти во все направления запрещена), оставляя в финале почти точно определенное состояние – это и есть результат вычисления. Заметим, что описанный здесь дифракционный процесс существенно отличается от дифракции классической волны: размер дифракционной решетки, показанной на рис. 5, растет экспоненциально с величиной числа, которое должно быть факторизованно. Именно по этой причине классическая волновая оптика не может решить проблему факторизации.

Наконец, поясним, почему оценка числа шагов, необходимых для проведения факторизации по алгоритму Шора, произвела сенсацию в компьютерном научном сообществе. Алгоритм Шора полиномиален по $k$, число шагов пропорционально $k^{3}$ при малых $k$, и $k^{2}$ при больших $k$. Наилучший из существующих классических алгоритмов, основанных на обыкновенных булевых операциях, оценивает число шагов как $\exp \left(a k^{1 / 3}\right)$, где $a$ – некая константа $[4,26]$. Даже если признать, что пока неизвестно, может ли данная проблема быть решена за полиномиальное время на обыкновенном компьютере, результат Шора показал научному сообществу, что алгоритмические подходы с использованием квантовых вычислений значительно мощнее обыкновенной булевой логики, и активная работа в этом направлении в более полной мере покажет силу этих квантово-механических подходов к решению важных математических задач.