Skip main navigation

Diffusion and Performance

Grover's algorithm can be applied to any unstructured search problem, and gives a square root speedup.

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.) grover-average

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.


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.


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.




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


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

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




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

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






© Keio University
This article is from the free online

Understanding Quantum Computers

Created by
FutureLearn - Learning For Life

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now