グローバーのアルゴリズムについて
量子コンピュータが古典コンピュータと比較して優れている点のひとつに、データベースの検索速度が優れていることが挙げられます。グローバーのアルゴリズムは、その代表的な例です。
インド系アメリカ人のコンピュータ科学者であるラヴ・グローバーは、1996年に論文を発表し、量子コンピュータの分野で名声を得ました。研究では、非構造化検索問題の最適化に取り組みました。
グローバーは、非構造化データベースから勝者Wを見つけるのにかかる時間を大幅に短縮するために、Amplitude Amplification（振幅増幅）と呼ばれる量子のトリックを実装することを提案しています。グローバーは論文を書くにあたって、いくつかのインスピレーションを得たそうです。グローバーによると、量子システムはポテンシャルの低い点に向かって「移動」すると説明しています。システムは、状態がより多くの確率振幅を蓄積するように、ポテンシャルが最も低い点を探します。
2つ目に、彼はシュレーディンガー方程式を使用しています（動的システムの将来の挙動を予測する方程式。この方程式は波動関数に基づいており、事象や結果を解析的かつ正確に予測するものです）。これに加えて、離散化された進化行列のユニタリバージョンを発見しました。初期量子状態または試行量子状態の位相選択とその後の拡散は、グローバーのアルゴリズムに不可欠な2つの要素です。グローバーはマルコフ的な性質を持つがユニタリーではない状態をマークしたメトリクスを使用しています（マルコフ行列は確率行列とも呼ばれ、マルコフ連鎖のステップを表すのに使われいます。マルコフ行列の各入力は、結果の確率を表します）。
グローバーによれば、検索操作は、項目xで動作する関数f (x)を用いて表現することができ、それが検索を成功させるものであれば、f(x)=1となります。項目xが見つからない場合は、f(x)=0となります。量子コンピューティングは、古典的な検索アルゴリズムと比較して非常に効率的であるO√Nの非構造化検索問題を解決するために使用できます。
グローバーのアルゴリズムの簡単な例：
N個のキーのうち、ランダムにボックスに置かれた特定のキーを見つけたいとします。
特定のキーを見つけるには、ボックスを平均N/2回、最悪の場合はN回検索する必要があります。量子技術を使用すると、このプロセスを√N倍にまで高速化できます。
100個のキーのボックスでは、これは50〜100個のキーの代わりに10個のキーを試すことを意味します。
グローバーのアルゴリズムのもう1つの利点は、O (√ N log N)ゲートのみで動作することです。グローバーは、Oracleの概念を使用し、nビットのバイナリ入力を受けてmビットを生成するブラックボックス的な操作です。同様に、その拡散演算子は、平均値について反転を与えるので、無限スケールの小さなステップが測定可能になります。
グローバーのアルゴリズムのアプリケーション
グローバーのアルゴリズムは、数の集合の平均値と中央値の消去に関する問題を解決することができます。また、衝突の問題を解決することもできます。
- NP完全問題を、可能な解を見つけるための網羅的な検索を使って解くことができます
- このアルゴリズムは、他のさまざまなアルゴリズムに対して、二次関数的な実行時間で非構造化検索問題を高速化するのに役立ちます。
- 振幅増幅に加え、位相干渉や重ね合わせを利用して、検索対象の素子を探し出すことができます。
Utimacoは、量子コンピュータや暗号化キーを見つけるためのグローバーのアルゴリズムの実行に基づく攻撃から企業のシステムを守ることを可能にする量子耐性ソリューションを提供しています。ポスト量子暗号における当社の多大な時間と人材投資により、NISTとBSIに認証されたPQCアルゴリズムが、当社のサイバーセキュリティソリューションにすでに実装されています。
