反復回数の選び方

グローバーのアルゴリズムにおいて、初期化ステップを実行した後、レジスタ $\mathsf{Q}$ の状態ベクトルは $\vert A_0\rangle$ と $\vert A_1\rangle$ が張る2次元部分空間の中に留まり続けることを確認しました。

目標は $A_1$ の要素 $x\in A_1$ を見つけることであり、状態 $\vert A_1\rangle$ を得ることができれば目標を達成できます。この状態を測定すると、必ず $x\in A_1$ という測定結果が得られるからです。 ステップ2で $t$ 回反復した後の $\mathsf{Q}$ の状態が

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle,$$

であることを踏まえると、$x\in A_1$ を測定で得る確率を最大化するために、

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

が絶対値として $1$ にできるだけ近くなるように $t$ を選ぶべきです。 $\theta \in (0,2\pi)$ の任意の角度に対して、$t$ が増加するにつれて $\sin((2t + 1)\theta)$ は 振動 しますが、必ずしも周期的ではありません。同じ値が2回以上得られる保証はありません。

当然、測定から $x\in A_1$ の要素が得られる確率を大きくすることに加え、操作 $G$ を $t$ 回適用すると関数 $f$ への $t$ 回のクエリが必要になるため、$t$ をできるだけ小さく選びたいところです。 $\sin( (2t + 1) \theta)$ を絶対値として $1$ に近づけることを目指しているので、自然な方法は

$$(2t + 1) \theta \approx \frac{\pi}{2}$$

となるように $t$ を選ぶことです。

$t$ について解くと

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}$$

が得られます。

もちろん $t$ は整数でなければならないので、この値をちょうど達成できるとは限りませんが、この値に最も近い整数を取ることができます。それは

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

です。

これがグローバーのアルゴリズムに推奨される反復回数です。 分析を進めると、この整数が目標値にどれだけ近いかが、アルゴリズムの性能に自然に影響することがわかります。

（補足として、目標値 $\pi/(4\theta) - 1/2$ がちょうど2つの整数の中間になる場合、この $t$ の式は切り上げた結果となります。クエリが1回少なくて済むという意味で切り捨てることも考えられますが、これは副次的な事柄であり、この授業においては重要ではありません。）

角度 $\theta$ の値は次の式で与えられることを思い出すと、

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr),$$

推奨される反復回数 $t$ は $A_1$ 内の文字列の数に依存することがわかります。 これは解の数がわからない場合に問題となりますが、その点については後で説明します。

唯一解探索

まず、$f(x)=1$ となる文字列 $x$ が1つだけ存在する場合に焦点を当てましょう。 別の言い方をすると、唯一解探索（Unique search）問題のインスタンスを考えているということです。 この場合、

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr),$$

であり、$N$ が大きくなると

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr) \approx \sqrt{\frac{1}{N}}$$

と便利に近似できます。 $\theta = 1/\sqrt{N}$ を次の式に代入すると、

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

次の結果が得られます。

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

$t$ は操作 $G$ を実行する回数であるだけでなく、アルゴリズムが必要とする関数 $f$ へのクエリ回数でもあることを思い出すと、$O(\sqrt{N})$ 回のクエリを必要とするアルゴリズムを得る方向に進んでいることがわかります。

次に、推奨される $t$ の選択がどれほどうまく機能するかを調べます。 最終的な測定が唯一の解を返す確率は次のように明示的に表せます。

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

第1引数の $N$ は探索対象の要素数を、第2引数の $1$ は解の数を表します。 少し後で、解が複数ある場合により一般的に同じ記法を使います。

以下は $N = 2^n$ の値を増やしたときの成功確率の表です。

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

これらの確率は単調増加ではないことに注意してください。 特に $N=4$ のとき、確実に解が得られるという興味深い異常があります。 しかし一般的に、すべての $N$ に対して

$$p(N,1) \geq 1 - \frac{1}{N}$$

が証明できるので、上の値が示唆するように、$N$ が大きくなる極限で成功確率は $1$ に近づきます。 これは良い結果です！

ただし、$p(N,1) \geq 1/2$ という弱い下界であっても、グローバーのアルゴリズムの有用性を示すのに十分です。 この手順を実行して得られた測定結果 $x$ が何であれ、$f$ への1回のクエリで $f(x) = 1$ かどうか常に確認できます。 この手順を1回実行した場合、$f(x) = 1$ となる唯一の文字列 $x$ を得るのに失敗する確率が高々 $1/2$ であるとすると、この手順を $m$ 回独立に実行した後に唯一の文字列 $x$ を得るのに失敗する確率は高々 $2^{-m}$ となります。 すなわち、$f$ への $O(m \sqrt{N})$ 回のクエリを使うことで、少なくとも $1 - 2^{-m}$ の確率で唯一の解 $x$ が得られます。 より良い下界 $p(N,1) \geq 1 - 1/N$ を使うと、この方法で $x\in A_1$ を見つける確率は実際には少なくとも $1 - N^{-m}$ であることがわかります。

複数の解

$A_1$ の要素数が変わると角度 $\theta$ も変わり、アルゴリズムの成功確率に大きな影響を与えることがあります。 簡潔さのために、解の数を $s = \vert A_1 \vert$ と書き、前と同様に $s\geq 1$ と仮定します。

動機付けの例として、上で考えた唯一解ではなく $s = 4$ 個の解がある場合を想像してみましょう。 この場合、

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{4}{N}} \biggr),$$

であり、$N$ が大きいとき $\vert A_1 \vert = 1$ の場合のほぼ2倍の角度になります。 何も知らないと仮定して、唯一解の場合と同じ $t$ の値を選んだとします。

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

次の確率の表が示すように、その結果は壊滅的なものになります。

$$\begin{array}{ll} N & \text{成功確率}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

今度は $N$ が無限大になると成功確率が $0$ に近づきます。 これは、唯一解のときの2倍の速さで回転しているため、目標の $\vert A_1\rangle$ を通り過ぎて $-\vert A_0\rangle$ の近くに到達してしまうからです。

しかし、代わりに推奨される $t$ の選択、すなわち

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

を

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

に対して使うと、性能は改善されます。 より正確には、この $t$ の選択により高い確率で成功します。

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

先ほどの主張を一般化すると、

$$p(N,s) \geq 1 - \frac{s}{N}$$

が証明できます。ここで先ほど示した記法を使っています。$p(N,s)$ は、$N$ 通りの可能性のうち合計 $s$ 個の解がある場合に、$t$ 回反復したグローバーのアルゴリズムを実行して解を得る確率を表します。

成功確率の下界 $1 - s/N$ はやや奇妙に見えます。解が多いほど下界が悪くなるからです。しかし $s$ が $N$ に比べて十分小さいという仮定のもとでは、成功確率は十分高いと結論づけることができます。 前と同様に、$p(N,s)$ が十分大きいという事実だけでアルゴリズムの有用性が示されます。

また、次のことも成り立ちます。

$$p(N,s) \geq \frac{s}{N}.$$

この下界は、$\Sigma^n$ から一様ランダムに選ばれた文字列 $x$ が解である確率を表しています。したがってグローバーのアルゴリズムは常にランダムな推測と同等以上の性能を持ちます。 （実際、$t=0$ のとき、グローバーのアルゴリズムはランダムな推測そのものです。）

次に、反復回数（したがってクエリ回数）

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

を

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{s}{N}}\biggr)$$

に対して調べましょう。

すべての $\alpha \in [0,1]$ に対して $\sin^{-1}(\alpha)\geq \alpha$ が成り立ち、したがって

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}$$

となります。

これより、

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}$$

が導かれます。

これは $s$ が増えるにつれてクエリ回数の節約につながります。 特に、必要なクエリ回数は

$$O\biggl(\sqrt{\frac{N}{s}}\biggr)$$

です。

解の数が不明な場合

解の数 $s = \vert A_1 \vert$ が未知である場合は、$t$ の選択を $s$ の情報に基づいて行うことができないため、別のアプローチが必要です。 実際、複数のアプローチがあります。

一つの簡単なアプローチは、

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

から一様ランダムに選ぶことです。 このように $t$ を選ぶと、解が存在すると仮定して常に40%以上の確率で解を見つけることができますが、これは自明ではなく、ここでは含めない分析が必要です。 しかしこれは直感的に理解できます。特に幾何学的な描像を考えると、このようにランダムな回数だけ $\mathsf{Q}$ の状態を回転させることは、$\vert A_0\rangle$ と $\vert A_1\rangle$ が張る空間でランダムな単位ベクトルを選ぶことに似ており、$\vert A_1\rangle$ の係数が十分大きい確率が高いです。 前述と同様の方法で結果を確認しながらこの手順を繰り返すことで、解を見つける確率を $1$ に非常に近づけることができます。

解が存在する場合に解の数 $s$ が未知であっても $O(\sqrt{N/s})$ 回のクエリで解を見つけ、$s=0$ のとき解が存在しないことを判定するのに $O(\sqrt{N})$ 回のクエリを要する、より洗練された方法があります。

基本的なアイデアは、$T$ の値を増加させながら、集合 $\{1,\ldots,T\}$ から $t$ を一様ランダムに選ぶことを繰り返し行うことです。 特に、$T = 1$ から始めて指数的に増加させ、解が見つかった時点で終了し、解がない場合に無駄なクエリを避けるために $T$ に上限を設けます。 解が多いほどより少ないクエリで済むという事実をこの手順は利用しています。 ただし、$T$ の増加率と各反復における成功確率のバランスに注意が必要です。 （例えば $T \leftarrow \lceil \frac{5}{4}T\rceil$ とすることが有効であることが分析によって示されています。一方、$T$ を2倍にすることは有効ではありません。これは増加が速すぎるためです。）

自明なケース

ここまでの分析を通じて、解の数が0でないことを仮定してきました。 実際、ベクトル

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

を参照することで、$A_0$ と $A_1$ がどちらも空でないことを暗黙的に仮定していました。 ここでは、これらの集合のいずれかが空の場合に何が起こるかを簡単に考えます。

分析に入る前に、明らかなことを観察しておきましょう。 $\Sigma^n$ のすべての文字列 $x$ が解であれば、測定したときに必ず解が得られます。解が1つも存在しない場合は、解が得られることはありません。 ある意味ではこれ以上深く考える必要はありません。

しかし、これらの自明なケースについて数学的に素早く確認することはできます。 $A_0$ と $A_1$ のいずれかが空になるのは $f$ が定数のときです。 $\Sigma^n$ のすべての $x$ に対して $f(x) = 0$ のとき $A_1$ は空であり、$\Sigma^n$ のすべての $x$ に対して $f(x) = 1$ のとき $A_0$ は空です。 このとき

$$Z_f \vert u\rangle = \pm \vert u\rangle$$

が成り立ち、したがって

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

したがって、これらのケースでは反復回数 $t$ によらず、測定は常に $\Sigma^n$ から一様ランダムな文字列 $x$ を返します。