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

Quantum search algorithm

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

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

Charles H. Bennett、Ethan Bernstein、Gilles Brassard、およびUmesh Vaziraniは、問題に対する量子ソリューションは関数を回評価する必要があることを証明した。そのため、Groverのアルゴリズムは漸近的に最適である。^[2] NP完全問題に対する古典的なアルゴリズムは指数的に多くのステップを必要とし、Groverのアルゴリズムは非構造化検索に対して古典的なソリューションに対して最大で2乗の高速化を提供するだけであるため、GroverのアルゴリズムだけではNP完全問題に対して多項式時間ソリューションを提供できないことが示唆される（指数関数の平方根は依然として指数関数であり、多項式関数ではないため）。^[3] ${\displaystyle \Omega ({\sqrt {N}})}$

他の量子アルゴリズムは古典的アルゴリズムに比べて指数関数的な高速化をもたらす可能性がありますが、グローバーのアルゴリズムは2乗の高速化しか提供しません。しかし、2乗の高速化でさえ、が大きければ相当なものであり、グローバーのアルゴリズムは幅広いアルゴリズムの高速化に適用できます。^[3]グローバーのアルゴリズムは、128ビットの対称暗号鍵を約2の^64乗回の反復で、256ビットの鍵を約2の¹²⁸乗回の反復で総当たり攻撃できます。しかし、グローバーのアルゴリズムが既存の古典的アルゴリズムに比べて暗号化のリスクを大幅に高めるわけではないかもしれません。^[4] ${\displaystyle N}$

アプリケーションと制限

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

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

暗号化

グローバーのアルゴリズムは本質的に関数の反転という課題を解決する。大まかに言えば、量子コンピュータで評価できる関数があれば、グローバーのアルゴリズムを使えば が与えられたときにを計算することができる。その結果、グローバーのアルゴリズムは、衝突攻撃や原像攻撃など、対称鍵暗号に対する多くの種類のブルートフォース攻撃を広範囲に漸近的に高速化する。^{[11]しかし、例えば}ポラードのローアルゴリズムはグローバーのアルゴリズムよりも効率的にSHA-2の衝突を見つけることができるため、必ずしも最も効率的なアルゴリズムであるわけではない。^[12] ${\displaystyle y=f(x)}$ ${\displaystyle x}$ ${\displaystyle y}$

制限事項

Groverの原論文では、このアルゴリズムをデータベース検索アルゴリズムとして説明しており、この説明は今でも一般的です。このアナロジーにおけるデータベースとは、関数のすべての出力を、対応する入力でインデックス付けしたテーブルです。しかし、このデータベースは明示的に表現されていません。代わりに、オラクルが呼び出され、インデックスによって項目を評価します。データベース全体を項目ごとに読み取り、そのような表現に変換するには、Groverの探索よりもはるかに長い時間がかかる可能性があります。このような影響を考慮すると、Groverのアルゴリズムは方程式を解く、または制約を満たすものと見なすことができます。このような応用では、オラクルは制約をチェックする方法であり、探索アルゴリズムとは関係ありません。この分離により、通常、アルゴリズムの最適化が防止されます。一方、従来の探索アルゴリズムは、多くの場合、このような最適化に依存し、網羅的な探索を回避します。^[13]幸いなことに、多くの制約充足問題と最適化問題において、Groverのオラクルの高速実装が可能です。^[14]

グローバーのアルゴリズムによる高速化を実現する上での大きな障壁は、達成される二次的な高速化があまりにも控えめで、近い将来の量子コンピュータの大きなオーバーヘッドを克服できないことである。^[15]しかし、より優れたハードウェア性能を持つ後世代のフォールトトレラント量子コンピュータは、実用的なデータインスタンスに対してこれらの高速化を実現できる可能性がある。

問題の説明

グローバーのアルゴリズムの入力として、関数 があると仮定します。「非構造化データベース」のアナロジーでは、定義域 はデータベースへのインデックスを表し、 を指すデータが検索基準を満たす場合のみ、 となります。さらに、 を満たすインデックスは1つだけであると仮定し、このインデックスを と呼びます。目標は を特定することです。 ${\displaystyle f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}}$ ${\displaystyle f(x)=1}$ ${\displaystyle x}$ ${\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{, that is, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, that is, }}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 .}$$

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

代替オラクル定義

このセクションでは、上記のオラクルとオラクルを比較します。 ${\displaystyle U_{\omega }}$ ${\displaystyle U_{f}}$

${\displaystyle U_{\omega }}$は関数 の標準的な量子オラクルとは異なります。この標準的なオラクル（ここでは と表記）は、補助的な量子ビットシステムを使用します。この演算は、補助的なシステムからのf ( x )の値によって条件付けられた主システム上の反転（NOTゲート）を表します。 ${\displaystyle f}$ ${\displaystyle U_{f}}$

$${\displaystyle {\begin{cases}U_{f}|x\rangle |y\rangle =|x\rangle |\neg y\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{f}|x\rangle |y\rangle =|x\rangle |y\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0,\end{cases}}}$$

あるいは簡単に言えば、

$${\displaystyle U_{f}|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle .}$$

これらのオラクルは通常、非計算を使用して実現されます。

がオラクルとして与えられている場合は、 も実装できます。これは、補助量子ビットが状態 にあるとき であるためです。 ${\displaystyle U_{f}}$ ${\displaystyle U_{\omega }}$ ${\displaystyle U_{\omega }}$ ${\displaystyle U_{f}}$ ${\displaystyle |-\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}=H|1\rangle }$

$${\displaystyle {\begin{aligned}U_{f}{\big (}|x\rangle \otimes |-\rangle {\big )}&={\frac {1}{\sqrt {2}}}\left(U_{f}|x\rangle |0\rangle -U_{f}|x\rangle |1\rangle \right)\\&={\frac {1}{\sqrt {2}}}\left(|x\rangle |0\oplus f(x)\rangle -|x\rangle |1\oplus f(x)\rangle \right)\\&={\begin{cases}{\frac {1}{\sqrt {2}}}\left(-|x\rangle |0\rangle +|x\rangle |1\rangle \right)&{\text{if }}f(x)=1,\\{\frac {1}{\sqrt {2}}}\left(|x\rangle |0\rangle -|x\rangle |1\rangle \right)&{\text{if }}f(x)=0\end{cases}}\\&=(U_{\omega }|x\rangle )\otimes |-\rangle \end{aligned}}}$$

したがって、グローバーのアルゴリズムは、どのオラクルを与えても実行できます。^[3]が与えられた場合、状態で追加の量子ビットを維持し、の代わりにを適用する必要があります。 ${\displaystyle U_{f}}$ ${\displaystyle |-\rangle }$ ${\displaystyle U_{f}}$ ${\displaystyle U_{\omega }}$

アルゴリズム

グローバーアルゴリズムの量子回路表現

Grover のアルゴリズムの手順は次のとおりです。

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. 計算基底において結果として得られる量子状態を測定します。

の正しく選択された値の場合、出力は、N ≫ 1に対して確率で 1 に近づきます。分析により、 のこの最終的な値は を満たすことがわかります。 ${\displaystyle r}$ ${\displaystyle |\omega \rangle }$ ${\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))}$

幾何学的証明

グローバーアルゴリズムの最初の反復における幾何学的解釈を示す図。状態ベクトルは図に示すように目標ベクトルに向かって回転します。 ${\displaystyle |s\rangle }$ ${\displaystyle |\omega \rangle }$

グローバーのアルゴリズムには幾何学的な解釈があり、これはグローバーのアルゴリズムの量子状態が各ステップの後に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)}$

拡張機能とバリアント

複数の一致するエントリ

1つの一致するエントリの代わりにk個の一致するエントリがある場合、同じアルゴリズムが機能しますが、反復回数は ${\textstyle {\frac {\pi }{4}}{\left({\frac {N}{k}}\right)^{1/2}}}$ ${\textstyle {\frac {\pi }{4}}{N^{1/2}}.}$

kが不明な場合の対処法はいくつかある。^[16]定数倍まで最適なパフォーマンスを発揮する単純な解決策は、グローバーのアルゴリズムをkの値を徐々に小さくして繰り返し実行することである。例えば、 k = N、N /2、N /4、…のようにして、一致するエントリが見つかるまで反復tを実行する。 ${\displaystyle k=N/2^{t}}$

十分に高い確率で、マークされたエントリは定数cに対する反復によって発見される。したがって、反復回数は最大で ${\displaystyle t=\log _{2}(N/k)+c}$

$${\displaystyle {\frac {\pi }{4}}{\Big (}1+{\sqrt {2}}+{\sqrt {4}}+\cdots +{\sqrt {\frac {N}{k2^{c}}}}{\Big )}=O{\big (}{\sqrt {N/k}}{\big )}.}$$

kが不明な場合の別のアプローチは、量子カウントアルゴリズム事前を介してそれを導出することです。

（または、 で実行された場合の従来のグローバーアルゴリズムの状態を示すマーク）の場合、アルゴリズムは増幅を提供しません。 の場合、k を増やすと、解を得るのに必要な反復回数が増加し始めます。^[17]一方、 の場合、単一のランダムな入力に対してチェックオラクルを従来通りに実行すると、正しい解が得られる可能性が高くなります。 ${\displaystyle k=N/2}$ ${\displaystyle N=2}$ ${\displaystyle k>N/2}$ ${\displaystyle k\geq N/2}$

このアルゴリズムのバージョンは衝突問題を解決するために使用されます。^{[18] [19]}

量子部分探索

グローバーのアルゴリズムの改良版である量子部分探索は、グローバーとラダクリシュナンによって2004年に発表されました^[20]。部分探索では、対象アイテムの正確なアドレスを見つけることではなく、アドレスの最初の数桁のみに着目します。これは、探索空間をブロックに「チャンク化」し、「対象アイテムはどのブロックにあるか」を尋ねるようなものです。多くの応用において、対象アドレスに必要な情報が含まれていれば、このような探索で十分な情報が得られます。例えば、LKグローバーの例を挙げると、クラス順位順に並べられた生徒のリストがある場合、生徒が下位25%、25～50%、50～75%、または75～100%のパーセンタイルのいずれに位置するかのみに着目すればよいでしょう。

部分探索を説明するために、サイズ のブロックに分割されたデータベースを考えます。部分探索問題はより容易です。古典的なアプローチを考えてみましょう。ランダムに1つのブロックを選択し、残りのブロック（集合論用語では補ブロック）に対して通常の探索を実行します。目的のブロックが見つからない場合、探索しなかったブロックにあることがわかります。平均反復回数は から に減少します。 ${\displaystyle K}$ ${\displaystyle b=N/K}$ ${\displaystyle N/2}$ ${\displaystyle (N-b)/2}$

グローバーのアルゴリズムは反復を必要とします。部分探索は、ブロック数に依存する数値係数によって高速化されます。部分探索では、グローバル反復とローカル反復が使用されます。グローバルグローバー演算子は で指定され、ローカルグローバー演算子は で指定されます。 ${\textstyle {\frac {\pi }{4}}{\sqrt {N}}}$ ${\displaystyle K}$ ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$

グローバルグローバー演算子はブロックに作用します。基本的には、次のように表されます。

1. データベース全体に対して標準の Grover 反復処理を実行します。 ${\displaystyle j_{1}}$
2. ローカルグローバー反復を実行します。ローカルグローバー反復は、各ブロックにおけるグローバー反復の直和です。 ${\displaystyle j_{2}}$
3. 標準的な Grover 反復を 1 回実行します。

と の最適値は、グローバーとラダクリシュナンの論文で議論されています。また、異なるレベルの「解像度」で部分探索を連続的に適用するとどうなるか疑問に思う人もいるかもしれません。このアイデアはウラジミール・コレーピンと徐によって詳細に研究され、彼らはこれを二分量子探索と呼びました。彼らは、実際には単一の部分探索を実行する場合と比べて速度が遅くないことを証明しました。 ${\displaystyle j_{1}}$ ${\displaystyle j_{2}}$

最適性

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

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

非局所的隠れ変数量子コンピュータの一種は、最大ステップ数で - アイテムデータベースの検索を実行できることが示されています。これは、グローバーのアルゴリズムのステップ数よりも高速です。 ^[22] ${\displaystyle N}$ ${\displaystyle O({\sqrt[{3}]{N}})}$ ${\displaystyle O({\sqrt {N}})}$

参照

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

注記

1. Grover, Lov K. (1996-07-01). 「データベース検索のための高速量子力学アルゴリズム」.第28回ACMコンピューティング理論シンポジウム議事録 - STOC '96 . フィラデルフィア、ペンシルベニア州、米国: Association for Computing Machinery. pp.  212– 219. arXiv : quant-ph/9605043 . Bibcode :1996quant.ph..5043G. doi :10.1145/237814.237866. ISBN 978-0-89791-785-8. S2CID  207198067。
2. Bennett, C.H.; Bernstein, E.; Brassard, G.; Vazirani, U. (1997). 「量子計算の強みと弱み」. SIAM Journal on Computing . 26 (5): 1510– 1523. arXiv : quant-ph/9701001 . doi :10.1137/s0097539796300933. S2CID  13403194.
3. ニールセン, マイケル・A.; チュアン, アイザック・L. (2010).量子計算と量子情報. ケンブリッジ: ケンブリッジ大学出版局. pp.  276– 305. ISBN 978-1-107-00217-3. OCLC  665137861。
4. Bernstein, Daniel J. (2010). "Grover vs. McEliece" (PDF) . Sendrier, Nicolas (編).ポスト量子暗号, 第3回国際ワークショップ, PQCrypto 2010, ダルムシュタット, ドイツ, 2010年5月25日～28日. Proceedings . Lecture Notes in Computer Science. Vol. 6061. Springer. pp.  73– 80. doi :10.1007/978-3-642-12929-2_6. ISBN 978-3-642-12928-5。
5. Grover, Lov K. (1998). 「高速量子力学アルゴリズムのためのフレームワーク」. Vitter, Jeffrey Scott (編). Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23–26, 1998 . Association for Computing Machinery. pp.  53– 62. arXiv : quant-ph/9711043 . doi :10.1145/276698.276712. ISBN 0-89791-962-9。
6. Ambainis, A. (2004-06-01). 「量子探索アルゴリズム」. ACM SIGACT News . 35 (2): 22– 35. arXiv : quant-ph/0504012 . doi :10.1145/992287.992296. ISSN  0163-5700. S2CID  11326499.
7. ジョーダン、スティーブン. 「Quantum Algorithm Zoo」. quantumalgorithmzoo.org . 2021年4月21日閲覧。
8. Cerf, Nicolas J.; Grover, Lov K.; Williams, Colin P. (2000-05-01). 「ネストされた量子探索とNP困難問題」.工学、コミュニケーション、コンピューティングにおける応用代数. 10 (4): 311– 338. doi :10.1007/s002000050134. ISSN  1432-0622. S2CID  311132.
9. Ambainis, Andris (2007-01-01). 「要素の識別性のための量子ウォークアルゴリズム」. SIAM Journal on Computing . 37 (1): 210– 239. arXiv : quant-ph/0311001 . doi :10.1137/S0097539705447311. ISSN  0097-5397. S2CID  6581885.
10. Brassard, Gilles; Høyer, Peter; Tapp, Alain (1998). 「ハッシュ関数とクローフリー関数の量子暗号解析」. Lucchesi, Claudio L.; Moura, Arnaldo V. (編). LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings . Lecture Notes in Computer Science. Vol. 1380. Springer. pp.  163– 169. arXiv : quant-ph/9705002 . doi :10.1007/BFb0054319. ISBN 978-3-540-64275-6。
11. ポスト量子暗号。ダニエル・J・バーンスタイン、ヨハネス・ブッフマン、エリック、数学者ダーメン。ベルリン：シュプリンガー。 2009.ISBN​ 978-3-540-88702-7. OCLC  318545517。{{cite book}}: CS1 maint: others (link)
12. Bernstein, Daniel J. (2021-04-21). 「ハッシュ衝突のコスト分析：量子コンピューターはSHARCSを時代遅れにするのか？」(PDF) .暗号システム攻撃用特殊用途ハードウェア会議論文集 (SHARCS '09) . 09 : 105–117 .
13. Viamontes GF; Markov IL; Hayes JP (2005)、「量子探索は実用的か？」(PDF) , Computing in Science and Engineering , 7 (3): 62– 70, arXiv : quant-ph/0405001 , Bibcode :2005CSE.....7c..62V, doi :10.1109/mcse.2005.53, S2CID  8929938
14. Sinitsyn NA; Yan B. (2023). 「分割問題に対するトポロジカルに保護されたグローバーのオラクル」. Physical Review A. 108 ( 2) 022412. arXiv : 2304.10488 . Bibcode :2023PhRvA.108b2412S. doi :10.1103/PhysRevA.108.022412. S2CID  258236417.
15. Babbush, Ryan; McClean, Jarrod R.; Newman, Michael; Gidney, Craig; Boixo, Sergio; Neven, Hartmut (2021-03-29). 「誤り訂正量子優位性のための二次速度向上の先に焦点を当てる」. PRX Quantum . 2 (1) 010103. arXiv : 2011.04149 . doi : 10.1103/PRXQuantum.2.010103 .
16. アーロンソン、スコット（2021年4月19日）「量子情報科学入門講義ノート」（PDF） .
17. ニールセン・チュアン
18. ボワイエ、ミシェル;ジル・ブラッサール。ピーター・ホイヤー。 Tapp、Alain (1998)、「Tight Bounds on Quantum Searching」、Fortschritte der Physik、46 ( 4–5 ): 493– 506、arXiv : quant-ph/9605034、Bibcode :1998ForPh..46..493B、doi :10.1002/3527603093.ch10、ISBN 978-3-527-60309-1
19. Ambainis, Andris (2004)、「量子探索アルゴリズム」、SIGACT News、35 (2): 22– 35、arXiv : quant-ph/0504012、Bibcode :2005quant.ph..4012A、doi :10.1145/992287.992296、S2CID  11326499
20. Grover, LK; Radhakrishnan, J. (2005-02-07). 「データベースの部分量子探索はもっと簡単になるか？」arXiv : quant-ph/0407122v4 .
21. Zalka, Christof (1999-10-01). 「Groverの量子探索アルゴリズムは最適である」. Physical Review A. 60 ( 4): 2746– 2751. arXiv : quant-ph/9711070 . Bibcode :1999PhRvA..60.2746Z. doi :10.1103/PhysRevA.60.2746. S2CID  1542077.
22. アーロンソン、スコット「量子コンピューティングと隠れた変数」（PDF）。

参考文献

• 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 月、pp. 24–30。
• Nielsen, MAおよびChuang, IL 「量子計算と量子情報」ケンブリッジ大学出版局、2000年。第6章。
• 量子電話帳とは何か？、ラブ・グローバー、ルーセント・テクノロジーズ

外部リンク

• Davy Wybiral. 「量子回路シミュレータ」. 2017年1月16日時点のオリジナルよりアーカイブ。2017年1月13日閲覧。
• Craig Gidney (2013年3月5日). 「Groverの量子探索アルゴリズム」. 2020年11月17日時点のオリジナルよりアーカイブ。2013年3月8日閲覧。
• François Schwarzentruber (2013-05-18). 「グローバーのアルゴリズム」
• Alexander Prokopenya. 「グローバーの探索アルゴリズムを実装した量子回路」Wolfram Alpha .
• 「量子計算理論」、数学百科事典、EMSプレス、2001 [1994]
• Roberto Maestre (2018-05-11). 「RとCで実装されたGroverのアルゴリズム」. GitHub .
• Bernhard Ömer. 「QCL - 量子コンピュータ向けプログラミング言語」. 2022年4月30日閲覧. /qcl-0.6.4/lib/grover.qcl に実装

Retrieved from "https://en.wikipedia.org/w/index.php?title=Grover%27s_algorithm&oldid=1324044824"