Как упоминалось в параграфе 1.1, квантово-механические операции, которые могут быть реализованы в терминах унитарных операций, – это локальные матрицы переходов, т. е. матрицы, в которых только постоянное число элементов в каждом столбце не равно нулю. Преобразование диффузии $D$, определенное на этапе (ii)b алгоритма это: $D_{i j}=2 / N$, если $i
eq j$, и $D_{i i}=-1+2 / N . D$, как представлено выше, не есть локальная матрица перехода, т. к. здесь осуществляется переход из каждого состояния во все $N$ состояний. Используя преобразование Уолша-Адамара (см. 1.1), $D$ можно представить как произведение трех локальных унитарных преобразований $D=W R W$, где $R$ – матрица фазового поворота и $W$ – матрица преобразования Уолша-Адамара, определенные как $R_{i j}=0$, если $i
eq j ; R_{i i}=1$, если $i=0 ; R_{i i}=-1$, если $i
eq 0 . W_{i j}=2^{-n / 2}(-1)^{(\bar{i} \cdot \bar{j})}, \bar{i}$ – это бинарное представление $i$, и $\bar{i} \cdot \bar{j}$ определяет поразрядное произведение двух $n$-битных строк $\bar{i}$ и $\bar{j}$.

Каждая из матриц $W$ и $R$ – это локальная матрица перехода. $R$, определенная выше, – это фазовый поворот и ясно, что она локальна. $W$, как она реализована в 1.1 , – это локальная матрица перехода на каждом бите.

Вычислим $W R W$ и убедимсн, что это действительно $D . R$ может быть записана в виде $R=R_{1}+R_{2}$, где $R_{1}=I, I$ – тождественная матрица, и $R_{2,00}=2, R_{2, i j}=0$, если $i
eq 0, j
eq 0$. Замечая, что $M M=I$, где $M$ – это матрица, определенная в 1.1 , легко доказать, что $W W=I$ и, следовательно, $D_{1}=W R_{1} W=-I$. Вычислим теперь $D_{2}=W R_{2} W$. Из стандартного матричного произведения имеем: $D_{2, a d}=\sum_{b, c} W_{a b} R_{2, b c} W_{c d}$. Из определения $R_{2}$ и того факта, что $N=2^{n}$, следует, что $D_{2, a d}=2 W_{a 0} W_{0 d}=\left(2 / 2^{n}\right)(-1)^{(\bar{a} \cdot \overline{0}+\overline{0} \cdot \bar{d})}=2 / N$. T. е. $D_{2}$ равна $2 / N$, и сумма двух матриц $D_{1}$ и $D_{2}$ дает $D$.

Квантовый алгоритм поиска этой статьи, вероятно, будет проще реализовать по сравнению с многими другими известными квантовомеханическими алгоритмами, так как необходимые операции – это только преобразование Уолша-Адамара и операция условного сдвига фазы, каждая из которых относительно проста по сравнению с операциями, используемыми другими квантово-механическими алгоритмами [6]. К тому же квантовые алгоритмы, основанные на преобразовании УолшаАдамара (например, алгоритм поиска этой статьи, $[4,7,8]$ ), вероятно, много проще в реализации, чем те, что основываются на «большом преобразовании Фурье» $[1,6]$.

Приношу благодарности П.Шору, Е.Берстейну, Д.Брассарду, Н. Марголюсу и Д. Прескилу за полезные комментарии.