出てくるもの（3）：情報の側から見ると

相対エントロピーから情報と物理を組み立てる　第6部 第4章 §6.4.5　★★★ 当たりを一様な確率変数 $V$ とみると、$k$ 回の後に得られる情報量は Holevo 量 $\chi_k=S(\bar\rho_k)$ で押さえられ、$\chi_k\le h_{\mathrm b}(\delta_k)+\delta_k\ln(N-1)$（$\delta_k\le4k^2/N$）。情報量は問い合わせの回数の2乗に比例して増える

当たりを確率変数とみる

当たり $v$ が一様に分布する確率変数 $V$ だとする。アルゴリズムは $V=v$ のとき状態 $| \psi_k^v \rangle$ を作り、それを測って答え $\hat V$ を出すので、$V\to(\text{量子状態})\to\hat V$ は古典の値を量子状態に載せて送り、受け手が測る通信と同じ形をしている（第3部第7章）。送る状態の集まりは $\{1/N,| \psi_k^v \rangle \}$ で、平均の状態は

$$\bar\rho_k=\frac1N\sum_v| \psi_k^v \rangle \langle \psi_k^v |\tag{6.4.24}$$

である。比べる2つの状態は、ここでは各 $| \psi_k^v \rangle \langle \psi_k^v |$ と平均の $\bar\rho_k$ になる。その相対エントロピーの平均が Holevo 量

$$\chi_k=\frac1N\sum_vD\bigl(| \psi_k^v \rangle \langle \psi_k^v |\,\big\|\,\bar\rho_k\bigr)=S(\bar\rho_k)-\frac1N\sum_vS\bigl(| \psi_k^v \rangle \langle \psi_k^v |\bigr)=S(\bar\rho_k)\tag{6.4.25}$$

で（純粋状態の von Neumann エントロピーは $0$）、Holevo の限界から、どんな測定をしても

$$I(V;\hat V)\le\chi_k=S(\bar\rho_k)\tag{6.4.26}$$

が成り立つ。$| \psi_k^v \rangle$ がどれも同じなら $\bar\rho_k$ は純粋で $\chi_k=0$、互いに直交していれば $\bar\rho_k$ は $N$ 次元の上で一様で $\chi_k=\ln N$ になる。$\chi_k$ は「$N$ 個の状態が平均からどれだけ離れているか」を相対エントロピーで測った量で、6.4.1 節の $\Delta_k$ が距離で測った同じ量の言い換えになっている。

問い合わせで得られる情報量の上限

証明

$\bar\rho_k$ の最大固有値を下から押さえる。空の状態 $| \psi_k \rangle$ での期待値は$\langle \psi_k | \bar\rho_k | \psi_k \rangle =\frac1N\sum_v\lvert \langle \psi_k | \psi_k^v \rangle \rvert ^2$ である。$\lVert | \psi_k^v \rangle -| \psi_k \rangle \rVert ^2=2-2\operatorname{Re}\langle \psi_k | \psi_k^v \rangle$ から$\operatorname{Re}\langle \psi_k | \psi_k^v \rangle =1-(d_k^v)^2/2$ で、$(d_k^v)^2<1$ なら $\lvert \langle \psi_k | \psi_k^v \rangle \rvert ^2\ge(1-(d_k^v)^2/2)^2\ge1-(d_k^v)^2$、$(d_k^v)^2\ge1$ なら右辺が $0$ 以下なので同じ不等式が成り立つ。平均を取ると、最大固有値 $\lambda_{\max}$ は $\lambda_{\max}\ge\langle \psi_k | \bar\rho_k | \psi_k \rangle \ge1-\delta_k$ を満たす。$\bar\rho_k$ は $N$ 個の純粋状態の平均なので、0 でない固有値は高々 $N$ 個である。最大固有値が $1-\delta$ 以上で、0 でない固有値が $N$ 個以下の分布のエントロピーは、最大固有値がちょうど $1-\delta$ で残りの $\delta$ が $N-1$ 個に等分されたときに最大で（$\delta\le1-1/N$ のとき）、その値が $h_{\mathrm b}(\delta)+\delta\ln(N-1)$ である。この値は $\delta$ について $1-1/N$ まで増加するので、$\delta_k$ で押さえた式 (6.4.27) を得る。$\delta_k\le4k^2/N$ は定理 6.4.3 である。

この上限は、$k$ が小さいうちは $\chi_k\lesssim(4k^2/N)\ln N$ になる。比べるために古典の手順を見ておく。$k$ 回の問い合わせで $k$ 個の候補を調べると、答えの記録は「当たりが $j$ 番目だった」（各確率 $1/N$）か「どれも外れ」（確率 $1-k/N$）のどれかで、そこから得られる情報量は

$$I_k^{\mathrm{cl}}=\frac kN\ln N-\Bigl(1-\frac kN\Bigr)\ln\Bigl(1-\frac kN\Bigr)\approx\frac kN(\ln N+1)\tag{6.4.28}$$

である。古典の問い合わせは1回ごとにほぼ一定の情報量 $(\ln N)/N$ 程度を足し、$k$ に比例して情報を集める。量子の問い合わせで得られる情報量の上限は $k^2$ に比例して増え、上限の増え方で見ると、$k$ 回目の問い合わせが足せる分はおよそ $(8k/N)\ln N$ で、後の問い合わせほど多くを足せる。振幅が $k$ に比例して増え、情報は確率（振幅の2乗）の大きさで入ってくるからである。問い合わせ1回あたりの平均で見ても $\chi_k/k\lesssim(4k/N)\ln N$ で、これが $\ln N$ の全体を集めるのに $k\sim\sqrt N$ 回を要する理由になる。

Fano の不等式と合わせる

誤りなく当てる（$\hat V=V$）なら $I(V;\hat V)=H(V)=\ln N$ が要る。式 (6.4.27) の右辺が $\ln N$ に達するのは $\delta_k=1-1/N$ のときだけなので（その値を入れると $h_{\mathrm b}(1/N)+(1-1/N)\ln(N-1)=\ln N$）、

$$\frac{4k^2}N\ge1-\frac1N,\qquad\text{すなわち}\qquad k\ge\frac{\sqrt{N-1}}2\tag{6.4.29}$$

が要る。誤りを許すなら、Fano の不等式（第1部第6章）$H(V\,|\,\hat V)\le h_{\mathrm b}(P_{\mathrm{err}})+P_{\mathrm{err}}\ln(N-1)$ と$H(V\,|\,\hat V)=\ln N-I(V;\hat V)\ge\ln N-\chi_k$ を合わせて、誤りの確率の下限が出る。情報の側からの下界 (6.4.29) は、6.4.4 節の下界 (6.4.22) と同じ $\sqrt N/2$ になる。2つの議論は同じ不等式 $\Delta_k\le4k^2$ から出発しているので、これは偶然ではない。

Grover の状態での Holevo 量

Grover のアルゴリズムでは $\chi_k$ が閉じた形で求まる。$\bar\rho_k$ は候補の入れ替えで不変なので、$| s \rangle$ と、それに直交する $N-1$ 次元の空間とで対角になる。$| s \rangle$ 方向の固有値は $\frac1N\sum_v\lvert \langle s | \psi_k^v \rangle \rvert ^2=\cos^2(2k\theta)$ で、残りの $\sin^2(2k\theta)$ は $N-1$ 次元に等分される。したがって

$$\chi_k^{\mathrm{Grover}}=h_{\mathrm b}\bigl(\sin^2(2k\theta)\bigr)+\sin^2(2k\theta)\ln(N-1)\tag{6.4.30}$$

で、命題 6.4.6 の上限の形そのものになる（$\delta_k$ の代わりに $\sin^2(2k\theta)\le4k^2/N$ が入る）。計算基底で測ったときの情報量は、当たりが確率 $P_k$ で出て、外れが残りの $N-1$ 個に等分されるので

$$I_k^{\mathrm{Grover}}=\ln N-h_{\mathrm b}(P_k)-(1-P_k)\ln(N-1),\qquad P_k=\sin^2\bigl((2k+1)\theta\bigr)\tag{6.4.31}$$

である。図 6.4.3 に $N=256$ でこれらを示す。

図から2つのことが読み取れる。1つ目は、Grover の状態の Holevo 量が上限にほぼ沿って $k^2$ に比例して立ち上がることで、Grover のアルゴリズムは情報の側から見ても問い合わせを使い切っている。2つ目は、計算基底で測って実際に取り出せる情報量 $I_k$ が、途中では $\chi_k$ よりかなり小さいことである。途中の状態 $| \psi_k^v \rangle$ たちは互いに直交しておらず、1つずつ計算基底で測るとその重なりの分だけ情報を取りこぼす。最後の $k_*$ 回目で状態がほぼ $| v \rangle$ になり、直交するようになって初めて、$\chi_k$ と $I_k$ が揃って $\ln N$ に近づく。