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

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

В квантовой версии мы будем предполагать, что мы имеем квантовую логическую схему (или квантовый оракул), вычисляющую унитарный оператор $H_n\to H_n$
$$I_F:|x⟩\mapsto e^{\pi iF(x)}|x⟩.$$

Другими словами, $I_F$ — отражение, инвертирующее знак $|x_0⟩$ и оставляющее остальные классические состояния без изменений.

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