Home What's QC Tutorial Shor Grover Samples Specifications Download Order Links Contact

Grover のデータベース検索アルゴリズムのサンプルです。 ここで紹介する Grover のアルゴリズムは、きわめて基本的なもので、Grover のアルゴリズムの核心である、特定の状態をもつ確率振幅成分を大きくする操作の部分のみを取り扱います。 Grover のアルゴリズムで対象とするデータベースの構造は、ある特定の状態と、それに対応した状態が連続したものです。例えば、次のように、番号と名前からなるデータベース構造を想定しています。 このデータベース構造において、特定の番号から名前を引き出すような検索問題を取り扱います。 量子アルゴリズムにおいては、これを一般化して、次のように考えます。 2 つの数の組み で表現されるデータベースの構造が与えられたときに、求めたい状態 を高い確率で観測する。 例に対応させると、 が番号に、また が番号に対応した名前を与えると考えます。 Grover のアルゴリズムでは、データベース構造に 2 つのユニタリ変換を連続して回作用させることにより、求めたい状態が観測される確率を 以上にすることができます。 作用させるユニタリ作用素は で与えられる 2 つの行列です。ここで は、データベースの初期状態、また , は、求めたい状態です。具体的には、求めたい状態 を 0 とするなら で与えられます。 は求めたい状態についての選択的な回転をおこなう変換、また、 は平均についての反転の変換をおこなっていると考えることができます。 と を簡単に作成できるように、Mathematica のノートブックファイル "Grover.nb" が付属しています。 状態数、選びたい状態、2 つの行列とノートブック中の変数との対応関係は、次の通 りです。 必要な変数を評価した上で、シミュレータに取り込み確認して下さい。 Shorの因数分解 その他