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

グローバーのアルゴリズムとは、"N"個の要素をもつ未整序データベースの中から指定された値を検索する探索問題を解くための量子コンピュータのアルゴリズムであり、"O(N1/2)"のオーダーの計算量と、"O("log"N)"のオーダー（ランダウの記号も参照）の記憶領域を消費する。1996年にによって開発された。
概要.
典型的には、未整序データベースからの探索は、"O(N)"の計算時間を要する線型探索を用いなければならない。グローバーのアルゴリズムは、"O(N1/2)"の計算時間しか消費せず、未整序データベース探索を行う量子アルゴリズムの中で最も速い。
このアルゴリズムは他の量子アルゴリズムがしばしば、古典アルゴリズムと比較して指数的な速度向上をもたらすのとは異なり、二次の速度向上しかもたらさない。しかし、"N"が大きければ、二次の向上でもかなりの向上となる。たとえば、グローバーのアルゴリズムを共通鍵暗号の総当り攻撃に利用すると、128ビット鍵であれば264の繰り返しで、256ビット鍵であれば2128の繰り返しで求めることができる。このため、将来の量子総当り攻撃に対して安全性を持たせるために、鍵長を2倍にすることが提案されている。
他の量子アルゴリズムと同じように、グローバーのアルゴリズムは正しい確率の高い解を与える、確率的アルゴリズムである。この解が正しくない確率は、このアルゴリズムを繰り返すことによって減少させることができる（確率的アルゴリズムでない、正しい確率が1の解を与える、決定的アルゴリズムについてはドイッチュ・ジョサのアルゴリズムを参照）。
応用.
グローバーのアルゴリズムの目的は普通「データベース探索」とされるが、「逆関数の導出」と言うとより正確かもしれない。おおざっぱにいうと、"y=f(x)"という量子コンピュータで処理できる関数があったとして、このアルゴリズムを使うとある"y"を与える"x"の値を計算することができる。データベース探索は、データベースをインデックス"x"に対してデータ"y"を与える関数と考えれば、逆関数を求めることと同値である。
グローバーのアルゴリズムは、平均と中央値を推定すること、また衝突問題（w:Collision problem）を解くのにも使える。また、可能性のある解を総当たりで探すことによってNP完全問題を解くことにも使える。これは、膨大な可能性を試すのに、重ね合わせを用いることで限られた計算量しか消費しないので、古典アルゴリズムに比べてかなりのスピードアップを見込めるが、指数時間かかってしまうことは変らない。あらかじめ解が複数あることとその個数がわかっている場合、このアルゴリズムはさらに高速化することができる。
準備.
N個のデータを持つデータベースを考える。データベースの中から、何らかの検索条件を満たすデータを探し出す問題を考えよう。
グローバーのアルゴリズムは、formula_1 次元の状態空間 formula_2 を必要とする。これはformula_3 量子ビットあれば満され、基底状態は
と書ける。これらの固有値 formula_5 は全て異なるとする。
formula_6 を、データベースのインデクス formula_7 を入力すると、検索条件を満たしているか否かを判定する関数とする。例えば、値 formula_8に対してformula_9 となる formula_10 を探したい場合には、
である。以下では formula_12 を、formula_13 を満たす値とし、次のようにふるまうユニタリ演算子 formula_14 を自由にサブルーチンとして使えるとする。（このサブルーチンは、オラクルとも呼ばれる。）
アルゴリズムの目的は、インデクス formula_16 を特定することである。
なお、（下に示す量子回路のように）補助量子ビットシステムを使う場合には、演算子 formula_14 の定義は異なるものになる。この場合の演算子は、メインシステムの formula_18 の値（０か１）に応じて反転させる制御NOTによって
あるいは、
で表現される。
アルゴリズムの流れ.
formula_21 を、全ての状態の一様な重ね合わせ
とし、演算子 formula_23 を
とする。この演算子は、グローバーの拡散演算子と呼ばれている。
グローバーのアルゴリズムの流れは以下の通りである。
1回目の繰り返し.
演算子 formula_23 は
で定義されており、さらに、演算子 formula_14 は次のように書くことができることに注意する。
これを確認するには、formula_36 が基底状態に対してどのように作用するかをチェックしてみればよい。
さらに、formula_16 は基底状態で、formula_39 は全ての状態の一様な重ね合わせであるから、
が成り立つ。したがって、1回目の繰り返しでは次にように計算される。
分かりやすい例として、formula_1 が4で、条件を満たす（つまり formula_13 を満たす）formula_12 が一つしかない場合を考えてみると、formula_45 となり、Grover iterator を一回作用させただけで目的の状態を得ることができることが分かる。
一般の場合では、formula_29 と formula_23 を作用させることで、目的の状態の二乗振幅は formula_48 から formula_49 に増加する。
妥当性の幾何学的な証明.
初期状態 formula_39 に作用する最初の繰り返しを考えよう。formula_16 は基底ベクトルであるから、formula_21 と formula_55 の重なりは次のようになる。
幾何学的に言えば、formula_39 と formula_55 のなす角度 formula_59 は次の関係を満す。
演算子"Uω"は、|"s">と|"ω">で張られる空間を、|"ω">と垂直な超平面を対称面として反転させる。つまり、空間上のベクトルを、formula_55 に対して対称なベクトルへ移す。演算子"Us"は、|"s">を対称面とする反転である。よって、|"s">と|"ω">によって張られる平面上にあるベクトルは、"Us"と"Uω" で演算されても、その平面上に留まる。また、Grover iteration"UsUω"の各繰り返しで、状態ベクトルは |"ω"> に向かって角度 formula_62 の回転をすることが容易に分かる。
状態ベクトルが|"ω">に近付いたなら、繰返しを止めなければならない。繰返しを重ねすぎると、状態ベクトルは|"ω">から離れていってしまい、正しい解を与える確率を下げてしまう。formula_63 回繰り返した場合に正しい答えが観測される確率は、
である。したがって、ほぼ最適な測定が得られる繰り返し回数は formula_65 である。
妥当性の代数的な証明.
代数的な解析をするには、formula_66 を繰り返し適用したときに何が起こるかを見る必要がある。これは、行列の固有値解析によって見ることができる。アルゴリズムの計算の間、状態は常に formula_67 と formula_12 の線形結合で表されるいることに注意する。そこで、formula_69 によって張られる空間において、formula_23 と formula_29 の動作は次のように表すことができる。
よって、formula_74 を基底とすると（ただし，これらは直交していないし、全体の空間の基底にはなっていない）、formula_29 を作用させてから formula_23 を作用させるという動作 formula_77 は、次の行列で表せる。
この行列は、非常に便利なジョルダン標準形をしている。formula_79 と定義すれば、
と書ける。
これにより、この行列の "r" 乗（"r" 回の繰り返しに対応する）は、
となる。この形式を使えば、三角関数の公式を使って、"r" 回の繰り返しの後に目的の formula_12 が観測される確率を
と計算することができる。（幾何学的な解析で得た確率と同じ。）
あるいは、最適な繰り返し回数は、角度 formula_85 と formula_86 が最も離れているときであり、これは formula_87 に対応する、と考えてもよい。つまり、formula_88 が得られる。このとき、システムは
の状態で終了する。
少し計算すれば、観測によって（エラー確率 "O"(1/"N") を除き）正しい答え formula_12 が得られることがわかる。
発展形.
もし、探索条件にあうデータが1個だけでなく、"k"個存在するならば、同じアルゴリズムを適用できるが、繰返し回数は"πN1/2/4"の代わりに"π(N/k)1/2/4"としなければならない。
"k"が未知の場合を取り扱う方法は幾つかある。例として、繰返し回数を以下のようにしてグローバーのアルゴリズムを何回か走らせる方法がある。
"k"がどのような値でも、上のような繰返し回数で行えば正しい解を高い確率で得られる。繰返しの総回数は多くとも次のようであり、O("N1/2")のオーダーにとどまる。
このアルゴリズムは改良の余地がある。"k"が未知であるとして、formula_91のオーダーで解を見付けることができる。このことから、このアルゴリズムは衝突問題を解く目的で使用できる。
最適性.
グローバーのアルゴリズムは最適であることが知られている。つまり、データベースに"Uω"のみを用いてアクセスするようなどんなアルゴリズムも、グローバーのアルゴリズムと同じかそれ以上の回数だけ"Uω"を作用させなければならない。この結果は量子計算の限界を理解する上で重要である。
もし、グローバーの探索問題がlog"c""N"回"Uω"適用することで解くことができるとすれば、NP問題をグローバーの探索問題に帰着させることで、NPがBQPに含まれることが示される。グローバーのアルゴリズムが最適であることは、NPはBQPに含まれないことを示唆している（ただし証明しているわけではない）。
"k"個の条件に該当するデータがある場合、"π(N/k)1/2/4"も最適である。
適用可能性と制約.
このアルゴリズムにおいては、データベースは明示的に表されておらず、代わりに、インデクスによってデータで評価するためにオラクルを呼び出す。データベース全体をデータごとに読み込み、それをインデクスを使って評価できる形式に変換することは、グローバーの検索よりもはるかに時間がかかる場合がある。これを考えると、グローバーのアルゴリズムは、方程式や制約充足問題を解くための方法であると見ることができる。このようなアプリケーションでは、オラクルは制約を満たすかどうかをチェックする方法であり、検索アルゴリズムとは無関係に動作する。一方、従来の検索アルゴリズムでは、検索アルゴリズムを制約のチェック方法と合わせて考慮することで総当たりを回避して最適化を行うことが良くある。グローバーのアルゴリズムではこれらが分離しているため、アルゴリズムの最適化が妨げられる。グローバーのアルゴリズムの使用に関するこれらおよびその他の考慮事項は、Viamontes、Markov、およびHayesによる論文で説明されている。