Our second major building block in Grover’s algorithm is the diffusion operator, which implements the “inversion about the mean” operation. The algorithm gives us a polynomial speedup on a broad array of problems.

Inverting About the Mean

After the marking operation discussed in the last Step, we invert the amplitude of all of the states about the mean (average) of the set. In this figure, on the left, we show two isolated examples. Accept for the moment that the average over all of the elements of the superposition is at the dashed line. In diffusion, the blue (upper) one moves toward the center of the dial when it inverts about the mean – that is, its amplitude shrinks. The orange (lower) one is the same amplitude (length) as the blue one, but because its phase puts it pointing downward, it sits below and farther from the average, so when it flips about the mean, it winds up moving away from the center of the dial – that is, its amplitude grows. (Its phase also flips, so that it’s pointed up.)

The diffusion operator is effective because of the phase of the states. In the figure below, the first step is the mark operator. The solution to our problem is the one with the phase opposite the others (orange in the figure). The possibilities that aren’t marked (the blue bars) all point up. As shown in the third column of dials, this results in an average of the bars as shown, close to the tip of the blue bars.

For our four-possibility chess example, let’s see what happens when we run the mark-diffuse sequence once. The amplitude of a losing move sequence (each blue bar in the figure below) becomes zero and the amplitude of the winning move sequence (orange bar) becomes one.

After these steps, we measure the two qubits and learn which one of the move sequences had been marked, with probability one. In this case, the measurement result becomes (vert 10 rangle) which corresponds to the third move sequence. Recall that our marking function (f(x)) identifies solutions to the problem, but it does not a priori know what value or values of the input (x) will be flipped; all of them are done at the same time, in superposition.

All of this happens because of the constructive interference that causes the amplitude of our answer to grow and the destructive interference that causes the incorrect possibilities to shrink.

Performance

In our four-possibility chess example, as it happens, only one iteration of our mark-diffuse sequence is needed to raise the amplitude of the answer to one. For larger problems, the average is very close to the unmarked states. Therefore, the first few iterations don’t have much of an effect, but eventually the growth of the orange vector starts to pick up speed until it accumulates half or more of the total wave function, at which point it’s time to stop and measure it. (The exact number of iterations that it takes depends on the number of marked states versus the number of unmarked states, but a variant of Grover’s algorithm allows you to estimate that ratio, as well.)

As a general case using a classical computer, with (N) possibilities and only one answer, the worst case is that we have to check all (N) possibilities, and the average number we will check is approximately (N/2). Using a quantum computer with (log{N}) qubits running Grover’s search algorithm, we can find the value of (x) we are looking for with only (O(sqrt{N})) executions of the mark-diffuse routine.

Applications

Practical application of Grover’s algorithm to solving the traveling salesman problem (TSP) is known. TSP asks us to find the shortest possible route that visits all of the cities in a list exactly once and returns to the starting city. We preset the state of our quantum register to a superposition of all of the possible permutations of routes. We can also apply this search procedure to find the best move for chess, shogi, or go. Preset our state to a superposition of all legal sequences of moves, and flip the phase of any position in which we win. The computational complexity of Grover’s algorithm grows more slowly than brute force classical algorithms that simply try every possibility.

However, whether this results in a useful speedup depends on the problem type and size. Classical algorithms for some problems, such as examining chess positions, require exponentially more computation for each additional step you try to look ahead, so the corresponding execution of Grover’s algorithm will still require exponential amounts of computation. It can be said that this fact suggests that quantum computer cannot solve all problems with a usefully dramatic speedup.

Moreover, both chess and TSP have known heuristics that provide pretty good, if not perfect, solutions. Better candidates for Grover’s algorithm are those with no known structure, where our best order for testing possibilities classically would be no better than random.

It is hard to construct efficient algorithms for problems without structure, such as searching through a randomly shuffled set of cards. Considering only the asymptotic computational complexity, Grover’s search algorithm achieves a square root speed up compared to classical algorithms. This is true for all computations, so the worst case improvement for any algorithm using a quantum computer should be a square root speedup. Not bad, but not the exponential speedup we might naively think.

拡散とパフォーマンス

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のアルゴリズムは、古典的アルゴリズムに比べて二乗のルートの速度上昇を達成することができます。これはすべての計算に通じるものですが、どのようなアルゴリズムでも、量子コンピュータを用いれば、二乗のルートの速度上昇はするはずなのです。悪くはありませんが、私たちが純粋に考えてしまいそうな、指数関数的速度上昇ではないのです。