Цикл шага (ii) — суть алгоритма. Каждая итерация этого цикла увеличивает амплитуду искомого состояния на $O(1/\sqrt{N})$. В результате за $O(\sqrt{N})$ повторений цикла амплитуда, а следовательно, и вероятность оказаться в желаемом состоянии достигнет величины $O(1)$. Чтобы увидеть, что амплитуда увеличивается на $O(1/\sqrt{N})$ при каждом повторении цикла, мы, во-первых, покажем, что преобразование диффузии $D$, можно интерпретировать как операцию инверсии относительно среднего. Обычная инверсия — это операция поворота фазы и, как обсуждалось в последнем абзаце 1.1, она унитарна. Сейчас будет показано, что операция инверсии относительно среднего (точно определенная ниже) — также унитарная операция и эквивалентна преобразованию диффузии $D$, используемому на шаге (ii)а алгоритма.

Пусть $a$ обозначает усредненную по всем состояниям амплитуду, т. е. если $a_i$ — это амплитуда $i$-го состояния, то среднее есть $(1/N)\sum _{i=1}^N{a}_i$. В результате преобразования $D$ амплитуда в каждом состоянии увеличивается (уменьшается) таким образом, что после этой операции она настолько ниже (выше) $a_i$, насколько она была выше (ниже) до нее.
Преобразование диффузии $D$ определяется следующим образом:
$$D_{ij}=2/N,\text{ если }ieqj\text{ и }{D}_{ii}=-1+2/N.$$

Рис. 1. Инверсия относительно среднего.
Заметим, что $D$ можно представить в форме $D=-I+2P$, где $I-$ тождественная матрица и $P$ — проекционная матрица с $P_{ij}=1/N$ для всех $i$ и $j$. Легко проверить, что $P$ обладает такими свойствами: во-первых, $P^2=P$, и, кроме того, $P$, действуя на любой вектор $v$, дает вектор, каждая составляющая которого равна среднему по всем составляющим. Используя тот факт, что $P^2=P$, из представления $D=-I+2P$ немедленно получаем, что $D^2=I$ и, следовательно, преобразование $D$ унитарно. Чтобы показать, что $D$ — это инверсия относительно среднего, посмотрим, что случится, когда $D$ действует на произвольный вектор $\overline{u}$. Представляя $D$ как $-I+2P$, получаем, что $D\overline{u}=(-I+2P)\overline{u}=-\overline{u}+2P\overline{u}$. Как установлено выше, каждая составляющая вектора $P\overline{u}$ есть $A$, где $A$ есть среднее по всем составляющим вектора $\overline{u}$. Следовательно, $i$-ая составляющая вектора $D\overline{u}$ равна $(-{\overline{u}}_i+2A)$, что можно записать как $(A+(A-{\overline{u}}_i))$, что в точности есть инверсия относительно среднего.

Далее рассмотрим ситуацию на рис. 2 , когда эта операция применяется к вектору со всеми составляющими, кроме одной, имеющими амплитуду равную $C/\sqrt{N}$, где $C$ лежит между $1/2$ и 1 , а одна составляющая равна $-\sqrt{1-C^2}$.

Среднее $A$ всех составляющих приблизительно равно $C/\sqrt{N}$. Так как каждая из $(N-1)$ составляющих приблизительно равна среднему, они не изменяются существенно в результате инверсии относительно среднего. Одна составляющая, которая была отрицательной, теперь стала положительной, и ее величина возросла на $2C/\sqrt{N}$.

В цикле шага (ii) параграфа 3 , вопервых, амплитуда выбранного состояния обращается (это фазовое вращение и, следовательно, правильная квантовомеханическая операция, как обсуждалось в последнем абзаце параграфа 1.1). Потом
Рис. 2. Операция инверсии относительно среднего применяется к суперпозиции, где все, кроме одной, компоненты первоначально равны и имеют величину $O(1/\sqrt{N})$. проводится операция инверсии относительно среднего. Это увеличивает амплитуду избранного состояния при каждой итерации на $2C/\sqrt{N}$. Следовательно, пока амплитуда единственного состояния, т. е. $\sqrt{1-C^2}$, меньше чем $1/\sqrt{2}$, увеличение в ее величине больше, чем $1/\sqrt{2N}$. Отсюда немедленно следует, что существует число $M$ меньшее, чем $\sqrt{N}$, такое, что за $M$ повторений цикла на этапе (ii) величина амплитуды отыскиваемого состояния будет превосходить $1/\sqrt{2}$. Следовательно, если теперь производить измерение состояния системы, она будет находиться в желаемом состоянии с вероятностью большей, чем 0.5 .