Skip to 0 minutes and 3 secondsIn 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.
Skip to 0 minutes and 44 secondsGrover 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.
Skip to 1 minute and 29 secondsIn 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.
Skip to 2 minutes and 16 secondsInstead, 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.
Skip to 2 minutes and 56 secondsIf 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.
Introduction to Grover's Algorithm
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 does , for some number ?”
A quantum computer allows us to calculate for a superposition of all values of 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 , 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.
© Keio University