Цикл шага (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_{i j}=2 / N, \quad \text { если } \quad i
eq j \quad \text { и } \quad D_{i i}=-1+2 / N .
\]

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

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

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

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