授業で習った形との対応

相対エントロピーから情報と物理を組み立てる　第6部 第4章 §6.4.6　★★ 量子計算の授業の Grover の演算子・回転角・反復回数の式と、この章の $\hat G_v=\hat R_s\hat O_v$・$\theta$・$k_*$ を並べる。角の定義が2倍ずれる流儀に注意

量子計算の授業や教科書では、Grover の反復を

$$G=H^{\otimes n}\bigl(2| 0 \rangle \langle 0 |-\mathbf 1\bigr)H^{\otimes n}O=(2| s \rangle \langle s |-\mathbf 1)\,O\tag{6.4.32}$$

と書き、「拡散変換」「平均のまわりの反転」と呼ぶことが多い。これはこの章の $\hat G_v=\hat R_s\hat O_v$ そのもので、式 (6.4.9) の書き方に当たる。「$2| 0 \rangle \langle 0 |-\mathbf 1$ の代わりに $\mathbf 1-2| 0 \rangle \langle 0 |$ を使う」流儀もあり、その場合は反復ごとに全体の符号 $-1$ が付くだけで、測定の確率は変わらない。

回転角の書き方には2つの流儀がある。この章は $| s \rangle$ と $| r \rangle$ のなす角を $\theta$（$\sin\theta=\sqrt{M/N}$）とし、1回の反復の回転角を $2\theta$ とした。回転角そのものを $\theta$ と呼び、$\sin(\theta/2)=\sqrt{M/N}$ と書く教科書もある。その流儀では成功確率は $\sin^2((2k+1)\theta/2)$、反復の回数は

$$R=\mathrm{round}\Bigl(\frac{\arccos\sqrt{M/N}}{\theta}\Bigr)\tag{6.4.33}$$

と書かれる。この章の記号に直すと（教科書の $\theta$ を $2\theta$ に置き換えて）$\arccos(\sin\theta)/(2\theta)=(\pi/2-\theta)/(2\theta)=\pi/(4\theta)-1/2$ で、これを四捨五入した値は、$\pi/(4\theta)$ がちょうど整数のときを除いて $k_*=\lfloor\pi/(4\theta)\rfloor$ と一致する。どちらの書き方でも、状態を $| \mathrm{good} \rangle$ に最も近づける回数を選んでいる。

「Grover のアルゴリズムは $\mathcal{O}(\sqrt N)$ 回の問い合わせで探索する」「これ以上速くはならない」という授業の2つの主張は、それぞれ式 (6.4.16) と系 6.4.5 に当たる。授業では下界を結果だけ述べることが多いが、この章では $\Delta_k\le4k^2$ と $\Delta_k\gtrsim N$ の2つの不等式から導いた。

古典の計算量の授業で習う「整列していないデータの探索は $\mathcal{O}(N)$」との対応にも注意が要る。量子の速さは問い合わせの回数についての主張で、データを量子の重ね合わせとして読み出す装置（量子 RAM）の手間や、1回の問い合わせにかかる時間は含んでいない。問い合わせ1回の時間が古典より長ければ、$N$ が大きくなるまで量子の方が速くはならない（例題 6.4.6）。Grover のアルゴリズムが実際に役立つのは、オラクルが「候補が条件を満たすかを計算する回路」として書ける場合で、データベースを引く場面ではない。