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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/01/13 10:16 UTC 版)

グローバーのアルゴリズムとは、N個の要素をもつ未整序データベースの中から指定された値を検索する探索問題を解くための量子コンピュータのアルゴリズムであり、O(N^1/2)のオーダーの計算量と、O(logN)のオーダー（ランダウの記号も参照）の記憶領域を消費する。1996年にロブ・グローバーによって開発された。

概要

典型的には、未整序データベースからの探索は、O(N)の計算時間を要する線型探索を用いなければならない。グローバーのアルゴリズムは、O(N^1/2)の計算時間しか消費せず、未整序データベース探索を行う量子アルゴリズムの中で最も速い。

このアルゴリズムは他の量子アルゴリズムがしばしば、古典アルゴリズムと比較して指数的な速度向上をもたらすのとは異なり、二次の速度向上しかもたらさない。しかし、Nが大きければ、二次の向上でもかなりの向上となる。たとえば、グローバーのアルゴリズムを共通鍵暗号の総当り攻撃に利用すると、128ビット鍵であれば2⁶⁴の繰り返しで、256ビット鍵であれば2¹²⁸の繰り返しで求めることができる。このため、将来の量子総当り攻撃に対して安全性を持たせるために、鍵長を2倍にすることが提案されている。

他の量子アルゴリズムと同じように、グローバーのアルゴリズムは正しい解を高い確率で与える確率的アルゴリズムである。この解が正しくない確率は、このアルゴリズムを繰り返すことによって減少させることができる（確率的アルゴリズムでない、正しい確率が1の解を与える、決定的アルゴリズムについてはドイッチュ・ジョサのアルゴリズムを参照）。

応用

グローバーのアルゴリズムの目的は普通「データベース探索」とされるが、「逆関数の導出」と言うとより正確かもしれない。おおざっぱにいうと、y=f(x)という量子コンピュータで処理できる関数があったとして、このアルゴリズムを使うとあるyを与えるxの値を計算することができる。データベース探索は、データベースをインデックスxに対してデータyを与える関数と考えれば、逆関数を求めることと同値である。

グローバーのアルゴリズムは、平均と中央値を推定すること、また衝突問題（w:Collision problem）を解くのにも使える。また、可能性のある解を総当たりで探すことによってNP完全問題を解くことにも使える。これは、膨大な可能性を試すのに、重ね合わせを用いることで限られた計算量しか消費しないので、古典アルゴリズムに比べてかなりのスピードアップを見込めるが、指数時間かかってしまうことは変らない。あらかじめ解が複数あることとその個数がわかっている場合、このアルゴリズムはさらに高速化することができる。

準備

N個のデータを持つデータベースを考える。データベースの中から、何らかの検索条件を満たすデータを探し出す問題を考えよう。 グローバーのアルゴリズムは、 $N$

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

$|s\rangle$

グローバーのアルゴリズムの最初の繰り返しの幾何学的な解釈。状態ベクトル $|s\rangle$ カテゴリ

ウィキペディア小見出し辞書

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/19 00:40 UTC 版)

「量子コンピュータ」の記事における「グローバーのアルゴリズム」の解説

詳細は「グローバーのアルゴリズム」を参照 n 個のデータの中から、ある特定のデータを √n ステップで取得することができるアルゴリズム。正確には、1 から N のある一つの値で、オラクル関数 f(z) が 1 になり、それ以外は f(z) = 0 となる、オラクル関数 f において、f(z) = 1 となる z を求める問題。オラクル関数とは計算量が 0 の関数である。古典コンピュータではおよそ n/2 ステップが必要である。1996年にロブ・グローバー（英語版）が発表した。きわめて広範な種類の確率的アルゴリズムや量子アルゴリズムと組み合わせて、計算時間をその平方根まで落とすことができる。ショアのアルゴリズムほどその効果は劇的ではないが、広い応用をもつことが特徴である。検索条件や検索対象について改良されている。 このアルゴリズムはデータ数に見合うだけ十分な量子ビット数があることを前提としているが、古典コンピュータにおいてデータに見合うだけの十分な並列度がある場合、f(z) = 1 を探すのは O(1) であり、関数の最小値を探す問題は、O(log log n) である。