グローバーのアルゴリズムを見る。書籍と textbook では少し進み方が違う気もするが、ここでは書籍をそのまま辿ってみる。
オラクルの部分については Bernstein-Vazirani のアルゴリズムのケースを思い出してみる。オラクルを含む量子ゲート $U_f$ を
$$
\begin{align*}
\ket{x} \xrightarrow{U_f} (-1)^{f(x)} \ket{x}
\end{align*}
$$
というようにとっていた。今回もこのケースで、$\ket{x} = \ket{\omega}$ の時にのみ $f(x) = 1$ となるので、$U_f$ によって、$U_f \ket{\omega} = - \ket{\omega}$ となる。
少し難しく感じるのは $U_s = - H^{\otimes n} X^{\otimes n} C^{n-1}Z X^{\otimes n} H^{\otimes n}$ の部分だ。簡単のため、$n=2$ として眺めてみたい。
直接計算で $- H^{\otimes 2} X^{\otimes 2} CZ X^{\otimes 2} H^{\otimes 2} = 2 \ket{s}\bra{s} - I$ を示すのは難しそう、というか綺麗な計算ができなかったので、代わりに $\ket{s}$ に適用して実際の値を見てみる:
$$
\begin{align*} - H^{\otimes 2} X^{\otimes 2} CZ X^{\otimes 2} H^{\otimes 2} \ket{s} &= - H^{\otimes 2} X^{\otimes 2} CZ X^{\otimes 2} H^{\otimes 2} H^{\otimes 2} \ket{0}^{\otimes 2} \\
&= - H^{\otimes 2} X^{\otimes 2} CZ X^{\otimes 2} \ket{0}^{\otimes 2} \\
&= - H^{\otimes 2} X^{\otimes 2} CZ \ket{1}^{\otimes 2} \\
&= H^{\otimes 2} X^{\otimes 2} \ket{1}^{\otimes 2} \\
&= H^{\otimes 2} \ket{0}^{\otimes 2} \\
&=\ket{s}
\end{align*}
$$
ということで、それっぽさがあることは分かった。[quant-ph/9605043] A fast quantum mechanical algorithm for database search でもこの等式は出ていないし、ニールセン&チャンにも書いていないようだが、どこに書いてあるか分かったら再度検証してみたい。
ゲートの演算を変形して同値であることを見るのは難しそうなので、計算基底状態に作用させてみる。
$$
\begin{align*}
U_s \ket{00} &= - H^{\otimes 2} X^{\otimes 2} CZ X^{\otimes 2} H^{\otimes 2} \ket{00} \\
&= - \frac{1}{2} H^{\otimes 2} X^{\otimes 2} CZ X^{\otimes 2} (\ket{00} + \ket{01} + \ket{10} + \ket{11}) \\
&= - \frac{1}{2} H^{\otimes 2} X^{\otimes 2} CZ (\ket{00} + \ket{01} + \ket{10} + \ket{11}) \\
&= - \frac{1}{2} H^{\otimes 2} X^{\otimes 2} (\ket{00} + \ket{01} + \ket{10} - \ket{11}) \\
&= - \frac{1}{2} H^{\otimes 2} (\ket{11} + \ket{10} + \ket{01} - \ket{00}) \\
&= - \frac{1}{2} H^{\otimes 2} (\ket{11} + \ket{10} + \ket{01} + \ket{00} - 2 \ket{00}) \\
&= H^{\otimes 2} (\ket{00} - H^{\otimes 2} \ket{00}) \\
&= \ket{s} -\ket{00}
\tag{1}
\end{align*}
$$
が分かる。
ところで、$j,k \in \Z_{\geq 0}$ に対して $\braket{j|k} = \delta_{jk}$ であるので、$ 0 \leq \ell \leq 2^n-1$ に対して
$$
\begin{align*}
\ket{s}\braket{s|\ell} = \ket{s} \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} \braket{x|\ell} = \frac{1}{\sqrt{2^n}} \ket{s}
\end{align*}
$$
が成立する。
よって、(1) 式は $2 \ket{s}\braket{s|00} - \ket{00} = (2 \ket{s}\bra{s} - I) \ket{00}$ と等しい。故に、$\ket{00}$ に対して、$U_s \ket{00} = (2 \ket{s}\bra{s} - I) \ket{00}$ が示せた。実は、残りも同様の計算で簡単に示せる:
- $U_s \ket{01} = (2 \ket{s}\bra{s} - I) \ket{01}$
- $U_s \ket{10} = (2 \ket{s}\bra{s} - I) \ket{10}$
- $U_s \ket{11} = (2 \ket{s}\bra{s} - I) \ket{11}$
よって、2 量子ビットで表現されるすべての状態に対して $U_s = 2 \ket{s}\bra{s} - I$ が成立する。
いずれのケースでも $X^{\otimes 2} H^{\otimes 2}$ 適用後に $\ket{11}$ になる状態に注意することになる。この状態だけ $CZ$ が有意に作用する。逆にそれ以外では $CZ$ は何も起こらないので、恒等ゲート $I$ と見做せる。これを踏まえて、次に一般の $n$ の場合を確認する。
