Diffusion and Performance／拡散とパフォーマンス

Groverアルゴリズムの2つ目の要素は拡散作用で、「平均の反転」を実行するものとなっています。Groverのアルゴリズムは、幅広い問題において、多項式時間の速度上昇をもたらしてくれます。

平均を反転する

先ほどのステップで議論したような操作を行った後、状態の振幅の幅の平均をとり、反転させます。下記の図の左側に2つの独立した例が示されています。すべての量子状態の重ね合わせの要素の平均は、破線で表されます。 拡散においては、青（上向き）の線は、平均について回転されたとき、中心に向かって回転するため、振幅は縮小します。反対に、橙（下向き）色の線は、青線と同じ振幅を持っていますが、平均による回転にともなって上向きになり、振幅は増大します。

拡散操作は状態の位相によって非常に効果的なものになります。下の図にみられるように、最初の手順は マーキング です。問題解決の糸口は、他の状態とは異なる、一つの状態（図の中では橙色）です。マークされない（図の青線のような状態）ものはすべて上を向きます。図の3列目にみられるように、この結果からもわかるように、平均値は青線の先の近くにみることができます。

4つの可能性をもつチェスの例のように、私たちが マーキングと拡散の繰り返し を行ったときに、何が起こっているかについてみていきましょう。劣勢状態（下の図では青線）での振幅は0となり、優勢状態（下の図の黄線）での振幅は1となります。

この手順ののち、私たちは2つの量子ビットを測定し、どちらのシーケンスがマークされているのかを知ります。この場合、測定結果は(vert10rangle)となり、3回目の動作シーケンスと一致します。特定の関数(f(x))は問題の解決策を特定することを思い出してください。しかしそれは、値や、(x)の入力が反転したことを演繹的に知ることはできないのです。それらはすべて重ね合わせ状態の時に起きます。

これらのすべては、答えの部分は波が強め合い、その他の波は衰えることによって発生するのです。

パフォーマンス

チェスの例のように、マーキングと拡散 の繰り返しのみが、回答の波を強くするうえで必要なのです。より大きな問題に対しては、平均値がマークされていない状態に非常に近くなります。それ故に、最初の繰り返しはほとんど意味がなく、だんだんと測定店での橙色のベクトルが成長するスピードは、蓄積されていくことによって早くなっていきます。（厳密な繰り返しの数は、マークされている状態と、マークされていない状態の数によって決まりますが、Groverのアルゴリズムによれば同様に比率として考えることができます。）

古典コンピュータを用いる一般的な場合は、(N)個の可能性と一つの答えを持っているもので、最悪の場合(N)通りすべての場合を確かめなくてはならず、平均的には(N/2)個確かめることとなります。量子コンピュータによってGroverのアルゴリズムを、(log{N})個の量子ビットで走らせることによって、(O(sqrt{N}))程の マーキングと拡散 の繰り返しによって解くことが可能となるのです。

応用

Groverアルゴリズムの実用的な応用として、巡回セールスマン問題（TSP)が知られています。TSPは地図上のすべての都市を一回のみずつ通って、最初の都市に戻ってくる最短経路を求めるものです。まず、量子レジスタをルートのすべての組み合わせの可能性に対して重ね合わせの状態にします。これはチェスや将棋、囲碁等の最も効果的な動かし方などにも応用できます。動きの規則的な繰り返しを、前もって重ね合わせの状態として準備し、反転して、優勢な（私たちが求めたい解）状態のみが残ります。量子コンピュータのGroverアルゴリズムは、古典コンピュータの総当たり的なアプローチに比べて、複雑性の上昇速度が緩やかです。

しかし、この結果が問題解決の効果的な速度上昇につながるかどうかは、問題の種類や大きさによります。チェスの動きを調べたりするような、いくつかの問題に対する古典アルゴリズムは、数手先を読むためには、各ステップに対して指数関数的な計算を必要とするため、Groverアルゴリズムは指数関数的計算においては、依然として必要とされます。この事実は、量子コンピュータはすべての問題を劇的な速度で解くことができないことを表しています。

さらには、チェスもTSPもヒューリスティックで、解決策が完璧でなくても、それなりの答えを導くことができます。Groverのアルゴリズムにより適しているのは、構造が知られておらず、古典的には乱数によって可能性が求められていたものなどです。

シャッフルされたカードを無造作に探すように、構造なしに効率的なアルゴリズムを組み立てることは困難なことです。漸近的な計算複雑性を考えたとき、Groverのアルゴリズムは、古典的アルゴリズムに比べて二乗のルートの速度上昇を達成することができます。これはすべての計算に通じるものですが、どのようなアルゴリズムでも、量子コンピュータを用いれば、二乗のルートの速度上昇はするはずなのです。悪くはありませんが、私たちが純粋に考えてしまいそうな、指数関数的速度上昇ではないのです。