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$ はどの量子算法でも下げられない。
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 回だけである。
この記事の公式が成り立つのは次の条件のもとである。
| 量 | 式 | 条件 | 根拠 |
|---|---|---|---|
| 回転の角 | $\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 |
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 になる。
量子の算法を、問い合わせのない部分を表すユニタリ変換 $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 つ探すには、次のようにする。
使う公式: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)。
$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$ からなる。
$\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 行目 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する