Groverのアルゴリズム

同義語:Grover's algorithmGroverの探索アルゴリズムGrover's search algorithm

概要

Groverのアルゴリズム(Grover's algorithm)とは、$N$ 個の候補のうち条件をみたす $M$ 個($0< M< N$)の 1 つを、条件の判定を符号として返す神託への約 $\frac{\pi}{4}\sqrt{N/M}$ 回の問い合わせで、確率 $1-M/N$ 以上で見つける量子計算の算法である。$\sin^2\theta=M/N$ とすると、解の符号の反転と一様な状態についての鏡映の合成は角 $2\theta$ の回転で、$k$ 回後の成功確率は $\sin^2((2k+1)\theta)$ になる。成功確率 $a$ の任意の量子算法を約 $1/\sqrt a$ 回で確実にする振幅増幅に一般化され、問い合わせの回数の位数 $\sqrt N$ はどの量子算法でも下げられない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 量子計算, ユニタリ行列

Grover のアルゴリズム(Grover's algorithm)は、$N$ 個の候補の中から条件をみたすものを 1 つ探す問題を、条件の判定(神託への問い合わせ)を約 $\frac{\pi}{4}\sqrt{N/M}$ 回だけ使って解く量子計算の算法である($M$ は条件をみたす候補の個数)。古典の算法では、どんな工夫をしても確率 $1/2$ で見つけるのに $N/2$ 回程度の問い合わせが必要なので、問い合わせの回数は平方根の程度に減る。この算法は Grover による(Gro96)。
算法の中身は、状態ベクトルを 2 つの鏡映の合成で少しずつ回転させることである。回転の角は $\sin^2\theta=M/N$ で決まり、$k$ 回の反復で解を得る確率は $\sin^2((2k+1)\theta)$ になる。この見方は、成功確率 $a$ の任意の量子算法を約 $1/\sqrt a$ 回の繰り返しで確実にする 振幅増幅 に一般化される。
この記事では、振幅増幅の回転の公式を証明し、そこから Grover のアルゴリズムの問い合わせの回数と成功確率を導く。さらに、どんな量子算法も $\sqrt N$ の定数倍より少ない問い合わせでは探索できないことを、混成の論法で証明する。解の個数が分からない場合の扱いも述べる。量子ビット・量子回路・測定の定義は 量子計算 に従う。

定義と使える条件

以下、$\mathcal H$ を有限次元の複素内積空間、$\{|x\rangle\}$ をその正規直交基底(計算基底)とし、状態は単位ベクトルである。状態 $\psi$ を測定すると、基底の元 $x$ が確率 $|\langle x,\psi\rangle|^2$ で得られる(量子計算 の定義「測定」)。

探索問題と神託

$N\ge2$ とし、$f\colon\{0,1,\dots,N-1\}\to\{0,1\}$ を 判定関数、$A_f:=f^{-1}(1)$ を 解の集合、$M:=|A_f|$ とする。$f$ は次の 位相の神託 を通してだけ使えるとする。
$$ S_f|x\rangle:=(-1)^{f(x)}|x\rangle\qquad(0\le x< N). $$
$S_f$ を 1 回施すことを $f$ への 問い合わせ 1 回と数える。解を 1 つ出力する問題を 探索問題 という。

ビットを書き換える神託 $|x\rangle|b\rangle\mapsto|x\rangle|b\oplus f(x)\rangle$ からは、補助の量子ビットを $(|0\rangle-|1\rangle)/\sqrt2$ にしておくことで $S_f$ が 1 回の問い合わせで作れる(量子計算 の補題「符号の書き込み」)。

振幅増幅の設定

$\mathcal A$ を $\mathcal H$ のユニタリ変換、$|0\rangle$ を基底の 1 つの元、$\psi:=\mathcal A|0\rangle$ とする。基底の元のうち「良い元」の集合を決め、良い元の張る部分空間への直交射影を $\Pi$ とする。$a:=\|\Pi\psi\|^2$ を $\mathcal A$ の 成功確率 といい、$0< a< 1$ のとき $\theta\in(0,\pi/2)$ を $\sin^2\theta=a$ で定める。
$$ S_\chi:=I-2\Pi,\qquad S_0:=I-2|0\rangle\langle0|,\qquad Q:=-\mathcal A S_0\mathcal A^{-1}S_\chi $$
とおき、$Q$ を 振幅増幅の反復 という。

$-\mathcal AS_0\mathcal A^{-1}=\mathcal A(2|0\rangle\langle0|-I)\mathcal A^{-1}=2\psi\psi^*-I$ なので、$Q$ は「良い元の振幅の符号を反転し、そのあと $\psi$ の方向の成分を残してほかの成分の符号を反転する」変換である。$\psi^*$ は $\psi$ の共役転置を表す。
Grover の反復 は、$N=2^n$、$\mathcal H=(\mathbb C^2)^{\otimes n}$、$\mathcal A=H^{\otimes n}$(Hadamard 門をすべての量子ビットに施す)、良い元を解の集合 $A_f$ とした場合の $Q$ である。このとき $\psi=u:=N^{-1/2}\sum_x|x\rangle$、$S_\chi=S_f$、$a=M/N$ である。$2uu^*-I=H^{\otimes n}(2|0\rangle\langle0|-I)H^{\otimes n}$ は $f$ を使わずに量子回路で作れるので、反復 1 回の問い合わせは $S_f$ の 1 回だけである。
この記事の公式が成り立つのは次の条件のもとである。

  1. $f$ には神託の問い合わせを通してだけ触れる(問い合わせの回数を数える意味がある)。
  2. 解の個数 $M$ が分かっていて、$0< M< N$ である(反復の回数の選び方に使う)。
  3. 振幅増幅では、$\mathcal A$ は測定を含まないユニタリ変換で、その逆 $\mathcal A^{-1}$ も施せる。

公式の表

量式条件根拠
回転の角$\sin^2\theta=M/N$(一般には $\sin^2\theta=a$)$0< M< N$定義
$k$ 回後に解を得る確率$\sin^2((2k+1)\theta)$$k\ge0$thm-gr-amp
反復の回数$k=\lfloor\pi/(4\theta)\rfloor\le\frac{\pi}{4}\sqrt{N/M}$$0< M< N$cor-gr-grover
そのときの成功確率$1-M/N$ 以上(一般には $1-a$ 以上)同上cor-gr-grover
解が $4$ 分の $1$ のとき$M=N/4$ なら $k=1$ で確率 $1$$\theta=\pi/6$$\sin^2(3\theta)=1$
個数が分からないとき$0\le j< m$ から一様に選んだ $j$ 回の平均の成功確率は $\frac12-\frac{\sin(4m\theta)}{4m\sin2\theta}$ で、$m\ge1/\sin2\theta$ なら $\frac14$ 以上$0< M< N$lem-gr-random
個数が分からないときの期待回数$O(\sqrt{N/M})$$1\le M\le 3N/4$証明しない:BBHT98 Theorem 3
量子の下界解が 1 つのとき、すべての解で確率 $1/2$ 以上を保証するには $\sqrt{N/40}$ 回以上$N\ge32$thm-gr-lower
古典の下界同じ保証には $N/2-1$ 回以上乱数を使ってもよいprop-gr-classical

主定理:2 つの鏡映による回転

振幅増幅

def-gr-amp の設定で $0< a< 1$ とし、
$$ \psi_1:=\frac{\Pi\psi}{\sqrt a},\qquad\psi_0:=\frac{(I-\Pi)\psi}{\sqrt{1-a}} $$
とおく。すべての整数 $k\ge0$ について
$$ Q^k\psi=\sin\big((2k+1)\theta\big)\,\psi_1+\cos\big((2k+1)\theta\big)\,\psi_0 $$
が成り立つ。したがって $Q^k\psi$ を測定して良い元を得る確率は $\sin^2((2k+1)\theta)$ である。

平面の中での計算

$\psi_1$ は良い元の張る部分空間に、$\psi_0$ はその直交補空間にあるので、$\psi_0,\psi_1$ は正規直交である。$\psi=\sqrt a\,\psi_1+\sqrt{1-a}\,\psi_0=\sin\theta\,\psi_1+\cos\theta\,\psi_0$ である。$\varphi\in\mathbb R$ について
$$ w(\varphi):=\sin\varphi\,\psi_1+\cos\varphi\,\psi_0 $$
とおくと、$\psi=w(\theta)$ である。
$S_\chi=I-2\Pi$ は $\psi_1$ を $-\psi_1$ に、$\psi_0$ を $\psi_0$ に移すので、$S_\chi w(\varphi)=w(-\varphi)$ である。
$D:=2\psi\psi^*-I$ とおくと $Dv=2\langle\psi,v\rangle\psi-v$ である。$\langle\psi,w(\varphi)\rangle=\sin\theta\sin\varphi+\cos\theta\cos\varphi=\cos(\varphi-\theta)$ なので、
$$ Dw(\varphi)=2\cos(\varphi-\theta)\,w(\theta)-w(\varphi) $$
である。$\psi_1$ の係数は $2\cos(\varphi-\theta)\sin\theta-\sin\varphi=\sin(2\theta-\varphi)$、$\psi_0$ の係数は $2\cos(\varphi-\theta)\cos\theta-\cos\varphi=\cos(2\theta-\varphi)$ である(積和の公式 $2\cos\alpha\sin\beta=\sin(\beta+\alpha)+\sin(\beta-\alpha)$ と $2\cos\alpha\cos\beta=\cos(\beta+\alpha)+\cos(\beta-\alpha)$ を $\alpha=\varphi-\theta$、$\beta=\theta$ で使う)。よって $Dw(\varphi)=w(2\theta-\varphi)$ である。
$Q=DS_\chi$ なので
$$ Qw(\varphi)=Dw(-\varphi)=w(2\theta+\varphi) $$
であり、$k$ についての帰納法で $Q^k\psi=Q^kw(\theta)=w((2k+1)\theta)$ が従う。
$w(\varphi)$ を測定して良い元を得る確率は $\|\Pi w(\varphi)\|^2=\sin^2\varphi\,\|\psi_1\|^2=\sin^2\varphi$ である。$\square$

$Q$ は $\psi_0,\psi_1$ の張る平面の中で、角 $2\theta$ の回転として働く。最初の状態は良い元の方向 $\psi_1$ から角 $\pi/2-\theta$ だけ離れており、1 回の反復で $2\theta$ ずつ近づく。$k$ を大きくしすぎると $\psi_1$ を通り過ぎ、成功確率は再び下がる。

反復の回数と成功確率

$0< a< 1$ のとき $k:=\lfloor\pi/(4\theta)\rfloor$ とすると、$k\le\frac{\pi}{4\sqrt a}$ で、$Q^k\psi$ を測定して良い元を得る確率は $1-a$ 以上である。とくに Grover の反復では、$f$ への $\frac{\pi}{4}\sqrt{N/M}$ 回以下の問い合わせで、確率 $1-M/N$ 以上で解が得られる。

$\pi/(4\theta)-1< k\le\pi/(4\theta)$ より $\pi/2-\theta< (2k+1)\theta\le\pi/2+\theta$ である。$\sin^2$ は $\pi/2$ に関して対称で $[0,\pi/2]$ で増加するので、この区間で $\sin^2((2k+1)\theta)\ge\sin^2(\pi/2-\theta)=\cos^2\theta=1-a$ である。また $0< \theta< \pi/2$ では $\theta\ge\sin\theta=\sqrt a$ なので $k\le\pi/(4\theta)\le\pi/(4\sqrt a)$ である。Grover の反復では $a=M/N$ で、反復 1 回の問い合わせは 1 回である。$\square$

この結論は BHMT02 Theorem 2(p. 7)の形である。同論文 Lemma 1(p. 5)は $Q$ が $\psi_0,\psi_1$ の張る平面を保つことを、それに続く p. 6 の議論は平面の上の $Q$ の固有値が $e^{\pm2i\theta}$ であることを述べている。
図: N=1024 で反復の回数 k を横軸に、解が得られる確率を縦軸にとったグラフ。M=1 の曲線は k=25 で最大値およそ 0.9995 に達し、その後下がって k=50 付近でほぼ 0 になる。M=4 の曲線は周期が約半分で、k=12 で最大になり k=25 付近でほぼ 0 になる。 図: N=1024 で反復の回数 k を横軸に、解が得られる確率を縦軸にとったグラフ。M=1 の曲線は k=25 で最大値およそ 0.9995 に達し、その後下がって k=50 付近でほぼ 0 になる。M=4 の曲線は周期が約半分で、k=12 で最大になり k=25 付近でほぼ 0 になる。

下界:問い合わせは平方根より減らせない

量子の算法を、問い合わせのない部分を表すユニタリ変換 $U_0,U_1,\dots,U_T$ と、問い合わせ $T$ 回の列としてモデル化する。問い合わせを行う量子ビットの組(問い合わせのレジスタ)とそれ以外の作業用の量子ビットを合わせた空間で、$O|i\rangle|z\rangle:=(-1)^{f(i)}|i\rangle|z\rangle$ とし、算法の最後の状態は
$$ U_TOU_{T-1}O\cdots U_1OU_0|0\rangle $$
である。最後に出力のレジスタを測定し、得た値を答えとする。$U_t$ は $f$ によらない。

探索の下界

$N\ge32$ とする。上のモデルの算法が、ちょうど 1 点 $x$ だけで値 $1$ をとる $N$ 個の $f$($f=f_x$)のどれについても、確率 $1/2$ 以上で $x$ を出力するなら、$T\ge\sqrt{N/40}$ である。

混成の論法

$f_x$ の神託を $O_x$ と書き、すべての点で値 $0$ をとる関数の神託(恒等変換)を使った場合の最後の状態を $\Psi$、$O_x$ を使った場合を $\Psi^x$ とする。また、恒等の神託を使ったときの $t$ 回目の問い合わせの直前の状態を $\varphi_t:=U_{t-1}\cdots U_0|0\rangle$ とし、問い合わせのレジスタの値が $x$ の部分への直交射影を $P_x$ とする。$O_x=I-2P_x$ である。
上からの評価. $s=0,1,\dots,T$ について、最初の $s$ 回の問い合わせを恒等変換、残りを $O_x$ にした最後の状態を $h_s$ とすると、$h_0=\Psi^x$、$h_T=\Psi$ である。$h_{s-1}$ と $h_s$ は $s$ 回目の問い合わせだけが違い、その直前の状態はどちらも $\varphi_s$ なので、$s$ 回目より後の変換の積を $V_s$(ユニタリ)とすると
$$ h_{s-1}-h_s=V_s(O_x-I)\varphi_s=-2V_sP_x\varphi_s,\qquad\|h_{s-1}-h_s\|=2\|P_x\varphi_s\| $$
である。三角不等式と Cauchy–Schwarz の不等式により
$$ \|\Psi^x-\Psi\|^2\le\Big(\sum_{s=1}^T2\|P_x\varphi_s\|\Big)^2\le4T\sum_{s=1}^T\|P_x\varphi_s\|^2 $$
である。$x$ について足すと、各 $s$ で $\sum_x\|P_x\varphi_s\|^2=\|\varphi_s\|^2=1$ なので
$$ \sum_{x=0}^{N-1}\|\Psi^x-\Psi\|^2\le4T^2 $$
を得る。
下からの評価. 出力のレジスタの値が $x$ の部分への射影を $R_x$ とし、$p_x:=\|R_x\Psi\|^2$ とおく。$\sum_xp_x\le1$ なので $p_x>2/N$ となる $x$ は $N/2$ 個未満であり、$p_x\le2/N$ となる $x$ が $N/2$ 個以上ある。そのような $x$ について、仮定 $\|R_x\Psi^x\|^2\ge1/2$ とノルムの三角不等式から
$$ \|\Psi^x-\Psi\|\ge\|R_x(\Psi^x-\Psi)\|\ge\|R_x\Psi^x\|-\|R_x\Psi\|\ge\frac1{\sqrt2}-\sqrt{\frac2N}\ge\frac1{\sqrt2}-\frac14>\frac{9}{20} $$
である($N\ge32$ を使った)。$(9/20)^2>1/5$ なので $\sum_x\|\Psi^x-\Psi\|^2>\frac N2\cdot\frac15=\frac N{10}$ である。
2 つを合わせて $4T^2> N/10$、すなわち $T>\sqrt{N/40}$ である。$\square$

Grover の反復は $M=1$ で $\frac\pi4\sqrt N$ 回以下なので、問い合わせの回数の位数 $\sqrt N$ は最良である。この論法は BBBV97 Theorem 3.3(p. 7)にさかのぼり、同論文 Theorem 3.5(p. 8)は、ランダムな神託に相対化すると NP が時間 $o(2^{n/2})$ の量子計算に含まれないことを導いている。
比較のため、古典の算法の下界も示しておく。

古典の探索の下界

$f(x)$ の値を 1 点ずつ問い合わせる古典の算法(乱数を使ってよい)が、ちょうど 1 点 $x$ で値 $1$ をとるどの $f_x$ についても確率 $1/2$ 以上で $x$ を出力するなら、ある $f_x$ と乱数のある値について $N/2-1$ 回以上問い合わせる。

証明を開く

算法が最大 $T$ 回問い合わせるとし、$x$ を一様に選んだときの成功確率を考える。乱数の値を固定すると決定的な算法になる。それが問い合わせのたびに値 $0$ を受け取ったときに問い合わせる点の集合を $Q_0$($|Q_0|\le T$)、出力を $y_0$ とする。$x\notin Q_0\cup\{y_0\}$ なら、$f_x$ に対しても同じ点を問い合わせて値 $0$ を受け取り、$y_0\ne x$ を出力して失敗する。よって一様な $x$ での成功確率は $(T+1)/N$ 以下で、乱数について平均しても同じである。すべての $x$ で $1/2$ 以上なら平均も $1/2$ 以上なので、$T\ge N/2-1$ である。$\square$

解の個数が分からないとき

cor-gr-grover の $k$ は $M$ によって決まる。$M$ を誤ると回転が行き過ぎ、成功確率はほぼ $0$ にもなりうる(反例の表の 1 行目)。そこで、反復の回数を乱数で選ぶ。

反復の回数を一様に選ぶ

$0< M< N$、$\sin^2\theta=M/N$ とし、$m\ge1$ を整数とする。$\{0,1,\dots,m-1\}$ から一様に選んだ $j$ について Grover の反復を $j$ 回施して測定すると、解を得る確率は
$$ P_m=\frac12-\frac{\sin(4m\theta)}{4m\sin(2\theta)} $$
である。とくに $m\ge1/\sin(2\theta)$ なら $P_m\ge1/4$ である。

証明を開く

thm-gr-amp により $P_m=\frac1m\sum_{j=0}^{m-1}\sin^2((2j+1)\theta)=\frac1{2m}\sum_{j=0}^{m-1}\big(1-\cos((2j+1)2\theta)\big)$ である。$\beta:=2\theta$ とおくと、$2\sin\beta\cos((2j+1)\beta)=\sin((2j+2)\beta)-\sin(2j\beta)$ の和は隣り合う項が打ち消し合って $\sin(2m\beta)$ になるので、$\sum_{j=0}^{m-1}\cos((2j+1)\beta)=\frac{\sin(2m\beta)}{2\sin\beta}$ である($0< \beta< \pi$ なので $\sin\beta>0$)。代入して $P_m=\frac12-\frac{\sin(4m\theta)}{4m\sin2\theta}$ を得る。$m\sin2\theta\ge1$ なら第 2 項の絶対値は $\frac1{4m\sin2\theta}\le\frac14$ である。$\square$

この補題は BBHT98 Lemma 2(p. 3)である。同論文 §4 は、$m=1$ から始めて、失敗するたびに $m$ を $\min(\lambda m,\sqrt N)$ に増やす($1< \lambda< 4/3$、論文では $\lambda=6/5$)算法を与え、$1\le M\le3N/4$ のとき解が見つかるまでの反復の回数の期待値が $O(\sqrt{N/M})$ であることを示している(同 Theorem 3、p. 4。この記事では証明しない)。$M>3N/4$ のときは、一様に選んだ点を古典的に調べれば十分である。

計算の手順

Grover のアルゴリズムで解を 1 つ探すには、次のようにする。

  1. $N=2^n$ にそろえる(足りない分は $f=0$ とする)。判定関数 $f$ の論理回路から、量子計算 の補題「可逆な模倣」と「符号の書き込み」で $S_f$ を作る。
  2. $M$ が分かっていれば $\theta=\arcsin\sqrt{M/N}$、$k=\lfloor\pi/(4\theta)\rfloor$ とする。
  3. $|0^n\rangle$ に $H^{\otimes n}$ を施して $u$ を作り、$G=(2uu^*-I)S_f$ を $k$ 回施す。
  4. 測定して $x$ を得たら、$f(x)$ を 1 回計算して解かどうか確かめる。解でなければ 3 からやり直す(成功確率が $1-M/N$ 以上なので、やり直しの期待回数は小さい)。
  5. $M$ が分からなければ、lem-gr-random の後に述べた $m$ を増やす算法を使う。$M=0$ の可能性があるときは、反復の総数に上限($\sqrt N$ の定数倍)を置き、上限まで解がなければ「解なし」と答える。この答えは誤る確率がある。
    一般の振幅増幅では、手順 3 の $H^{\otimes n}$ を $\mathcal A$ に、$2uu^*-I$ を $-\mathcal AS_0\mathcal A^{-1}$ に置き換え、$\theta=\arcsin\sqrt a$ とする。

例題

$N=1024$、解が 1 つ

使う公式:thm-gr-amp、cor-gr-grover。
答え:$\theta=\arcsin(1/32)\approx0.031255$、$k=\lfloor\pi/(4\theta)\rfloor=25$ で、成功確率は $\sin^2(51\theta)\approx0.999461$ である。問い合わせは $25$ 回で、上限 $\frac\pi4\sqrt{1024}\approx25.13$ 以下である。

途中の計算を開く

$\pi/(4\theta)\approx25.13$ なので $k=25$。$51\theta\approx1.59401$ は $\pi/2\approx1.57080$ をわずかに越え、$\sin^2(51\theta)\approx0.999461\ge1-1/1024\approx0.999023$ である。$k=24$ では $0.998457$、$k=26$ では $0.992669$、$k=50$ では $0.000230$ に下がる。古典の算法では、すべての解で確率 $1/2$ を保証するのに $511$ 回以上が要る(prop-gr-classical)。

20 変数の論理式の唯一の充足割り当て

$n=20$ 変数の論理式で、充足する割り当てがちょうど 1 つあると分かっているとする。$N=2^{20}=1048576$、$M=1$ である。
使う公式:cor-gr-grover、thm-gr-lower。
答え:$k=804$ 回の反復で、失敗の確率は約 $2.43\times10^{-7}$ である。下界 thm-gr-lower は $\sqrt{N/40}\approx161.9$ 回で、古典の下界は $524287$ 回である。

途中の計算を開く

$\theta=\arcsin(2^{-10})$、$\pi/(4\theta)\approx804.25$ で $k=804$。$\frac\pi4\sqrt N=256\pi\approx804.25$ とほぼ一致する。$1-\sin^2(1609\theta)\approx2.43\times10^{-7}$。各反復は論理式の評価を可逆にした回路と $n$ 量子ビットの $2uu^*-I$ からなる。

成功確率 $0.1$ の算法の振幅増幅

$\mathcal A|00\rangle=\sqrt{0.9}\,|00\rangle+\sqrt{0.1}\,|11\rangle$(良い元は $|11\rangle$)とする。たとえば $\mathcal A$ は、1 つ目の量子ビットを角 $\arcsin\sqrt{0.1}$ だけ回す実の回転行列のあとに CNOT を施して作れる。
使う公式:thm-gr-amp、cor-gr-grover。
答え:$\theta=\arcsin\sqrt{0.1}\approx0.321751$、$k=\lfloor\pi/(4\theta)\rfloor=2$ で、成功確率は $\sin^2(5\theta)=0.99856$ である。$k=1$ では $0.676$、$k=3$ では約 $0.603194$ に戻る。

途中の計算を開く

$\sin\theta=\sqrt{0.1}$ から 3 倍角の公式で $\sin3\theta=3\sin\theta-4\sin^3\theta=2.6\sqrt{0.1}$、$\sin^2 3\theta=0.676$。5 倍角の公式 $\sin5\theta=5s-20s^3+16s^5$($s=\sin\theta$)で $\sin5\theta=\sqrt{0.1}(5-2+0.16)=3.16\sqrt{0.1}$、$\sin^25\theta=0.99856$。4 次元の行列 $Q=-\mathcal AS_0\mathcal A^{-1}S_\chi$ を直接掛けても同じ値になる。何もしないで $\mathcal A$ を繰り返すなら、同程度の確率($0.998$ 程度)を得るのに独立に約 $60$ 回が要る($0.9^{60}\approx0.0018$)。

個数が分からないときの平均の成功確率

$N=1024$、$M=1$ とし、lem-gr-random の $m$ を変える。
使う公式:lem-gr-random。
答え:$1/\sin(2\theta)\approx16.008$ である。$m=8$ では $P_m\approx0.079015$、$m=16$ では $0.272598$、$m=17$ では $0.299870$、$m=32$ では $0.594700$ である。$m\ge17$ で補題の保証 $P_m\ge1/4$ が働くが、$m=16$ でもたまたま $1/4$ を超えている。

途中の計算を開く

$\theta\approx0.031255$、$\sin(2\theta)\approx0.062469$。$m=17$ では $4m\sin2\theta\approx4.24792$ で、$P_{17}=\frac12-\frac{\sin(4m\theta)}{4m\sin2\theta}\approx0.299870$ である。定義の和 $\frac1{17}\sum_{j=0}^{16}\sin^2((2j+1)\theta)$ を直接計算しても同じ値になる。$m=32$ のように $m$ が大きいと $\sin(4m\theta)$ が負になり、$P_m$ は $1/2$ を超えうる。

使える条件と反例

外す条件反例成り立たなくなること
$k=\lfloor\pi/(4\theta)\rfloor$ を正しい $M$ で選ぶこと$N=1024$ で実際は $M=4$ なのに、$M=1$ として $k=25$ にする成功確率が約 $0.0023$ で、cor-gr-grover の $1-M/N$ 以上が成り立たない
$2uu^*-I$ が $u$ についての鏡映であること$N=1024$、$M=1$ で $2uu^*-I$ を $2\lvert0\rangle\langle0\rvert-I$ に替え、$k=25$ 回反復する成功確率は $1/1024$ のままで、thm-gr-amp の回転が起こらない
thm-gr-lower で「すべての $x$ で」成功すること何も問い合わせず、つねに $x_0$ を出力する算法$f_{x_0}$ には確率 $1$ で成功し、$T=0< \sqrt{N/40}$
thm-gr-lower で $f$ に神託を通してだけ触れること$f_x(y)=[y=x]$ が「入力を定数 $x$ と比べる回路」として中身ごと与えられる回路から $x$ を読み取れば問い合わせ $0$ 回で答えが出る
反例の確かめ

各行で外した条件のほかは、記事の設定のままである。

各行の確かめを開く

1 行目:$M=4$ では $\theta=\arcsin(1/16)\approx0.062541$ で、$\sin^2(51\theta)\approx0.0023$ である。$M=1$ の最適な回数は $M=4$ の最適な回数 $12$ の約 2 倍なので、回転が $\psi_1$ を通り過ぎてほぼ逆向きの位置に来る。

2 行目:$2|0\rangle\langle0|-I$ は $|0\rangle$ 以外の基底の元の符号を反転するだけで、$S_f$ も符号を変えるだけなので、どちらも各振幅の絶対値を変えない。$u$ の振幅はすべて $1/\sqrt{1024}$ なので、解の確率は何回反復しても $1/1024$ である。

3 行目:$x\ne x_0$ では成功確率が $0$ なので、定理の仮定を外したことになる。定理は最悪の場合についての主張である。

4 行目:問い合わせの回数は、$f$ を神託として与えたときだけ意味をもつ。論理式の充足可能性のように $f$ が回路で与えられる問題では、回路の構造を使う古典の算法が全探索より速いことがあり、この記事の下界はそれを禁じない。

よくある誤り

誤り正しくはなぜ
反復は多いほど成功確率が上がる成功確率は $k$ について周期的に上下するthm-gr-amp、図
$k$ 回後の成功確率は $\sin^2(k\theta)$$\sin^2((2k+1)\theta)$。初めから角 $\theta$ にあり、1 回で $2\theta$ 進むprf-gr-amp
Grover のアルゴリズムで NP 完全問題が多項式時間で解ける全探索の $N$ が $\sqrt N$ になるだけで、神託のモデルではこれ以上速くならないthm-gr-lower
反復 1 回に問い合わせが 2 回要る$2uu^*-I$ は $f$ を使わないので 1 回def-gr-amp の後の注意
解の個数を知らなくても $\frac\pi4\sqrt N$ 回でよい$M$ を誤ると成功確率がほぼ $0$ になる反例の表の 1 行目

補足

  • 振幅推定.$\psi_0,\psi_1$ の張る平面の上の $Q$ の固有値は $e^{\pm2i\theta}$ である(BHMT02 p. 6)。この角を量子 Fourier 変換で推定すると $a$ を推定でき、解の個数の近似にも使える(同論文 §4)。量子 Fourier 変換は Shorのアルゴリズム と同じ道具である。
  • 確実な成功.$a$ が分かっていれば、$\mathcal A$ と $\mathcal A^{-1}$ を $\Theta(1/\sqrt a)$ 回使って確率 $1$ で良い元を得る算法がある(BHMT02 Theorem 4、p. 11。この記事では証明しない)。$a=1/4$ では $\theta=\pi/6$ なので、工夫なしで $k=1$ のとき確率 $1$ になる。
  • 古典との比較.量子計算 の Deutsch–Jozsa のアルゴリズムでは、誤りを許さない古典の算法に対して問い合わせの回数が指数的に減る。探索では thm-gr-lower と prop-gr-classical により差は平方根の程度にとどまる。

関連項目

参考文献

[1]
Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC 1996), 1996, pp. 212–219
[2]
Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp, Tight bounds on quantum searching, Fortschritte der Physik, 1998, pp. 493–505。頁は arXiv 版(quant-ph/9605034v1)による:Lemma 2(p. 3)、§4 と Theorem 3(pp. 3–4)
[3]
Gilles Brassard; Peter Høyer; Michele Mosca; Alain Tapp, Quantum amplitude amplification and estimation, Quantum Computation and Information(S. J. Lomonaco, Jr. 編), Contemporary Mathematics, 2002, pp. 53–74。頁は arXiv 版(quant-ph/0005055v1)による:Lemma 1(p. 5)、p. 6、Theorem 2(p. 7)、Theorem 4(p. 11)、§4
[4]
Charles H. Bennett; Ethan Bernstein; Gilles Brassard; Umesh Vazirani, Strengths and weaknesses of quantum computing, SIAM Journal on Computing, 1997, pp. 1510–1523。頁は arXiv 版(quant-ph/9701001v1)による:Theorem 3.3(p. 7)、Theorem 3.5(p. 8)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する