当てる道具：2つの反射の積は回転

相対エントロピーから情報と物理を組み立てる　第6部 第4章 §6.4.2　★★★ オラクル $\hat O_v$ と平均のまわりの反射 $\hat R_s$ はどちらも反射で、2つの反射の積は角 $2\theta$ の回転になる。Grover のアルゴリズムはこの回転を $k$ 回くり返すだけである

2つの反射

すべての候補の一様な重ね合わせ

$$| s \rangle =\frac1{\sqrt N}\sum_{y=0}^{N-1}| y \rangle =H^{\otimes n}| 0\cdots0 \rangle\tag{6.4.8}$$

から始める。$H$ は Hadamard ゲート $H| b \rangle =(| 0 \rangle +(-1)^b| 1 \rangle )/\sqrt2$ である。$| s \rangle$ は「当たりについて何も知らない」状態で、計算基底で測るとどの候補も確率 $1/N$ で出る。

位相オラクル $\hat O_v=\mathbf 1-2| v \rangle \langle v |$ は、$| v \rangle$ の成分の符号だけを反転し、$| v \rangle$ に直交する成分はそのまま残す。$N$ 次元の空間で見ると、$| v \rangle$ に直交する超平面についての反射である。もう1つの演算子を

$$\hat R_s=2| s \rangle \langle s |-\mathbf 1=H^{\otimes n}\bigl(2| 0\cdots0 \rangle \langle 0\cdots0 |-\mathbf 1\bigr)H^{\otimes n}\tag{6.4.9}$$

と定める。$\hat R_s$ は $| s \rangle$ の成分を残し、$| s \rangle$ に直交する成分の符号を反転するので、$| s \rangle$ を通る直線についての反射である。成分で書くと $(\hat R_s\bm{c})_y=2\bar c-c_y$（$\bar c=\frac1N\sum_yc_y$ は振幅の平均）で、各振幅を平均のまわりに折り返す操作になっている。Grover の1回の反復を

$$\hat G_v=\hat R_s\hat O_v\tag{6.4.10}$$

と定める。1回の反復でオラクルを1回使う。

2次元の平面に閉じる

当たり $| v \rangle$ と、当たり以外の一様な重ね合わせ

$$| r \rangle =\frac1{\sqrt{N-1}}\sum_{y\neq v}| y \rangle\tag{6.4.11}$$

は直交する単位ベクトルで、$| s \rangle$ は

$$| s \rangle =\sin\theta\,| v \rangle +\cos\theta\,| r \rangle ,\qquad\sin\theta=\frac1{\sqrt N}\tag{6.4.12}$$

と、この2つで張られる平面の中にある。$\hat O_v$ は $| v \rangle$ と $| r \rangle$ をそれぞれ $-| v \rangle$ と $| r \rangle$ に写し、$\hat R_s$ は $\hat R_s| \phi \rangle =2\langle s | \phi \rangle | s \rangle -| \phi \rangle$ なので $| s \rangle$ を含む平面の中のベクトルを同じ平面の中に写す。したがって$\hat G_v$ はこの平面を保つ。$| s \rangle$ から始めれば、状態はいつまでもこの2次元の平面の中にとどまる。$N$ 次元の問題が、平面の中の幾何の問題になった。

証明

直線 $\ell_1$ を横軸に取り、角 $\beta$ の向きの直線についての反射を行列で書くと $F(\beta)=\begin{pmatrix}\cos2\beta&\sin2\beta\\ \sin2\beta&-\cos2\beta\end{pmatrix}$ である（角 $\beta$ の単位ベクトルを動かさず、それに直交する単位ベクトルの符号を反転することを、直接代入して確かめられる）。積を計算すると

$$F(\alpha)F(0)=\begin{pmatrix}\cos2\alpha&\sin2\alpha\\ \sin2\alpha&-\cos2\alpha\end{pmatrix}\begin{pmatrix}1&0\\0&-1\end{pmatrix} =\begin{pmatrix}\cos2\alpha&-\sin2\alpha\\ \sin2\alpha&\cos2\alpha\end{pmatrix},$$

これは角 $2\alpha$ の回転の行列である。

平面の中で $\hat O_v$ は $| r \rangle$ の直線についての反射、$\hat R_s$ は $| s \rangle$ の直線についての反射で、2つの直線は角 $\theta$ をなす。補題から次が従う。

$| s \rangle$ は $| r \rangle$ から角 $\theta$ の向きにあり、反復のたびに $2\theta$ ずつ $| v \rangle$ のほうへ回る。$k$ 回の後の角は $(2k+1)\theta$ で、これが $\pi/2$ に届けば状態は $| v \rangle$ そのものになる。図 6.4.1 にこの様子を描いた。振幅の言葉で言い直すと、$\hat O_v$ が当たりの振幅だけを負にし、$\hat R_s$ が平均のまわりで折り返すので、平均より大きく下に飛び出した当たりの振幅が、折り返されて平均より大きく上に出る。当たりの振幅は1回の反復で $1/\sqrt N$ の約2倍ずつ増え、当たりの確率は振幅の2乗なので、$k$ 回の後には $(2k+1)^2/N$ ほどになる。古典の成功確率 (6.4.1) が $k$ に比例するのに対し、量子の成功確率は $k^2$ に比例して増える。

回路で書く

$\hat R_s$ の中の $2| 0\cdots0 \rangle \langle 0\cdots0 |-\mathbf 1$ は、全体の符号 $-1$ を除けば「すべての量子ビットが $0$ のときだけ符号を反転する」ゲートである。全体の符号は測定の確率を変えないので無視してよい。これは各量子ビットを $X$ で挟んだ多重制御 $Z$ ゲートで作れて、多重制御のゲートは補助の量子ビットと Toffoli ゲートを $n$ に比例する数だけ使って組める（第6部第1章）。したがって1回の反復の手間はオラクル1回と $n=\log_2N$ に比例する数のゲートで、全体の手間は問い合わせの回数で決まる。