When first trying to learn about Grover’s algorithm (GA), many people can follow the math (which is fairly simple if you understand the basics of quantum mechanics and Dirac notation), but they can’t understand the purpose of GA. Can GA be used to search an unstructured database, as is frequently claimed? For instance, can it be used to search a disordered telephone directory for the telephone number of Mary Smith? Not really. So then, what are quantum computerists raving about? Are they all lying or seriously deluded? Not really. It turns out that they are right to rave; GA is indeed a very useful result. In my opinion, the problem is that most GA expositions do an atrocious job explaining its use. So let me try to do a better job here.
I will assume that you’ve read the GA math, which you can find, for example, in this Wikipedia article.
Let be the number of states for bits. GA is most useful when is very large. However, for simplicity, let’s assume that . Suppose you have a register with bits. Let be a target configuration for that register. For example, for , might be . Let the beginning configuration be the zero configuration, the one in which all bits are zero. Suppose the job of the computer, whether classical or quantum mechanical, is to transform the register from the zero configuration to configuration .
A classical computer might do this
Here each arrow represents one step. I’ll call this sequence of steps CW (Classical Walk). On average, a CW will take steps to go from to .
A quantum computer, on the other hand, can do GA, which looks like this
Here we define . Furthermore, , , etc. denote linear combinations (i.e., Superpositions) of the vectors for .
The number of steps GA takes to reach is about , much smaller than the number of steps taken by CW. That’s because one GA step is much more powerful than one CW step. In each step, GA performs, in one fell swoop, a matrix multiplication by a HUGE matrix (albeit a sparse one).
So why can’t the classical computer (or the quantum one) just go from to (respectively, from to ) in just one step? Or else, suppose . Why can’t the classical computer (or the quantum one) do this: (respectively, )? Because the rules of the game entail that it is not possible for any step to know so well that it can change one or more of the bits to their final value in one fell swoop. That would require much more precise information about than the oracle is capable of giving.
Note that each CW step is “almost Tar-blind”; meaning that it does not depend on what is, except in deciding whether to stop or go on. It’s as if we were moving from to in a dark room, taking small blind steps, until we hit the target. Once we hit the target, we recognize it as such and stop.
Now note that each GA step is NOT almost Tar-blind; in fact, each GA step is a rotation by a small angle in the plane that contains the vectors and , and depends on the angle between and . So the GA steps are not almost Tar-blind. Far from it.
You might ask, if the CW steps are constrained to be almost Tar-blind and the GA steps aren’t, isn’t the analogy between CW and GA unfair? The analogy between CW and GA is ultimately just that, an analogy. Analogies are not unique or perfect. The only perfect analogy of X is X itself. Many people, including Grover himself, find the CW/GA analogy useful. In fact, it appears that this analogy is what led Grover to discover his algorithm in the first place. So the analogy can indeed be useful. But don’t push it, buddy. An unfortunate and very common example of pushing it too far: it’s clear that one can use CW to search a disordered telephone directory for Mary Smith. However, one cannot use GA, all alone, to do such a search. So it’s incorrect, and quite confusing to beginners, to assert that GA can be used to search an unstructured database.
If GA can’t be used to search an unstructured data base, then what good is it? Well, it is extremely useful for doing “amplitude amplification”, meaning that it magnifies the amplitude of . It tells you how to go from to in “easy” steps! By easy steps, I mean that each step can be decomposed into a SEO (Sequence of Elementary Operations like CNOTs and qubit rotations), in such a way that the SEO has a length that is merely polynomial in .
And that’s the lesson. For overachievers, here are a few additional observations:Geometric Picture of GA
If , then clearly . To prove it, just substitute 0 and 1 for on both sides. If is a normalized quantum state, then it is likewise true that . As you can see from Fig.1, the operation is a reflection: it takes any vector and replaces it by its reflection about the plane perpendicular to . Let be the plane that contains vectors and , and let be the axis perpendicular to . Reflections are a special type of orthogonal matrix. Since and are both orthogonal matrices, must be an orthogonal matrix too. In fact, one can show that is a rotation (about the axis ) by an angle . To do GA, one applies about times to , and this yields (approximately) .
Use of GA in Quantum Gibbs Sampling
Being such a rabid fan of quantum Gibbs sampling, I cannot resist mentioning the fact that quantum Gibbs sampling is an application of GA. If is a probability distribution where , then define the state . The goal of Gibbs sampling is to steer an arbitrary, known quantum state into . Then measurements of will yield samples for . These samples will be distributed according to . The steering is done using GA. (Besides GA, it takes a few more ingredients to cook a tasty quantum Gibbs sampler; for example, it also takes quantum multiplexors, Szegedy operators and quantum Phase Estimation.)