テクノロジー

グローバーのアルゴリズムとは?

定義:グローバーのアルゴリズムは、非常に高速な量子探索アルゴリズムです。このアルゴリズムは、他の従来のアルゴリズムとは異なり、非構造化検索の二次の加速をもたらします。ソートされていないデータベースを検索するために使用されます。関数のO√N評価のみを使用して、特定の出力値を生成するブラックボックス関数への一意の入力を高確率で見つけるもので、ここでNは関数の領域の大きさです。

概要

グローバーのアルゴリズムについて

量子コンピュータが古典コンピュータと比較して優れている点のひとつに、データベースの検索速度が優れていることが挙げられます。グローバーのアルゴリズムは、その代表的な例です。

インド系アメリカ人のコンピュータ科学者であるラヴ・グローバーは、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アルゴリズムが、当社のサイバーセキュリティソリューションにすでに実装されています。

ソリューション

ソリューション

ブログ投稿

ブログ投稿

関連商品

関連商品

お問い合わせ

お気軽にお問い合わせください。

How can we help you?

Talk to one of our specialists and find out how Utimaco can support you today.
You have selected two different types of downloads, so you need to submit different forms which you can select via the two tabs.

Your download request(s):

    By submitting below form you will receive links for your selected downloads.

    Your download request(s):

      For this type of documents, your e-mail address needs to be verified. You will receive the links for your selected downloads via e-mail after submitting below form.

      Utimacoのダウンロードについて

      ダウンロードセクションをご覧ください。

      パンフレット、データシート、ホワイトペーパーなどのリソースからお選びいただけます。ほぼすべての資料を直接(ダウンロードボタンをクリックして)閲覧・保存することができます。

      一部の資料については、電子メールアドレスの確認が必要です。ボタンにはEメールのアイコンがあります。

      Download via e-mail

       

      ボタンをクリックすると、オンラインフォームが開きますので、必要事項をご記入の上、送信してください。このタイプのダウンロードをいくつか収集し、1つのフォームをすべてのダウンロードに対して送信するだけで、リンクを電子メールで受け取ることができます。現在のコレクションは空です。