tecktom.com

出てくるもの（2）：N\sqrt N が最適であること（BBBV）

2026年10月15日10分で読めますAI生成教科書『虎の巻』第6部 第4章 Grover と探索の下界
目次
  1. 1回の問い合わせで引き離せる量
  2. 成功には大きく引き離すことが要る
  3. 下界が言っていること
  4. 木下の層

AI 生成・木下が未勉強

相対エントロピーから情報と物理を組み立てる　第6部 第4章 §6.4.4　★★★ 1回の問い合わせで dkvd_k^v を増やせる量は 2∥P^v∣ψk⟩∥2\lVert \hat P_v| \psi_{k} \rangle \rVert 以下で、足し上げると Δk≤4k2\Delta_k\le4k^2。成功には Δk≳N\Delta_k\gtrsim N が要るので k≳N/2k\gtrsim\sqrt N/2

1回の問い合わせで引き離せる量

6.4.1 節の一般のアルゴリズム (6.4.5) に戻る。候補のレジスタが ∣v⟩| v \rangle にある部分への射影を、作業用のレジスタも含めてP^v=∣v⟩⟨v∣⊗1\hat P_v=| v \rangle \langle v |\otimes\mathbf 1 と書く。∑vP^v=1\sum_v\hat P_v=\mathbf 1 で、O^v=1−2P^v\hat O_v=\mathbf 1-2\hat P_v である。

定理 6.4.3（問い合わせの回数と状態の離れ方 ★★★）

どの kk 回の量子アルゴリズムについても

Δk=∑v∥∣ψkv⟩−∣ψk⟩∥2≤4k2.(6.4.20)\Delta_k=\sum_v\lVert | \psi_k^v \rangle -| \psi_k \rangle \rVert ^2\le4k^2 .\tag{6.4.20}

証明

k+1k+1 回目の問い合わせの前後を比べる。∣ψk+1v⟩=U^k+1O^v∣ψkv⟩| \psi_{k+1}^v \rangle =\hat U_{k+1}\hat O_v| \psi_k^v \rangle、∣ψk+1⟩=U^k+1∣ψk⟩| \psi_{k+1} \rangle =\hat U_{k+1}| \psi_k \rangle で、ユニタリはノルムを変えないので

dk+1v=∥O^v∣ψkv⟩−∣ψk⟩∥≤∥O^v(∣ψkv⟩−∣ψk⟩)∥+∥(O^v−1)∣ψk⟩∥=dkv+2∥P^v∣ψk⟩∥.d_{k+1}^v=\lVert \hat O_v| \psi_k^v \rangle -| \psi_k \rangle \rVert \le\lVert \hat O_v(| \psi_k^v \rangle -| \psi_k \rangle )\rVert +\lVert (\hat O_v-\mathbf 1)| \psi_k \rangle \rVert =d_k^v+2\lVert \hat P_v| \psi_k \rangle \rVert .

1つ目の項はもう一度ユニタリ O^v\hat O_v を外し、2つ目は O^v−1=−2P^v\hat O_v-\mathbf 1=-2\hat P_v を使った。d0v=0d_0^v=0 から始めて足し上げるとdkv≤2∑j=0k−1ajvd_k^v\le2\sum_{j=0}^{k-1}a_j^v（ajv=∥P^v∣ψj⟩∥a_j^v=\lVert \hat P_v| \psi_j \rangle \rVert）である。Cauchy–Schwarz の不等式 (∑j=0k−1ajv)2≤k∑j=0k−1(ajv)2(\sum_{j=0}^{k-1}a_j^v)^2\le k\sum_{j=0}^{k-1}(a_j^v)^2 を使い、vv について和を取ると、∑v(ajv)2=∑v∥P^v∣ψj⟩∥2=1\sum_v(a_j^v)^2=\sum_v\lVert \hat P_v| \psi_j \rangle \rVert ^2=1 なので

Δk≤4∑v(∑j=0k−1ajv)2≤4k∑j=0k−1∑v(ajv)2=4k2.□\Delta_k\le4\sum_v\Bigl(\sum_{j=0}^{k-1}a_j^v\Bigr)^2\le4k\sum_{j=0}^{k-1}\sum_v(a_j^v)^2=4k^2 . \quad\square

証明の要は、問い合わせ1回で ∣ψv⟩| \psi^v \rangle を ∣ψ⟩| \psi \rangle から引き離せる量が、空の状態 ∣ψj⟩| \psi_j \rangle が ∣v⟩| v \rangle に置いている振幅 ajva_j^v の2倍以下だという点にある。空の状態は vv を知らないので、その振幅を NN 個の候補に配るしかなく、∑v(ajv)2=1\sum_v(a_j^v)^2=1 から平均の振幅は 1/N1/\sqrt N 程度にとどまる。kk 回の問い合わせで dkvd_k^v は高々 2k/N2k/\sqrt N 程度しか増えず、その2乗の和 Δk\Delta_k は 4k24k^2 を超えない。1つ1つの dkvd_k^v は振幅（確率の平方根）の大きさで kk に比例して増えるので、確率の大きさで見ると k2k^2 に比例して増える。この形は前の節で見た Grover の成功確率 (2k+1)2/N(2k+1)^2/N と同じである。

成功には大きく引き離すことが要る

定理 6.4.4（成功の条件 ★★★）

どの vv についても、kk 回の後に候補のレジスタを測って vv が出る確率が 1−ε1-\varepsilon 以上（0≤ε<10\le\varepsilon <1）なら、

Δk≥N(1−ε)−2(1−ε)N.(6.4.21)\Delta_k\ge N(1-\varepsilon )-2\sqrt{(1-\varepsilon )N} .\tag{6.4.21}

証明

成功の確率は ∥P^v∣ψkv⟩∥2≥1−ε\lVert \hat P_v| \psi_k^v \rangle \rVert ^2\ge1-\varepsilon である。射影はノルムを増やさないので

dkv≥∥P^v(∣ψkv⟩−∣ψk⟩)∥≥∥P^v∣ψkv⟩∥−∥P^v∣ψk⟩∥≥1−ε−bv,bv=∥P^v∣ψk⟩∥.d_k^v\ge\lVert \hat P_v(| \psi_k^v \rangle -| \psi_k \rangle )\rVert \ge\lVert \hat P_v| \psi_k^v \rangle \rVert -\lVert \hat P_v| \psi_k \rangle \rVert \ge\sqrt{1-\varepsilon }-b^v , \qquad b^v=\lVert \hat P_v| \psi_k \rangle \rVert .

c=1−εc=\sqrt{1-\varepsilon } とおく。c−bv≥0c-b^v\ge0 なら2乗して (dkv)2≥(c−bv)2≥c2−2cbv(d_k^v)^2\ge(c-b^v)^2\ge c^2-2cb^v である。c−bv<0c-b^v<0 なら c2−2cbv<c2−2c2≤0≤(dkv)2c^2-2cb^v<c^2-2c^2\le0\le(d_k^v)^2 である。どちらの場合も (dkv)2≥c2−2cbv(d_k^v)^2\ge c^2-2cb^v が成り立つ。vv について和を取り、∑vbv≤N∑v(bv)2=N\sum_vb^v\le\sqrt{N\sum_v(b^v)^2}=\sqrt N（Cauchy–Schwarz）を使えばΔk≥Nc2−2cN\Delta_k\ge Nc^2-2c\sqrt N を得る。

系 6.4.5（探索の下界（BBBV） ★★★）

すべての vv について成功確率 1−ε1-\varepsilon 以上で当たりを見つける量子アルゴリズムは、

k≥12(1−ε)N−2(1−ε)N=1−ε2N (1+O(N−1/2))(6.4.22)k\ge\frac12\sqrt{(1-\varepsilon )N-2\sqrt{(1-\varepsilon )N}}=\frac{\sqrt{1-\varepsilon }}2\sqrt N\,\bigl(1+\mathcal{O}(N^{-1/2})\bigr)\tag{6.4.22}

回の問い合わせを必要とする。

定理 6.4.3 と定理 6.4.4 を合わせればよい。Grover のアルゴリズムは (π/4)N≈0.785N(\pi/4)\sqrt N\approx0.785\sqrt N 回で成功確率 1−O(1/N)1-\mathcal{O}(1/N) を達成し、下界は 0.5N0.5\sqrt N なので、両者は N\sqrt N の比例係数の違い（π/2\pi/2 倍）を除いて一致する。C. Zalka は、より細かい議論で、成功確率が 11 に近い場合の最小の回数が N→∞N\to\infty で (π/4)N(\pi/4)\sqrt N に一致すること、つまり Grover のアルゴリズムが比例係数まで含めて最適であることを示した1C. Zalka (1999), Phys. Rev. A 60, 2746。下の脚注へ。

Grover のアルゴリズム自身で Δk\Delta_k を計算しておく。空のオラクルでは G^=R^s\hat G=\hat R_s で、R^s∣s⟩=∣s⟩\hat R_s| s \rangle =| s \rangle なので ∣ψk⟩=∣s⟩| \psi_k \rangle =| s \rangle のままである。式 (6.4.13) から ⟨s∣ψkv⟩=sin⁡θsin⁡((2k+1)θ)+cos⁡θcos⁡((2k+1)θ)=cos⁡(2kθ)\langle s | \psi_k^v \rangle =\sin\theta\sin((2k+1)\theta)+\cos\theta\cos((2k+1)\theta)=\cos(2k\theta) で、

ΔkGrover=N(2−2cos⁡2kθ)=4Nsin⁡2(kθ)≤4Nk2sin⁡2θ=4k2(6.4.23)\Delta_k^{\mathrm{Grover}}=N\bigl(2-2\cos2k\theta\bigr)=4N\sin^2(k\theta)\le4Nk^2\sin^2\theta=4k^2\tag{6.4.23}

となる（∣sin⁡kθ∣≤k∣sin⁡θ∣\lvert \sin k\theta\rvert \le k\lvert \sin\theta\rvert を使った）。kθk\theta が小さいうちは sin⁡(kθ)≈kθ≈k/N\sin(k\theta)\approx k\theta\approx k/\sqrt N で、Grover のアルゴリズムは不等式 (6.4.20) をほぼ等号で満たしている。1回の問い合わせで引き離せる量の上限を、毎回ほぼ使い切っているということである。

下界が言っていること

下界 (6.4.22) は、オラクルの中身を問わず、問い合わせの回数だけで述べた主張である。したがって、問題に構造があってオラクルの中身を覗ける場合には当てはまらない。Shor のアルゴリズム（第6部第3章）が指数的に速いのは、位数発見という問題に周期という構造があり、量子 Fourier 変換がそれを読むからである。一方、充足可能性問題（SAT）のような NP 完全問題に対して、候補の割り当てを1つずつ試すことしかできないなら、2n2^n 個の候補に対して 2n/22^{n/2} 回ほどの問い合わせが要り、指数的な手間は残る。BBBV の論文は、この意味で「オラクルを相手にする限り、NP の問題が量子の多項式時間で解けるとは限らない」ことを示した。これは NP と BQP（量子の多項式時間で解ける問題のクラス）の関係を決めた結果ではなく、構造を使わない方法では足りないことを示した結果である。

例題 6.4.4　100万個の候補での上界と下界 ★★

オリジナルN=106N=10^6 とする。

  1. Grover のアルゴリズムの最適な回数 k∗k_* と、そのときの失敗の確率を求めよ。
  2. 誤りなく（ε=0\varepsilon =0）当てるのに要る問い合わせの回数の下界 (6.4.22) を求めよ。
  3. k=k∗k=k_* での ΔkGrover\Delta_k^{\mathrm{Grover}} と上限 4k24k^2 を比べよ。
解答

(1) θ=arcsin⁡(10−3)=1.0000002×10−3\theta=\arcsin(10^{-3})=1.0000002\times10^{-3}、π/(4θ)=785.40\pi/(4\theta)=785.40 なので k∗=785k_*=785。失敗の確率は 1−sin⁡2(1571θ)=4.2×10−81-\sin^2(1571\theta)=4.2\times10^{-8} で、下限 sin⁡2θ=10−6\sin^2\theta=10^{-6} よりずっと小さい（角 (2k∗+1)θ(2k_*+1)\theta がたまたま π/2\pi/2 に近い）。

(2) 12106−2×103=12998000=499.5\frac12\sqrt{10^6-2\times10^3}=\frac12\sqrt{998000}=499.5 なので、少なくとも 500500 回。古典の手順では誤りなく当てるのに N−1=999999N-1=999999 回かかる。

(3) Δ785Grover=4×106sin⁡2(785θ)=2.00×106\Delta_{785}^{\mathrm{Grover}}=4\times10^6\sin^2(785\theta)=2.00\times10^6、上限は 4×7852=2.46×1064\times785^2=2.46\times10^6 である。kθ=0.785≈π/4k\theta=0.785\approx\pi/4 まで来ると sin⁡(kθ)\sin(k\theta) は kθk\theta より目に見えて小さくなるので、等号から離れる。成功のためには定理 6.4.4 から Δk≥106−2×103=9.98×105\Delta_k\ge10^6-2\times10^3=9.98\times10^5 が要り、Grover はその約2倍まで引き離している。

1　C. Zalka (1999), Phys. Rev. A 60, 2746。

木下の勉強ステータス

木下はまだこの記事を勉強していません。

AI（Claude）が書いた教材を、木下が勉強しながら公開しています。式と数値は検算していますが、誤りが残っているかもしれません。誤りのご指摘・削除のご依頼をいただければ直します。 連絡先：support@tecktom.com

目次

この記事が含まれている連載

連載AI生成教科書『虎の巻』授業とは別に、分野をまたいで気になったことを AI（Claude）が教材にし、木下が勉強しながら公開しています。上の段は AI が書いた本文、下の段は木下が勉強したあとに書いた文です。1787本の記事・木下 智貴
← AI生成教科書『虎の巻』の記事一覧へ