Skip main navigation

Introduction to Grover’s Algorithm

Rod Van Meter and Takahiko Satoh outline the behavior of Grover's algorithm.
3.1
In the first week of the course, we discussed search problems as one of the motivations for building a quantum computer. We used chess, go and shogi as examples. The most general quantum algorithm is Lov Grover’s search algorithm, so let’s take a look first at what kinds of problems it can solve, and what happens in the algorithm so that it gives us the answer we want, then in the next step we’ll look at how it uses entanglement and interference. As we saw in the first week, chess is actually not a great candidate for solving using Grover’s algorithm, but it’s a nice example of what happens, so we’ll stick with it.
43.9
Grover allows us to answer the question, “For what value of x does f(x)=k for some number k?” In our chess example, k would be a boolean, true if we win or false if we lose, and x would represent the sequence of moves. For trip planning, x might be a candidate route that drives past all of the county courthouses in the state of West Virginia in a particular order. In optimizing resources used in a factory, it might be a particular manufacturing plan. A quantum computer can assess all of the possibilities at once, in superposition.
88.6
In our chess example, we create a superposition of white’s first twenty moves and black’s first twenty moves and all of the following possibilities, all 10^120 at the same time We can calculate whether each sequence results in a win or a loss. The problem is that we can’t extract any useful information from this superposition. All of the possible move sequences have equal weights, or probability amplitudes. If we just run this calculation once, and measure the state of our quantum computer, measuring each of the possible sequences is equally likely. We gain information only about a single sequence, which is almost no help toward solving our bigger problem.
135.8
Instead, the algorithm is engineered to increase the quantum probability amplitude of moves that win, and decrease the amplitude of moves that lose. The first time we do this, the increase in probability is small, so we keep repeating the process, growing win amplitudes and shrinking lose amplitudes, until we have a high probability of getting a good answer when we measure our qubits. So how fast is it? If there’s no structure in the problem that we know of, then a classical algorithm has no choice but to look at each possible value of x and see if f(x)=k, until it finds the answer.
175.7
If there are n possible values for x, then on average, we will have to try half of them, N/2, before finding the answer. Grover’s algorithm uses entanglement and interference to grow those probability amplitudes faster than a simple linear check of all possible values. Instead of N/2 tries, around √N calculations will be enough. This change is a polynomial speedup for the search. Not as big a win as Shor’s algorithm, but it’s a much broader, more flexible algorithm, and is used as a part of other quantum algorithms, as well. In the next step, we will see more details of how the algorithm works.

The most general quantum algorithm is Lov Grover’s search algorithm. Using entanglement and interference, it allows us to answer the question, “For what value of (x) does (f(x) = k), for some number (k)?”

A quantum computer allows us to calculate (f(x)) for a superposition of all values of (x) at the same time, but not to extract useful information from that superposition directly. Instead, we use the result to increase the amplitude of good values of (x), and repeat until we have a high probability of reading out the value we want.

In this video, we outline the behavior of the algorithm, then in the next two Steps will we see the operation in more detail.

Groverのアルゴリズムの概要

最も一般的に認知されている量子アルゴリズムはLov Gloverの探索アルゴリズムです。 量子もつれと干渉を利用することで、「ある値(k) をもとに(f(x) = k)を満たす(x)の値を見つける」という問題を解くことができます。

量子コンピューターは、全ての値を重ね合わせることで、同時に多数の計算することが出来ますが、重ね合わさった出力から有益な情報を直接取り出すことはできません。 代わりに、その重ね合わせを利用し、解となる値の振幅を増やす作業を、必要としている値が観測される確率が十分に高くなるまで繰り返す必要があります。

この動画では、アルゴリズムの仕組みを説明し、次の2ステップでより詳細に操作について見ていきます。

This article is from the free online

Understanding Quantum Computers

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education