Все подпрограммы, описанные до настоящего момента, сводятся к некоторым тождествам в унитарных группах, содержащим произведения из не слишком большого числа операторов, действующих на подпространствах малой размерности. Они не содержат подпрограмм вывода, и поэтому не «вычисляют» что-либо в традиционном смысле этого слова. Сейчас мы опишем замечательный алгоритм квантового поиска, предложенный Л. Гровером. Этот алгоритм дает еще одно тождество этого типа, но, кроме того, показывает эффект наблюдения и способ, которым можно использовать квантовое скрещивание для того, чтобы использовать квантовый параллелизм.

Мы рассмотрим только самую простую версию алгоритма. Пусть $F: \mathbf{F}_{2}^{n} \rightarrow\{0,1\}$ – функция, принимающая значение 1 точно в одной точке $x_{0}$. Мы хотим вычислить $x_{0}$. Предположим, что $F$ вычислима за полиномиальное время, или, другой вариант – ее значения даются некоторым оракулом. Классический поиск $x_{0}$ требует в среднем около $N / 2$ определений значений $F$, где $N=2^{n}$.

В квантовой версии мы будем предполагать, что мы имеем квантовую логическую схему (или квантовый оракул), вычисляющую унитарный оператор $H_{n} \rightarrow H_{n}$
\[
I_{F}:|x\rangle \mapsto e^{\pi i F(x)}|x\rangle .
\]

Другими словами, $I_{F}$ – отражение, инвертирующее знак $\left|x_{0}\right\rangle$ и оставляющее остальные классические состояния без изменений.

Более того, положим $J=-I_{\delta}$, где $\delta: \mathbf{F}_{2}^{n} \rightarrow\{0,1\}$ дает значение 1 только в 0 , и $V=U_{1}^{(n-1)} \ldots U_{1}^{(0)}$, как в (16).