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

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

Вычислим $WRW$ и убедимсн, что это действительно $D.R$ может быть записана в виде $R=R_1+R_2$, где $R_1=I,I$ — тождественная матрица, и $R_{2,00}=2,R_{2,ij}=0$, если $ieq0,jeq0$. Замечая, что $MM=I$, где $M$ — это матрица, определенная в 1.1 , легко доказать, что $WW=I$ и, следовательно, $D_1=W{R}_{1}W=-I$. Вычислим теперь $D_2=W{R}_{2}W$. Из стандартного матричного произведения имеем: $D_{2,ad}=\sum _{b,c}{W}_{ab}{R}_{2,bc}{W}_{cd}$. Из определения $R_2$ и того факта, что $N=2^n$, следует, что $D_{2,ad}=2W_{a0}{W}_{0d}=\left(2/2^n\right)(-1{)}^{(\overline{a}\cdot \bar{0}+\bar{0}\cdot \overline{d})}=2/N$. T. е. $D_2$ равна $2/N$, и сумма двух матриц $D_1$ и $D_2$ дает $D$.

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

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