グローバーのアルゴリズム

量子コンピューティング において、グローバーのアルゴリズム（量子探索アルゴリズムとも呼ばれる）は、非構造化探索のための量子アルゴリズムであり、特定の出力値を生成するブラックボックス関数への一意の入力を高い確率で見つける。${\displaystyle O({\sqrt {N}})}$関数の評価において、${\displaystyle N}$は関数の定義域の大きさです。これは1996年にインド系アメリカ人のコンピュータ科学者であるLov Groverによって考案されました。 ^{[ 1 ]}

古典計算における類似の問題はクエリ複雑度を持つ${\displaystyle O(N)}$（つまり、関数を評価する必要がある）${\displaystyle O(N)}$回数: すべての入力値を 1 つずつ試すより良い方法はありません。平均して、${\displaystyle N/2}$ステップ）。^{[ 1 ]}

チャールズ・H・ベネット、イーサン・バーンスタイン、ジル・ブラッサール、ウメシュ・ヴァジラニは、この問題に対する量子解は関数を評価する必要があることを証明した。$\displaystyle \Omega (\sqrt N)$回数なので、グローバーのアルゴリズムは漸近的に最適です。^{[ 2 ]} NP完全問題に対する古典的なアルゴリズムは指数関数的に多くのステップを必要とし、グローバーのアルゴリズムは非構造化探索の古典的な解法に対して最大で2次的な高速化しか提供しないため、グローバーのアルゴリズムだけではNP完全問題に対して多項式時間解法は提供されないことが示唆されます（指数関数の平方根は依然として指数関数であり、多項式関数ではないため）。^{[ 3 ]}

他の量子アルゴリズムは、古典的なアルゴリズムに比べて指数関数的な高速化をもたらす可能性があるのに対し、グローバーのアルゴリズムは二次的な高速化しか提供しません。しかし、二次的な高速化であっても、${\displaystyle N}$は大きく、グローバーのアルゴリズムは幅広い種類のアルゴリズムの高速化に適用できます。^{[ 3 ]}グローバーのアルゴリズムは、128 ビットの対称暗号鍵を約 2 ⁶⁴回、または 256 ビットの鍵を約 2 ^128回の総当たり攻撃で解読できます。ただし、グローバーのアルゴリズムが既存の古典的なアルゴリズムに比べて暗号化に著しくリスクを高めるとは限らないかもしれません。^{[ 4 ]}

グローバーのアルゴリズムは、振幅増幅などの変種とともに、幅広いアルゴリズムの高速化に使用できます。^{[ 5 ] [ 6 ] [ 7 ]}特に、サブルーチンとして網羅的探索を含むNP完全問題のアルゴリズムは、グローバーのアルゴリズムによって高速化できます。^{[ 6 ]} 3SATに対する最悪ケースの複雑さの観点から、現在の理論上の最良アルゴリズムは、その一例です。一般的な制約充足問題も、グローバーによって2乗倍の高速化が見られます。^{[ 8 ]}これらのアルゴリズムは、入力がオラクルの形式で与えられる必要はありません。グローバーのアルゴリズムは、ビットの集合が3SATインスタンスを満たすかどうかをチェックする関数などの明示的な関数とともに適用されるためです。ただし、グローバーのアルゴリズムがこれらの問題に対する最良の実用的なアルゴリズムを高速化できるかどうかは不明です。

グローバーのアルゴリズムは、量子クエリ複雑性におけるブラックボックス問題、例えば要素の区別^{[ 9 ]}や衝突問題^{[ 10 ]} （ブラッサード・ホイヤー・タップアルゴリズムで解決）に対しても、証明可能な高速化をもたらすことができる。これらのタイプの問題では、オラクル関数fをデータベースとして扱い、この関数への量子クエリの使用回数をできるだけ少なくすることが目標となる。

グローバーのアルゴリズムへの入力として、関数があると仮定します。${\displaystyle f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}}$「非構造化データベース」のアナロジーでは、ドメインはデータベースのインデックスを表し、${\displaystyle f(x)=1}$データが${\displaystyle x}$検索条件を満たすポイント。さらに、1 つのインデックスのみが条件を満たすと仮定します。${\displaystyle f(x)=1}$、これをインデックスと呼びます${\displaystyle \omega }$私たちの目標は、${\displaystyle \omega }$。

アクセスできます${\displaystyle f}$単一演算子の形式のサブルーチン（オラクルと呼ばれることもある）を使用する${\displaystyle U_{\omega }}$それは以下のように機能します。

$${\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega {\text{, すなわち }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, すなわち }}f(x)=0.\end{cases}}}$$

これは${\displaystyle N}$次元状態空間$\displaystyle {\mathcal {H}}}$これはレジスタによって供給されます${\displaystyle n=\lceil \log _{2}N\rceil }$量子ビット。これはしばしば次のように書かれます。

$${\displaystyle U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle .}$$

グローバーのアルゴリズムの出力${\displaystyle \omega }$少なくとも確率で${\displaystyle 1/2}$使用${\displaystyle O({\sqrt {N}})}$の応用${\displaystyle U_{\omega }}$この確率は、グローバーのアルゴリズムを複数回実行することで任意に大きくすることができます。グローバーのアルゴリズムを${\displaystyle \omega }$発見されたが、予想される申請数はまだ${\displaystyle O({\sqrt {N}})}$平均して2回しか実行されないため。

グローバーのアルゴリズムの手順は以下のとおりです。

1. システムをすべての状態にわたる均一な重ね合わせ状態に初期化する${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$
2. 以下の「グローバー反復」を実行してください。${\displaystyle r(N)}$時間:
   1. 演算子を適用する${\displaystyle U_{\omega }}$
   2. グローバー拡散演算子を適用する${\displaystyle U_{s}=2\left|s\right\rangle \!\!\left\langle s\right|-I}$
3. 計算基底において、得られた量子状態を測定する。

正しく選択された値の場合${\displaystyle r}$出力は次のようになります${\displaystyle |\omega \rangle }$N ≫ 1の場合、確率は 1 に近づきます。分析によると、最終的な値は次のようになります。${\displaystyle r(N)}$満たす${\displaystyle r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }}$。

このアルゴリズムの手順を実装するには、量子ビット数に比例する数のゲートを使用できます。^{[ 3 ]}したがって、このアルゴリズムのゲート複雑度は次のようになります。${\displaystyle O(\log(N)r(N))}$、 または${\displaystyle O(\log(N))}$反復ごとに。

グローバーのアルゴリズムには幾何学的な解釈があり、これはグローバーのアルゴリズムの量子状態が各ステップ後に2次元部分空間に留まるという観察に基づいています。 によって張られる平面を考えてみましょう。${\displaystyle |s\rangle }$そして${\displaystyle |\omega \rangle }$; 同様に、によって張られる平面${\displaystyle |\omega \rangle }$そして垂直ケット${\displaystyle \textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle }$。

グローバーのアルゴリズムは、最初のケットから始まります。${\displaystyle |s\rangle }$部分空間に含まれる演算子${\displaystyle U_{\omega }}$は、に直交する超平面での反射である。${\displaystyle |\omega \rangle }$によって張られる平面内のベクトルについて${\displaystyle |s'\rangle }$そして${\displaystyle |\omega \rangle }$つまり、それは反射として作用する${\displaystyle |s'\rangle }$これは、次のように書くことで確認できます。${\displaystyle U_{\omega }}$世帯主の視点からの考察という形で：

$${\displaystyle U_{\omega }=I-2|\omega \rangle \langle \omega |.}$$

オペレーター${\displaystyle U_{s}=2|s\rangle \langle s|-I}$反射${\displaystyle |s\rangle }$両オペレーター${\displaystyle U_{s}}$そして${\displaystyle U_{\omega }}$によって張られる平面上の状態を取る${\displaystyle |s'\rangle }$そして${\displaystyle |\omega \rangle }$平面上の状態へ移行する。したがって、グローバーのアルゴリズムは、アルゴリズム全体を通してこの平面上に留まる。

オペレーターを確認するのは簡単です${\displaystyle U_{s}U_{\omega }}$各グローバー反復ステップで、状態ベクトルを角度だけ回転させます。${\displaystyle \theta =2\arcsin {\tfrac {1}{\sqrt {N}}}}$したがって、十分な反復回数を経れば、初期状態から回転させることができる。${\displaystyle |s\rangle }$目的の出力状態へ${\displaystyle |\omega \rangle }$初期ケットは、に直交する状態に近い。${\displaystyle |\omega \rangle }$:

$${\displaystyle \langle s'|s\rangle ={\sqrt {\frac {N-1}{N}}}.}$$

幾何学的に言えば、角度${\displaystyle \theta /2}$間${\displaystyle |s\rangle }$そして${\displaystyle |s'\rangle }$は

$${\displaystyle \sin {\frac {\theta }{2}}={\frac {1}{\sqrt {N}}}.}$$

状態ベクトルが近くを通過するときに停止する必要があります${\displaystyle |\omega \rangle }$;その後、後続の反復処理では状態ベクトルを回転させて${\displaystyle |\omega \rangle }$正解が得られる確率は低下します。正解を測定する正確な確率は

$${\displaystyle \sin ^{2}\left({\Big (}r+{\frac {1}{2}}{\Big )}\theta \right),}$$

ここで、rはグローバー反復の（整数）回数である。したがって、ほぼ最適な測定値が得られる最も早い時刻は${\displaystyle r\approx \pi {\sqrt {N}}/4}$。

代数解析を完了するには、繰り返し適用したときに何が起こるかを調べる必要があります。${\displaystyle U_{s}U_{\omega }}$これを行う自然な方法は、行列の固有値解析です。計算全体を通して、アルゴリズムの状態は、次の線形結合であることに注意してください。${\displaystyle s}$そして${\displaystyle \omega }$. アクションを書くことができます${\displaystyle U_{s}}$そして${\displaystyle U_{\omega }}$空間に広がる${\displaystyle \{|s\rangle ,|\omega \rangle \}}$として：

${\displaystyle {\begin{aligned}U_{s}:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\\U_{\omega }:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\end{aligned}}}$

つまり基本は${\displaystyle \{|\omega \rangle ,|s\rangle \}}$（直交でも全空間の基底でもない）アクション${\displaystyle U_{s}U_{\omega }}$適用する${\displaystyle U_{\omega }}$に続く${\displaystyle U_{s}}$行列によって与えられる

$${\displaystyle U_{s}U_{\omega }={\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}={\begin{bmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{bmatrix}}.}$$

この行列は、非常に便利なジョルダン形式を持っています。${\displaystyle t=\arcsin(1/{\sqrt {N}})}$それは

$${\displaystyle U_{s}U_{\omega }=M{\begin{bmatrix}e^{2it}&0\\0&e^{-2it}\end{bmatrix}}M^{-1}}$$

どこ${\displaystyle M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.}$

したがって、行列のr乗 ( r回反復に対応) は次のようになる。

$${\displaystyle (U_{s}U_{\omega })^{r}=M{\begin{bmatrix}e^{2rit}&0\\0&e^{-2rit}\end{bmatrix}}M^{-1}.}$$

この形式を使用すると、前のセクションで述べたr回の反復後にω を観測する確率を計算するために三角関数の恒等式を使用できます。

$${\displaystyle \left|{\begin{bmatrix}\langle \omega |\omega \rangle &\langle \omega |s\rangle \end{bmatrix}}(U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\right|^{2}=\sin ^{2}\left((2r+1)t\right).}$$

あるいは、2 rtと −2 rt の角度が可能な限り離れているときが、ほぼ最適な区別のタイミングであると合理的に想像できる。これは、${\displaystyle 2rt\approx \pi /2}$、 または${\displaystyle r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4}$するとシステムは次の状態になります

$${\displaystyle [|\omega \rangle \,|s\rangle ](U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\approx [|\omega \rangle \,|s\rangle ]M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}{\begin{bmatrix}0\\1\end{bmatrix}}=|\omega \rangle {\frac {1}{\cos(t)}}-|s\rangle {\frac {\sin(t)}{\cos(t)}}.}$$

簡単な計算により、観測値は誤差を伴う正しい答えωを与えることがわかる。${\displaystyle O\left({\frac {1}{N}}\right)}$。

グローバーのアルゴリズムは、定数以下の係数を除いて最適です。つまり、演算子U _ωのみを使用してデータベースにアクセスするアルゴリズムは、少なくともU _ωを適用する必要があります。${\displaystyle 1-o(1)}$グローバーのアルゴリズムの何倍もの分数である。^{[ 21 ]}グローバーのアルゴリズムをk個のマッチングエントリに拡張したπ ( N / k ) ^1/2/4も最適である。^{[ 18 ]}この結果は量子計算の限界を理解する上で重要である。

グローバーの探索問題がU _ωのlog ^c N回の適用で解けるとすれば、 NP の問題をグローバー型の探索問題に変換することで、 NPがBQPに含まれることになる。グローバーのアルゴリズムの最適性は、量子コンピュータがNP 完全問題を多項式時間で解くことができないことを示唆しており、したがって NP は BQP に含まれない。

非局所隠れ変数量子コンピュータの一種が、${\displaystyle N}$-アイテムデータベースは最大${\displaystyle O({\sqrt[{3}]{N}})}$ステップ。これは、${\displaystyle O({\sqrt {N}})}$グローバーのアルゴリズムによって実行されるステップ。^{[ 22 ]}

• 振幅増幅
• Brassard-Høyer-Tapp アルゴリズム(衝突問題を解決するため)
• ショアのアルゴリズム（因数分解用）
• 量子ウォーク探索

• Grover LK:データベース検索のための高速量子力学的アルゴリズム、第28回ACM理論計算機科学シンポジウム論文集（1996年5月）、 p.212
• Grover LK:シュレーディンガー方程式から量子探索アルゴリズムへ、American Journal of Physics、69(7): 769–777、2001年。アルゴリズムとその歴史に関する教育的レビュー。
• Grover LK:量子コンピューティング：素粒子の世界の奇妙な論理が、機械が今日よりも何百万倍も速く計算することを可能にする方法、The Sciences、1999年7月/8月号、24-30ページ 。
• Nielsen, MA および Chuang, IL 『量子計算と量子情報』ケンブリッジ大学出版局、2000 年。第 6 章。
• 量子電話帳とは？、ラブ・グローバー、ルーセント・テクノロジーズ

• Davy Wybiral。「量子回路シミュレータ」 。 2017年1月16日にオリジナルからアーカイブ済み。2017年1月13日に取得。
• Craig Gidney (2013-03-05). "Grover's Quantum Search Algorithm" . 2020-11-17のオリジナルからアーカイブ済み。2013-03-08 に取得。
• François Schwarzentruber (2013-05-18). "Groverのアルゴリズム" .
• Alexander Prokopenya. 「グローバーの探索アルゴリズムを実装する量子回路」。Wolfram Alpha。
• 「量子計算の理論」、数学百科事典、EMS Press、2001年 [1994年]
• Roberto Maestre (2018-05-11). "RとCで実装されたグローバーのアルゴリズム" . GitHub .
• Bernhard Ömer。「QCL - 量子コンピュータのためのプログラミング言語」 。 2022年4月30日取得。/qcl-0.6.4/lib/grover.qclに実装。