比べる2つの状態：印のついたオラクルと空のオラクル

相対エントロピーから情報と物理を組み立てる　第6部 第4章 §6.4.1　★★★ 探索問題を問い合わせの回数で測る。$k$ 回問い合わせた後の状態を、当たりの印がついたオラクルと空のオラクルとで比べ、その差の2乗和 $\Delta_k$ を章全体の物差しにする

$N$ 個の候補の中に1つだけ当たりがあり、候補 $y$ が当たりかどうかは「問い合わせ」を1回使えば分かるとする。候補の並びに何の手がかりも無ければ、古典の計算機は候補を1つずつ試すしかなく、半分の確率で当てるにも $N/2$ 回ほどの問い合わせが要る。L. K. Grover は、量子の計算機なら約 $(\pi/4)\sqrt N$ 回の問い合わせで、ほぼ確実に当たりを見つけられることを示した¹1L. K. Grover (1997), Phys. Rev. Lett. 79, 325。会議録の版は Proc. 28th Annual ACM Symposium on Theory of Computing (1996), p. 212。下の脚注へ閉じる。同じ頃、C. H. Bennett・E. Bernstein・G. Brassard・U. Vazirani は、どんな量子アルゴリズムも $\sqrt N$ に比例する数より少ない問い合わせでは当たりを見つけられないことを示していた²2C. H. Bennett, E. Bernstein, G. Brassard and U. Vazirani (1997), SIAM J. Comput. 26, 1510。4人の頭文字をとって BBBV と呼ぶ。下の脚注へ閉じる。上界と下界が $\sqrt N$ で一致するので、構造の無い探索について量子計算が得る速さは2乗の分だけで、それ以上ではない。

この章では、この2つの結果を同じ道具で読む。比べる2つの状態は、当たり $v$ の印がついたオラクル（問い合わせの箱）で $k$ 回問い合わせた後の状態 $| \psi_k^v \rangle$ と、何の印もない空のオラクルで同じ手順を走らせた後の状態 $| \psi_k \rangle$ である。アルゴリズムの仕事は、$N$ 個の $| \psi_k^v \rangle$ を互いに見分けられるほど $| \psi_k \rangle$ から引き離すことで、1回の問い合わせで引き離せる量には上限がある。当てる道具は2つある。1つは「平面の中の2つの反射の積は回転である」という幾何の事実で、Grover のアルゴリズムはこれだけで書くことができる。もう1つは、引き離した量を問い合わせごとに足し上げる三角不等式で、下界はこれから導かれる。出てくるものは3つである。1つ目は成功確率 $\sin^2((2k+1)\theta)$（$\sin\theta=1/\sqrt N$）と、それを一般化した振幅増幅、2つ目は $\sqrt N$ が最適であること（BBBV の下界）、3つ目は情報の側から見た読み方で、$k$ 回の問い合わせで得られる情報量が Holevo 量によって $(4k^2/N)\ln N$ 程度に押さえられることである。古典の問い合わせでは情報量が $k$ に比例して増えるのに対し、量子の問い合わせでは $k^2$ に比例して増える。$\sqrt N$ の速さはこの違いによる。

この章では次のように約束する。量子情報の章の流儀に従って Pauli 行列を $X,Y,Z$、恒等演算子を $\mathbf 1$ と書き、Hadamard ゲートは第3部・第6部第1章と同じく斜体の $H$ と書く。Shannon エントロピーはいつも引数つきの $H(V)$・$H(V\,|\,\hat V)$ で現れるので区別できる。sans の $\mathsf H$ は第3部第9章の検査行列に取ってある。探索の対象の演算子（オラクル・反射・回転）には帽子を付ける。当たりの候補を $v$、それを確率変数とみたものを $V$、アルゴリズムの答えを $\hat V$ と書く（第1部第6章 の Fano の不等式と同じ書き方）。対数は自然対数で、情報量の単位は nat である。候補の数を数える場面ではビットのほうが読みやすいので、$\ln2$ で割ってビットでも示す。

探索問題と問い合わせの回数

$N=2^n$ 個の候補 $y\in\{0,1,\dots,N-1\}$ と、関数 $f:\{0,\dots,N-1\}\to\{0,1\}$ が与えられている。$f(y)=1$ となる $y$ を当たりと呼ぶ。まずは当たりがちょうど1つ（$v$ とする）の場合を考える。$f$ の中身は見えず、使えるのは「$y$ を入れると $f(y)$ を返す箱」だけである。この箱をオラクル、箱を1回使うことを1回の問い合わせと呼ぶ。探索の難しさは、計算の手間全体でなく、問い合わせの回数で測る。オラクルの中で何が起きているかを問わず、箱を使う回数だけを数えるので、下界の議論が「どれほど賢い手順でも」という形で書くことができる。

古典の場合を先に片づける。$k$ 回の問い合わせで異なる $k$ 個の候補を調べ、当たりが見つからなければ残りの $N-k$ 個から1つを当てずっぽうで選ぶとする。$v$ が一様に分布しているなら、成功する確率は

$$P_k^{\mathrm{cl}}=\frac kN+\Bigl(1-\frac kN\Bigr)\frac1{N-k}=\frac{k+1}N\tag{6.4.1}$$

で、問い合わせの回数に比例して増える。乱数を使っても、問い合わせの順番を工夫しても、この値は上がらない。$k$ 回の問い合わせで調べられる候補は高々 $k$ 個で、どの候補が当たりかについて事前に何の手がかりも無いからである。

量子のオラクル

量子の計算機でオラクルを使うには、それをユニタリ演算子にしておく必要がある。候補を入れる $n$ 量子ビットのレジスタと、答えを書き込む1量子ビットを用意して

$$\hat U_f| y \rangle | b \rangle =| y \rangle | b\oplus f(y) \rangle \qquad(b\in\{0,1\})\tag{6.4.2}$$

と定める。$\oplus$ は2を法とする足し算である。$\hat U_f$ は計算基底を置換するだけなのでユニタリで、2回使うと元に戻る。答えのビットを $| - \rangle =(| 0 \rangle -| 1 \rangle )/\sqrt2$ に用意すると、$| 0\oplus f(y) \rangle -| 1\oplus f(y) \rangle =(-1)^{f(y)}(| 0 \rangle -| 1 \rangle )$ なので

$$\hat U_f| y \rangle | - \rangle =(-1)^{f(y)}| y \rangle | - \rangle .\tag{6.4.3}$$

答えのビットは変わらず、当たりの候補にだけ符号 $-1$ が付く。この現象を位相キックバックと呼ぶ（第6部第2章 の位相推定でも同じ仕組みを使った）。答えのビットを省いて候補のレジスタだけを見ると、オラクルは

$$\hat O_v=\mathbf 1-2| v \rangle \langle v |\tag{6.4.4}$$

と書ける。これを位相オラクルと呼ぶ。以下ではもっぱら $\hat O_v$ を使う。何の印もない空のオラクルは $\hat O_\varnothing=\mathbf 1$ である。

一般の量子アルゴリズムの形

$k$ 回問い合わせる量子アルゴリズムは、どれも次の形に書くことができる。候補のレジスタと作業用のレジスタを合わせた空間で、決まった初期状態 $| \psi_0 \rangle$ から始め、オラクルと、オラクルに依らないユニタリ $\hat U_1,\dots,\hat U_k$ を交互にかける。オラクルは候補のレジスタにだけ作用し、作業用のレジスタには恒等演算子として作用する。最後に候補のレジスタを計算基底で測り、出た値を答え $\hat V$ とする。当たりが $v$ のとき、$k$ 回問い合わせた後の状態は

$$| \psi_k^v \rangle =\hat U_k\hat O_v\hat U_{k-1}\hat O_v\cdots\hat U_1\hat O_v| \psi_0 \rangle\tag{6.4.5}$$

で、空のオラクルを使った場合は $| \psi_k \rangle =\hat U_k\cdots\hat U_1| \psi_0 \rangle$ である。測定の途中に挟んでもよい測定や古典の処理は、補助の量子ビットを足せばユニタリの中に入れられるので、この形で一般性は失われない。

アルゴリズムが成功するには、$v$ ごとに異なる $N$ 個の状態 $| \psi_k^v \rangle$ を、測定で見分けられる程度に互いに離す必要がある。ところが、どの $| \psi_k^v \rangle$ も問い合わせをする前は同じ $| \psi_0 \rangle$ で、$v$ の違いはオラクルを通してしか入らない。そこで、この章で比べる2つの状態を

$$| \psi_k^v \rangle \ \text{（当たり }{v}\text{ の印がついたオラクル）}\qquad\text{と}\qquad| \psi_k \rangle \ \text{（空のオラクル）}\tag{6.4.6}$$

に取り、その離れ方を

$$d_k^v=\lVert | \psi_k^v \rangle -| \psi_k \rangle \rVert ,\qquad\Delta_k=\sum_{v=0}^{N-1}\bigl(d_k^v\bigr)^2\tag{6.4.7}$$

で測る。$\Delta_k$ は「$k$ 回の問い合わせで、$N$ 通りの当たりの状態を空の状態から合わせてどれだけ引き離したか」を表す量である。6.4.4 節で、1回の問い合わせで $\Delta_k$ を増やせる量に上限があること（$\Delta_k\le4k^2$）と、成功には $\Delta_k\gtrsim N$ が要ることを示す。2つを合わせると $k\gtrsim\sqrt N/2$ になる。

ベクトルの距離で比べる理由を一言述べておく。2つの純粋状態 $| \phi \rangle ,| \phi' \rangle$ を等確率で渡されて当てるとき、誤りの確率の最小値は$\frac12\bigl(1-\sqrt{1-\lvert \langle \phi | \phi' \rangle \rvert ^2}\bigr)$ である（Helstrom の限界。第3部第8章）。$\lVert | \phi \rangle -| \phi' \rangle \rVert ^2=2-2\operatorname{Re}\langle \phi | \phi' \rangle$ が小さければ $\lvert \langle \phi | \phi' \rangle \rvert$ は $1$ に近く、2つの状態はほとんど見分けられない。状態どうしの相対エントロピーは純粋状態どうしでは発散してしまうので、この章では見分けやすさをベクトルの距離で測り、相対エントロピーは 6.4.5 節で混合状態（平均の状態）に対して使う。

1　L. K. Grover (1997), Phys. Rev. Lett. 79, 325。会議録の版は Proc. 28th Annual ACM Symposium on Theory of Computing (1996), p. 212。

2　C. H. Bennett, E. Bernstein, G. Brassard and U. Vazirani (1997), SIAM J. Comput. 26, 1510。4人の頭文字をとって BBBV と呼ぶ。