В квантовом компьютере логические схемы и временные шаги существенно классические, только биты памяти, которые хранят переменные, находятся в состояниях квантовой суперпозиции (смотрите [1] и [3] для более полного ознакомления с квантовыми компьютерами). Квантово-механические операции, которые могут быть проведены контролируемым путем, – это унитарные операции, действующие на каждом шаге на малое число битов. Квантовый алгоритм поиска, описываемый в этой статье, есть результат действия таких унитарных преобразований на чистое состояние, которое можно определить с помощью процедуры измерения. Нам необходимы следующие три элементарные операции. Первая – это приготовление состояния, в котором система находится с равной вероятностью в любом из ее $N$ базисных состояний; вторая – это преобразование Уолша-Адамара (Walsh-Hadamard) и третья – выборочный поворот фаз состояний.

Основной операцией для квантовых вычислений является операция $M$, действующая на один бит, которая представляется следующей матрицей:
\[
M=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}
1 & 1 \\
1 & -1
\end{array}\right)
\]
т. е. бит в состоянии 0 превращается в суперпозицию двух состояний: $(1 / \sqrt{2}, 1 / \sqrt{2})$. Аналогично, бит в состоянии 1 трансформируется в $(1 / \sqrt{2},-1 / \sqrt{2})$, т. е. величина амплитуды для каждого состояния равна $1 / \sqrt{2}$, но фаза в состоянии 1 перевернута. Фаза не имеет аналога в классических вероятностных алгоритмах. Она возникает в квантовой механике, где амплитуда вероятности комплексна. В системе, в которой состояние описывается $n$ битами (т. е. имеется $N=2^{n}$ возможных состояний), мы можем осуществить преобразование $M$ на каждом бите независимо, последовательно изменяя состояние системы. Матрица перехода, представляющая этот оператор, будет матрицей размерности $2^{n} \times 2^{n}$. В случае, когда начальная конфигурация представляла собой конфигурацию с $n$ битами в первом состоянии, полученная конфигурация будет иметь равные амплитуды $2^{-n / 2}$ для каждого из $2^{n}$ состояний. Это и есть способ создания суперпозиции с той же самой амплитудой для всех $2^{n}$ состояний.

Теперь рассмотрим случай, когда начальное состояние – это некоторое другое из $2^{n}$ возможных состояний, т. е. состояние, описываемое $n$-битной бинарной строкой, в которой есть как нули, так и единицы. Результат применения преобразования $M$ к каждому такому биту дает суперпозицию состояний, описывающую все возможные $n$ битов бинарной строки с амплитудами для каждого состояния по величине равными $2^{-n / 2}$ и со знаком + или -. Чтобы определить знак, заметим, что из определения матрицы $M$, т.е.
\[
M=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}
1 & 1 \\
1 & -1
\end{array}\right),
\]

фаза результирующей конфигурации изменяется, когда бит, который был первоначально в состоянии 1 , остается в состоянии 1 после проведенного преобразования. Следовательно, если $\bar{x}$ будет $n$-битной бинарной строкой, описывающей начальное состояние, и $\bar{y}-n$-битной бинарной строкой, описывающей результирующее состояние, то знак амплитуды определяется четностью поразрядного произведения $\bar{x}$ и $\bar{y}$, т. е. $(-)^{(\bar{x} \cdot \bar{y})}$. Мы получили преобразование Уолша-Адамара [4]. Эта операция (или тесно связанная с ней операция преобразования Фурье) одна из тех вещей, которые делают квантовые алгоритмы более мощными, чем классические, и образуют основу наиболее важных квантовомеханических алгоритмов.

Третье преобразование, которое нам понадобится, – это выборочное вращение фазы амплитуды в определенных состояниях. Преобразование, представленное здесь для системы из двух состояний, имеет форму:
\[
\left(\begin{array}{cc}
e^{j \phi_{1}} & 0 \\
0 & e^{j \phi_{2}}
\end{array}\right),
\]

где $j=\sqrt{-1}$ и $\phi_{1}, \phi_{2}$ – произвольные действительные числа. Заметим, что в отличие от преобразования Уолша-Адамара и других матриц преобразования состояний, вероятность каждого состояния остается той же, т. к. квадрат абсолютной величины амплитуды в каждом состоянии остается прежним.