出てくるもの（1）：成功確率と振幅増幅

相対エントロピーから情報と物理を組み立てる　第6部 第4章 §6.4.3　★★★ 成功確率 $\sin^2((2k+1)\theta)$ を最大にする回数は約 $(\pi/4)\sqrt{N/M}$。回しすぎると下がるので、当たりの数を知らないときは回数を乱数で選ぶ。同じ回転は任意の手順の成功確率を上げる（振幅増幅）

最適な回数

成功確率 (6.4.14) は、角 $(2k+1)\theta$ が $\pi/2$ に最も近いときに最大になる。

$$k_*=\Bigl\lfloor\frac{\pi}{4\theta}\Bigr\rfloor\tag{6.4.15}$$

と選ぶと、$\frac\pi{4\theta}-1<k_*\le\frac\pi{4\theta}$ から $(2k_*+1)\theta$ は $\pi/2-\theta$ より大きく $\pi/2+\theta$ 以下になり、

$$P_{k_*}\ge\cos^2\theta=1-\frac1N\tag{6.4.16}$$

が成り立つ。$N$ が大きいと $\theta=\arcsin(1/\sqrt N)=1/\sqrt N+\mathcal{O}(N^{-3/2})$ なので $k_*\approx(\pi/4)\sqrt N$ である。

成功確率は $k$ の単調な関数ではない。$k_*$ を過ぎても回し続けると、状態は $| v \rangle$ を通り越して反対側へ回り、成功確率は下がっていく。およそ $2k_*$ 回で状態は $-| s \rangle$ の近くに戻り、成功確率は $1/N$ 程度まで落ちる。古典の探索では問い合わせを増やして損をすることはないので、ここは量子の探索に特有の性質である。図 6.4.2 に $N=64$ の成功確率を古典の (6.4.1) と並べて示す。

当たりが複数あるとき

当たりが $M$ 個あるとき（$1\le M<N$）は、$| v \rangle$ を当たりの一様な重ね合わせ $| \mathrm{good} \rangle =M^{-1/2}\sum_{f(y)=1}| y \rangle$ に、$| r \rangle$ を外れの一様な重ね合わせ $| \mathrm{bad} \rangle$ に置き換え、オラクルを $\hat O_f=\sum_y(-1)^{f(y)}| y \rangle \langle y |$ にすれば、前の節の議論がそのまま通る。$| s \rangle =\sin\theta| \mathrm{good} \rangle +\cos\theta| \mathrm{bad} \rangle$ で

$$\sin\theta=\sqrt{\frac MN},\tag{6.4.17}$$

成功確率（当たりのどれかが出る確率）は $\sin^2((2k+1)\theta)$、最適な回数は $\lfloor\pi/(4\theta)\rfloor\approx(\pi/4)\sqrt{N/M}$ である。当たりの割合が $1/4$ のときは $\theta=\pi/6$ で、1回の反復で確実に当たる（例題 6.4.2 と同じ角）。割合が $1/2$ を超えると $\theta>\pi/4$ で、反復するとかえって悪くなるので、そのときは反復せずに測ればよい。

当たりの数を知らないとき

最適な回数は $M$ によるので、$M$ を知らないと回数を決められない。$M=1$ のつもりで $(\pi/4)\sqrt N$ 回まわすと、本当は $M$ が大きかった場合に大きく回しすぎてしまう。M. Boyer・G. Brassard・P. Høyer・A. Tapp は、回数を乱数で選べばこの問題を避けられることを示した¹1M. Boyer, G. Brassard, P. Høyer and A. Tapp (1998), Fortschr. Phys. 46, 493。下の脚注へ閉じる。回数 $k$ を $\{0,1,\dots,m-1\}$ から一様に選ぶと、平均の成功確率は

$$\overline{P}_m=\frac1m\sum_{k=0}^{m-1}\sin^2\bigl((2k+1)\theta\bigr)=\frac12-\frac{\sin(4m\theta)}{4m\sin2\theta}\tag{6.4.18}$$

になる（$\sin^2x=\frac12(1-\cos2x)$ と、等差に並んだ角の余弦の和 $\sum_{k=0}^{m-1}\cos((2k+1)\varphi)=\sin(2m\varphi)/(2\sin\varphi)$ を $\varphi=2\theta$ で使う）。$m\ge1/\sin2\theta$ なら第2項の絶対値は $1/4$ 以下なので、$\overline P_m\ge1/4$ である。$M$ を知らないまま $m$ を $1$ から始めて一定の比で増やしていき、そのたびに乱数の回数だけ回して測り、当たりが出たら止める。この手順の問い合わせの回数の期待値は $\mathcal{O}(\sqrt{N/M})$ で、$M$ を知っている場合と同じ程度で済む。

振幅増幅

Grover の反復は、探索に限らない形に一般化できる。ある量子の手順 $\hat A$ が、初期状態から

$$\hat A| 0\cdots0 \rangle =\sqrt a\,| \mathrm{good} \rangle +\sqrt{1-a}\,| \mathrm{bad} \rangle\tag{6.4.19}$$

を作り、成功の部分 $| \mathrm{good} \rangle$ を見分ける位相オラクル $\hat O_{\mathrm{good}}$ が使えるとする。$| s \rangle$ を $\hat A| 0\cdots0 \rangle$ に、$\hat R_s$ を $\hat A(2| 0\cdots0 \rangle \langle 0\cdots0 |-\mathbf 1)\hat A^\dagger$ に置き換えた反復 $\hat Q=\hat A(2| 0\cdots0 \rangle \langle 0\cdots0 |-\mathbf 1)\hat A^\dagger\hat O_{\mathrm{good}}$ は、平面 $\operatorname{span}\{| \mathrm{good} \rangle ,| \mathrm{bad} \rangle \}$ の中で角 $2\theta_a$（$\sin^2\theta_a=a$）の回転になる（証明は補題 6.4.1 と同じ）。成功確率を $1$ に近づけるには、$\hat A$ と $\hat A^\dagger$ を約 $\pi/(4\sqrt a)$ 回ずつ使えばよい。手順をくり返して成功を待つ古典の方法では約 $1/a$ 回かかるので、ここでも2乗の速さが得られる。これを振幅増幅と呼ぶ²2G. Brassard, P. Høyer, M. Mosca and A. Tapp (2002), Contemp. Math. 305, 53。下の脚注へ閉じる。Grover のアルゴリズムは $\hat A=H^{\otimes n}$、$a=M/N$ の場合である。

振幅増幅を使うと、成功確率を正確に $1$ にすることもできる。$k=\lceil\pi/(4\theta)-1/2\rceil$ 回まわすと決め、角を少し小さい $\theta'=\pi/(2(2k+1))\le\theta$ に直せば、$(2k+1)\theta'=\pi/2$ で確実に当たる。角を小さくするには、補助の量子ビットを1つ足し、それを $\sqrt c| 1 \rangle +\sqrt{1-c}| 0 \rangle$（$c=\sin^2\theta'/\sin^2\theta$）に回してから、「当たりで、しかも補助の量子ビットが $1$」を新しい成功とみなせばよい。成功の確率が $a$ から $ca=\sin^2\theta'$ に下がり、角が $\theta'$ になる。

当たりの数を数える

平面の中の回転 $\hat G$ の固有値は $\mathrm{e}^{\pm2\mathrm{i}\theta}$ で、$| s \rangle$ は2つの固有ベクトルの重みが $1/2$ ずつの重ね合わせである。そこで、$\hat G$ を制御つきでかける位相推定（第6部第2章）で固有値の位相 $\pm\theta/\pi$ を読めば、$M=N\sin^2\theta$ から当たりの数が分かる。これを量子計数と呼ぶ。位相推定は2つの固有値のどちらかを確率 $1/2$ ずつで読むが、$\sin^2$ は符号によらないので、どちらを読んでも同じ $M$ が出る。

1　M. Boyer, G. Brassard, P. Høyer and A. Tapp (1998), Fortschr. Phys. 46, 493。

2　G. Brassard, P. Høyer, M. Mosca and A. Tapp (2002), Contemp. Math. 305, 53。