一応 textbook の Grover's Algorithm も確認をしておく。
> Circuit Construction of a Grover Oracle
を開くとごちゃごちゃ書いてあるが、Deutsch-Jozsa アルゴリズムを思い出して、オラクルの問い合わせゲート $U_f$ として $\ket{x}\ket{y} \xrightarrow{U_f} \ket{x}\ket{y \oplus f(x)}$ となるものを考える。ここで $\oplus$ は XOR と考えるか、或いは modulo 2 の和とする。$\ket{y} = \ket{-} = \frac{1}{\sqrt{2}}(\ket{0} - \ket{1})$ であるので、
$$
\begin{align*}
U_f \ket{x}\ket{-} = \frac{1}{\sqrt{2}}(\ket{x}\ket{f(x)} - \ket{x}\ket{1 \oplus f(x)})
\end{align*}
$$
となるが、$\ket{x} \neq \ket{\omega}$ では、右辺は $\frac{1}{\sqrt{2}}(\ket{x}\ket{0} - \ket{x}\ket{1 \oplus 0}) = \ket{x}\ket{-}$ となり、$\ket{x} = \ket{\omega}$ では、$\frac{1}{\sqrt{2}}(\ket{x}\ket{1} - \ket{x}\ket{1 \oplus 1}) = -\ket{x}\ket{-}$ となる。つまり併せると、
$$
\begin{align*}
U_f \ket{x}\ket{-} = (-1)^{f(x)} \ket{x}\ket{-}
\end{align*}
$$
の形になっている。この時に、第 1 レジスタだけ見ると、グローバーのアルゴリズムにおけるオラクルの問い合わせゲートになっているよということが書いてある。
“位相キックバック” の話が出てくるのは分かりにくいが・・・第 1 レジスタを制御ビットならぬ制御レジスタとして考え、$\ket{x} = \ket{\omega}$ の時だけ、第 2 レジスタ・・・補助ビットに $X$ ゲートが作用するという解釈のようだ。$X$ ゲートは固有値 $-1$ と固有ベクトル $\ket{-}$ を持つので・・・
$$
\begin{align*}
\ket{0}^{\otimes n}\ket{-} \xrightarrow{H_1^{\otimes n}} &\ \ket{+}^{\otimes n} \ket{-} \\
=&\ \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} \ket{x} \ket{-} \\
\xrightarrow{CX}&\ -\frac{1}{\sqrt{2^n}} \ket{\omega} \ket{-} + \frac{1}{\sqrt{2^n}} \sum_{x=0,x\neq\omega}^{2^n-1} \ket{x} \ket{-} \\
\xrightarrow{H_1^{\otimes n}}&\ -\frac{2}{\sqrt{2^n}} H_1^{\otimes n} \ket{\omega} \ket{-} + \ket{0}^{\otimes n}\ket{-}
\end{align*}
$$
みたいな感じで、第 1 レジスタのほうの振幅に $X$ ゲートの固有値 $-1$ が紛れ込むことを言っているように思う。
この後の説明は暫く書籍と同じで、Example: 2 Qubits も書籍付属コードと同等である。
5. Solving Sudoku using Grover's Algorithm は気にならないわけではないのだが、先を急ぎたいので一旦触れないでおく。
