グローバーの検索アルゴリズムの理論
この記事では、グローバーのアルゴリズムを機能させる数学的原理の詳細な理論的説明を示します。
数学的な問題を解決するためのグローバーのアルゴリズムの実際の実装については、「グローバーの検索アルゴリズムを実装する」を参照してください。
問題のステートメント
グローバーのアルゴリズムは、非構造化データ検索 (または 検索の問題) に対するソリューションを高速化し、従来のアルゴリズムよりも少ない手順で検索を実行します。 任意の検索タスクは、検索項目 $x$ を受け取る抽象関数 $f(x)$ で表すことができます。 項目 $x$ が検索タスクの解である場合には、$f(x)=1$ です。 項目 $x$ が解でない場合は、$f(x)=0$ となります。 "検索の問題" は、$f(x_0)$1$ である任意の項目 =x_0$ を探すことで構成されます。
特定の値 $x$ が有効な解であるかどうかを確認できる問題 ("はい/いいえ問題") は、探索問題の観点で定式化できます。 次はその例です。
- ブール値の満足可能性の問題: 一連のブール値を指定すると、セットは特定のブール式を満たしていますか?
- 旅行セールスマンの問題:すべての都市を結ぶ最短のループは何ですか?
- データベース検索の問題: データベース テーブルに x$$レコードが含まれていますか?
- 整数の因数分解の問題: 定数 $N$ は値 $x$ で割り切れるか?
グローバーのアルゴリズムが解決しようとしているタスクは、次のように表すことができます。古典的関数 $f(x):\{0,1\}^n \rightarrow\{0,1\}$ が与えられ、$n$ が検索空間のビット サイズであるときに、$f(x_0)$1$ である入力 =x_0$ を探します。 アルゴリズムの複雑さは、関数 $f(x)$ の使用回数によって測定されます。 古典的には、最悪のシナリオで $f(x)$ を合計 $N-1$ 回評価してすべての可能性を試す必要があります。ここで $N=2^n$ です。 $N-1$ 要素の後、それは最後の要素である必要があります。 グローバーの量子アルゴリズムでこの問題をはるかに高速に解き、累乗的な高速化を実現できます。 ここで、累乗的であることは、$\sqrt{N}$ 回に比べ、約 $N$ 回の評価しか必要でないことを暗に示しています。
アルゴリズムの概要
検索タスクに $N=2^n$ 個の対象項目があり、各項目に $0$ から $N-1$ までの整数を割り当てることで、それらにインデックスを付けたとします。 さらに、$M$ 個の異なる有効な入力があるとします。つまり、$M$ 個の入力があり、$f(x)=1$ であることを意味します。 アルゴリズムのステップは次のようになります。
- 開始時には、レジスタに $n$ 個の量子ビットがあり、状態 $\ket{0}$ に初期化されています。
- レジスタ内の各量子ビットに $H$ を適用して、レジスタを一様の重ね合わせになるように準備します。$$|\text{register}\rangle=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$$
- 次の操作をレジスタ $N_{\text{optimal}}$ 回数に適用します。
- 解の項目に対して $-1$ の条件付き位相シフトを適用する位相オラクル $O_f$。
- レジスタの各量子ビットに $H$ を適用します。
- $ を除くすべての計算の基底状態への条件付きの位相シフト $-1$\ket{0}$。 これはユニタリ演算 $-O_0$ によって表すことができます。$O_0$ は、$\ket{0}$ のみへの条件付きの位相シフトを表すためです。
- レジスタの各量子ビットに $H$ を適用します。
- 確率が非常に高い解である項目のインデックスを取得するために、レジスタを測定します。
- 有効なソリューションであるかどうかを確認してください。 それ以外の場合は、再度開始します。
$N_{\text{optimal}}=\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{{1}{{2}\right\rfloor$ は、レジスタを測定することによって正しい項目が取得される確率を最大化する、最適な反復回数です。
Note
手順 3.b、3.c、および 3.d の共同適用は、通常、グローバーの拡散操作
レジスタに適用される全体的なユニタリ演算は次のとおりです。
$$(-H^{\otimes n}O_0H^{\otimes n}O_f)^{N_{\text{optimal}}}H^{\otimes n}$$
レジスタの状態にステップバイステップで従う
このプロセスを説明するために、2 つの量子ビットだけがあり、有効な要素が $\ket{01} である単純なケースについて、レジスタの状態の数学的変換を考えてみましょう。$
レジスタは次の状態で開始されます。
$\ket{\text{register}}=\ket{{00}$
$H$ を各量子ビットに適用すると、レジスタの状態は次の値に変換されます。
$\ket{\text{register}}=\frac{{1}{\sqrt{4}}\sum_{i \in \lbrace 0,1 \rbrace}^2\ket{i}=\frac12(\ket{00}+\ket{01}+\ket{{10}+\ket{11})$
次に、フェーズ Oracle を適用して次の値を取得します。
$\ket{\text{register}}=\frac12(\ket{{00}-\ket{{01}+\ket{{10}+\ket{{11})$
次に、H$$各量子ビットに対して再び作用して、次の機能を提供します。
$\ket{\text{register}}=\frac12(\ket{{00}+\ket{{01}-\ket{{10}+\ket{{11})$
条件位相シフトが、$\ket{00}$を除くすべての状態に適用されるようになりました。
$\ket{\text{register}}=\frac12(\ket{{00}-\ket{{01}+\ket{{10}-\ket{{11})$
最後に、最初のグローバーイテレーションは、$H$ を再度適用して終了します。
$\ket{\text{register}}=\ket{{01}$
上記のステップに従うことにより、1 回の反復で有効な項目が見つかります。 後で確認するように、これは、N=4 と 1 つの有効な項目の場合、最適な回数は $N_{\text{}}=1$になるためです。
幾何学的な説明
グローバーのアルゴリズムが動作する理由を確認するために、このアルゴリズムを幾何学的な観点から見てみましょう。 $M$ 個の有効な解があると仮定すると、検索の問題の解ではないすべての量子状態の重ね合わせは次のようになります。
$$\ket{\text{bad}}=\frac{{1}{\sqrt{N-M}}\sum_{x:f(x)=0}\ket{x}$$
検索の問題の解であるすべての状態の重ね合わせは次のようになります。
$$\ket{\text{good}}=\frac{{1}{\sqrt{M}}\sum_{x:f(x)=1}\ket{x}$$
項目は有効でありかつ無効であることはできないため、良い と 悪い は相互に排他的な集合であり、状態は独立しています。 どちらの状態も、ベクトル空間内の平面の直交を形成します。 この平面を使用してアルゴリズムを視覚化できます。
次に、$\ket{\psi}$ が、$\ket{\text{good}}$ と $\ket{\text{bad}}$ にまたがる平面に存在する任意の状態であるとします。 その平面内に存在する任意の状態は、次のように表現できます。
$$\ket{\psi}=\alpha\ket{\text{good}} + \beta\ket{\text{bad}}$$
ここで、$\alpha$ と $\beta$ は実数です。 次に、反射演算子 $R_{\ket{\psi}}$ を加えましょう。ここで、$\ket{\psi}$ は、その平面に存在する任意の量子ビット状態です。 演算子は次のように定義されます。
$$R_{\ket{\psi}}=2\ket{\psi}\bra{\psi}-\mathcal{I}$$
これは $\ket{\psi}$ に関する反射演算子と呼ばれます。それは、$\ket{\psi}$ の方向に関する反射であると幾何学的に解釈できるためです。 これを確認するために、$\ket{\psi}$ によって形成される平面の直交基底と、その直交補空間 $\ket{\psi^{\perp}}$ を考えます。 平面の任意の状態 $\ket{\xi}$ は、このような基底に分解できます。
$$\ket{\xi}=\mu \ket{\psi} + \nu {\ket{\psi^{\perp}}}$$
演算子 $R_{\ket{\psi}}$ を $\ket{\xi}$ に適用すると、次のようになります。
$$R_{\ket{\psi}}\ket{\xi}=\mu \ket{\psi} - \nu {\ket{\psi^{\perp}}}$$
演算子 $R_{\ket{\psi}}$ により、コンポーネントは $\ket{\psi}$ と直交するように反転されますが、$\ket{\psi}$ コンポーネントは変更されません。 したがって、$R_{\ket{\psi}}$ は $\ket{\psi}$ に関する反射です。
グローバーのアルゴリズムでは、最初に $H$ をすべての量子ビットに適用した後、すべての状態の一様の重ね合わせから開始します。 これは次のように記述できます。
$$\ket{\text{all}}=\sqrt{\frac{M}{N}}\ket{\text{good}} + \sqrt{\frac{N-M}{N}}\ket{\text{bad}}$$
このため、状態は平面内に存在します。 等しい重ね合わせから測定する場合に正しい結果を得る確率は、$|\bra{\text{すべて^2}}\ket{\text{M/N}}|で、=$これはランダムな推測から期待される値であることに注意してください。
オラクル $O_f$ により、検索問題の任意の解に負の位相が追加されます。 そのため、$\ket{\text{bad}}$ 軸に関する反射として記述できます。
$O_f = R_{\ket{\text{bad}}}= 2\ket{\text{bad}}\bra{\text{bad}} - \mathbb{I}$
同様に、条件付きの位相シフト $O_0$ は、状態 $\ket{0}$ に関する反転された反射にすぎません。
$O_{0}= R_{\ket{0}}= -2\ket{{0}\bra{{0} + \mathbb{I}$
この事実を知ると、グローバー拡散操作 $-H^{\otimes n} O_{0} H^{\otimes n}$ も、すべての}$$\ket{状態に関するリフレクションであることを簡単に確認できます。 次のことを行います。
$-H^{\otimes n} O_{{0} H^{\otimes n}=2H^{\otimes n}\ket{0}\bra{{0}H^{\otimes n} -H^{\otimes n}\mathbb{I}H^{\otimes n}= 2\ket{\text{all}}\bra{\text{all}} - \mathbb{I}= R_{\ket{\text{all}}}$
グローバーのアルゴリズムの各反復が、$R_{\ket{\text{bad}}}$ と $R_{\ket{\text{all}}}$ という 2 つの反射の合成であることが示されました。
各グローバー反復を組み合わせた効果は、角度 $2\theta$ の反時計回りでの回転です。 さいわい、角度 $\theta$ は簡単に見つかります。 $\theta$ は $\ket{\text{all}}$ と $\ket{\text{bad}}$ の間の角度なので、スカラー積を使用してその角度を見つけることができます。 $\cos{\theta}=\braket{\text{all}|\text{bad}}$ であることがわかっているので、計算する必要があるのは $\braket{\text{all}|\text{bad}}$ です。 $\ket{\text{all}}$ を $\ket{\text{bad}}$ と $\ket{\text{good}}$ について分解することから、次のようになります。
$$\theta = \arccos{\left(\braket{\text{all}|\text{bad}}\right)}= \arccos{\left(\sqrt{\frac{N-M}{N}}\right)}$$
レジスタの状態と $\ket{\text{良好}}$ な状態の間の角度は、反復のたびに減少し、有効な結果を測定する確率が高くなります。 この確率を計算するには、適切な$|\braket{\text{レジスタ}|\text{^2を計算}}|するだけで済む。$ 適切 $\ket{\text{}}$ と $\ket{\text{レジスタ}}$ の間の角度は、$\gamma (k)$として示されます。ここで、$k$ は反復回数です。
$\gamma = \frac{\pi}{2}-\theta -2k\theta =\frac{\pi}{{2} -(2k + 1) \theta $
したがって、成功の確率は次のようになります。
$$P(\text{success}) = \cos^2(\gamma(k)) = \sin^2\left[(2k +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)\right]$$
最適な反復回数
成功の確率を反復回数の関数として書くことができるため、成功の確率関数を (ほぼ) 最大化する最小の正の整数を計算することによって、最適な反復回数 $N_{\text{optimal}}$ が見つかります。
$\sin^2{x}$ が、$x=\frac{\pi}{2}$ で最初の最大値に達することがわかっているので、次のようになります。
$\frac{\pi}{{2}=(2k_{\text{optimal}} +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)$
次のように表示されます。
$$k_{\text{optimal}}=\frac{\pi}{4\arccos\left(\sqrt{1-M/N}\right)}-1/2 =\frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{1}{2}-O\left(\sqrt\frac{M}{N}\right)$$
最後のステップでは、$\arccos \sqrt{1-x}=\sqrt{x} + O(x^{3/2})$ となります。
したがって、$N_{\text{optimal}}=\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{{1}{{2}\right\rfloor$ を選択できます。
複雑さの分析
前の分析から、有効な項目を見つけるには、オラクル $O_f\left のクエリが \sqrt{\frac{O}{(}}\rightN$M$)$ 回必要です。 ただし、時間の複雑さに関して効率的にアルゴリズムを実装できるでしょうか。 $O_0$ は、$n$ 個のビットに対するブール演算の計算に基づいており、$O(n)$ 個のゲートを使用して実装可能なことがわかっています。 また、2 層のアダマール ゲート $n$ 個もあります。 したがって、これらのコンポーネントの両方で、1 回の反復あたりに必要なゲートの数は $O(n)$ 個だけです。 $N=2^n$ であるため、$O(n)=O(log(N))$ となります。 したがって、$O\left(\sqrt{\frac{N}{M}}\right)$ 回の反復と、1 回の反復あたり $O(log(N))$ 個のゲートが必要な場合、合計時間の複雑さ (オラクルの実装は考慮しない) は $O\left(\sqrt{\frac{N}{M}}log(N)\right)$ です。
アルゴリズムの全体的な複雑さは、最終的には、oracle $O_fの実装の複雑さに依存します$。 関数の評価が従来のコンピューターよりも量子コンピューターではるかに複雑な場合、技術的にはクエリの使用が少なくても、量子の場合はアルゴリズムの全体的なランタイムが長くなります。
関連情報
グローバーのアルゴリズムについて引き続き学習する場合は、次のいずれかのソースを確認してください。
- Lov K. Grover 氏による元の論文
- Nielsen、M. A. の量子検索アルゴリズム のセクション。 &アンプ;チュアン、I. L. (2010)。 Quantum Computation and Quantum Information (量子コンピューティングと量子の情報)。
- Arxiv.org のグローバーのアルゴリズム