Теперь наших знаний достаточно, чтобы понять, как квантовый компьютер может выполнять логические операции и вычислять подобно обычному компьютеру. В этом разделе мы опишем алгоритм, использующий квантовый параллелизм, на который мы уже намекали: поиск периода длинной последовательности.
Рассмотрим последовательность
\[
f(0), f(1), \ldots, f(q-1),
\]

где $q=2^{k}$; чтобы найти ее период, мы используем квантовый параллелизм. Начнем с совокупности частиц, спины которых первоначально направлены вниз. Сгруппируем их в два набора (два квантовых регистра, или квантовые переменные):
\[
|0 ; 0\rangle=|\downarrow, \downarrow, \ldots ; \downarrow, \downarrow, \ldots\rangle,
\]

при этом первый ряд содержит $k$ битов, и число битов в другом достаточно для наших целей. (В действительности, требуются и другие регистры, но зная решение Беннетта задачи об уборке мусора, пока о них можно умолчать.)

Применив к каждому биту первого регистра однобитную операцию $U_{-\pi / 2}$, получим суперпозицию всех возможных двоичных строк длины $k$ в этом регистре:
\[
\rightarrow \frac{1}{\sqrt{q}} \sum_{a=0}^{q-1}|a ; 0\rangle .
\]

Следующий шаг состоит в том, что вычисление функции $f(a)$ разбивается на ряд однобитных и двубитных унитарных операций. Последовательность операций конструируется таким образом, чтобы преобразовать состояние $|a ; 0\rangle$ в состояние $|a ; f(a)\rangle$ для любого $a$. Число битов, необходимых для второго регистра, должно быть, по крайней мере, достаточным для того, чтобы вместить самый длинный результат $f(a)$ для любого из этих вычислений. Когда эта последовательность операций применяется к нашей экспоненциально большой суперпозиции, а не к одному состоянию на входе, мы получаем
\[
\rightarrow \frac{1}{\sqrt{q}} \sum_{a=0}^{q-1}|a ; f(a)\rangle .
\]

Экспоненциально большое число вычислений проводится по существу бесплатно.

Конечный вычислительный шаг, также как и первый, опять является чисто квантовомеханическим. Рассмотрим дискретное «квантовое» преобразование Фурье первого регистра
\[
|a\rangle \rightarrow \frac{1}{\sqrt{q}} \sum_{c=0}^{q-1} e^{2 \pi i a c / q}|c ; f(a)\rangle .
\]

Легко заметить, что оно обратимо в результате обратного преобразования (нетрудно проверить, что оно унитарно). Эффективный способ вычисления этого преобразования с помощью однобитных и двубитных гейтов был описан Копперсмитом (рис. 10) $[23,24,6]$.

Рис. 10. Цепь для квантового преобразования Фурье переменной $\left|a_{k-1} \ldots a_{1} a_{0}\right\rangle$, использующая метод Копперсмита быстрого преобразования Фурье $[23,24,6]$. Двубитные « $X_{n} »$-гейты, в свою очередь, могут быть разложены в некоторые однобитные и XOR-гейты [14].
Когда это квантовое преобразование Фурье применяется к нашей суперпозиции, мы получаем
\[
\rightarrow \frac{1}{q} \sum_{a=0}^{q-1} \sum_{c=0}^{q-1}|c ; f(a)\rangle .
\]

Вычисление теперь завершено, и мы восстанавливаем результат на выходе квантового компьютера, измеряя состояние всех спинов в первом регистре (для первых $k$ битов). В действительности, как только преобразование Фурье выполнено, второй регистр может быть даже отброшен $[27]$.
Как будет выглядеть выход?
Предположим, что $f(a)$ имеет период $r$, т. е. $f(a+r)=f(a)$. Сумма по $a$ приводит к конструктивной интерференции коэффициентов, только когда $c / q$ кратно обратному периоду $1 / r[25]$. При всех других значениях $c / q$ происходит в большей или меньшей степени деструктивная интерференция. Таким образом, распределение вероятности найти первый регистр с различными значениями схематично показано на рис. 11 .

Рис. 11. График зависимости вероятности каждого результата относительно $c / q$. Конструктивная интерференция дает узкие пики при значениях $c / q$, кратных обратному периоду последовательности $1 / r$.

Один полный цикл работы квантового компьютера дает случайное значение $c / q$, соответствующее одному из пиков вероятности каждого результата $\operatorname{prob}(c)$. Иначе говоря, мы получаем случайное значение, кратное обратному периоду. Для выделения самого периода нам нужно только повторить это квантовое вычисление, грубо говоря, $\log \log r / k$ раз для того, чтобы получить высокую вероятность, по крайней мере, одному из кратных быть взаимно простым с периодом $r$ — тогда он однозначно определяется [1]. Таким образом, этот алгоритм дает только вероятностный результат. К счастью, мы можем сделать эту вероятность настолько большой, насколько захотим.

Вся описанная выше работа может показаться несколько обескураживающей. Мы столкнулись с большими трудностями при конструировании квантового компьютера для поиска периода последовательности. Преимущество, однако, состоит в том, что последовательность вычисляется параллельно и является экспоненциально длинной — даже для малого количества битов, скажем $k=140$, в первом регистре квантовый компьютер получал и сохранял больше результатов, чем число частиц во вселенной. Сейчас мы опишем простую структуру, которая существует в математической задаче факторизации и которая позволяет применить в этом случае описанный выше алгоритм квантовых вычислений.