One of the great challenges to understanding Grover’s Algorithm is that it is very poorly described. Therefore, except for this sentence, this article does not use the word “database.” For that matter, it doesn’t use the word “search” beyond this sentence, either. Neither term is accurate, and their longevity is perplexing. Enough people know this by now that you would think this could change, but I digress.
So, what is it?
Normally, algorithms take inputs and produce outputs. For example, with an adder circuit, you input 2 and 2 and the output is 4. Sorry: spoiler alert! Grover’s Algorithm, however, works backward. We want a 4, so we want to know the numbers we can add together to get to 4: 0 + 4, 1 + 3, and 2 + 2. This is why you might see Grover’s Algorithm mentioned in regards to factoring numbers, however Shor’s Factoring Algorithm still steals the show performance-wise for that specific application.
To add to your potential confusion, however, Grover’s Algorithm has been proposed as a solution to a great many things. Therefore, my characterization of “working backward” might not be complete. I’m not claiming to have analyzed every possible application. That said, my characterization is probably the most common application.
Before diving in too deep, let’s review the above circuit. Grover’s Algorithm has four distinct sections, separated here by dashed black lines. From left to right:
- Hadamards galore! But, wait… where are the inputs?!?!? There aren’t any! Again, Grover’s Algorithm works backward. We don’t know the inputs. Yet. I remember the first time I looked at this algorithm and I was absolutely baffled by that. But, anyway, we’re just putting the qubits into superposition so the “magic” can happen. Every qubit starts with an equal probability of measuring 0 or 1, which tells us nothing, but the next two sections are going to transform those probabilities until the measurements at the end tell us something useful.
- The “black box” oracle. Early tutorials told us we weren’t allowed to know how they work, but that’s nonsense. What makes the oracle true? That’s all it’s asking. Oracles are essentially Boolean functions that only care about what is true, and couldn’t care less about what’s false. This applies to negatives, as well, which may seem a little counterintuitive. If you want to know (this AND NOT that), for example, the oracle only cares what makes the whole statement true. To implement Grover’s Algorithm, this oracle section is the meat and potatoes; you’ll find that the other sections adapt only to the number of qubits in use, and they don’t otherwise require any special configuration.
- The diffusion operator. This is where amplitude amplification happens. Simply put, each measurement gives us one bit of information. Each bit, before measurement, has a probability of measuring zero and a probability of measuring one. This section takes the highest probabilities and makes them higher, at the expense of the lowest probabilities, which end up lower. We end up with greater separation in the results, making it easier to find the correct answer(s). Keep reading for a visual explanation of this phenomenon.
- Measurements. In this example, what makes a CZ oracle true? The answer is: 11. There’s no great explanation why, by the way, but the Qiskit textbook breaks the gate down and Wikipedia shows its matrix. But, you also have to understand phase kickback. Put that all together, and the bottom line is that tutorials really should not include this gate, but they do because a CZ oracle allows the most compact implementation of Grover’s Algorithm and phase kickback probably helps the oracle’s inner workings seem mysterious.
It’s important to note that with larger examples steps 2 and 3 repeat. The optimal number of iterations is the square root of the number of qubits. You’ll always know if you did one operation too many, because the quality of the results will backtrack.
So, besides errant terminology, what makes Grover’s Algorithm challenging to understand?
Examples Are Too Small
One of the challenges to understanding Grover’s Algorithm is that it is often explained with as few as two qubits. I’ve reviewed my earliest blog articles, and that’s how I “learned” it. At the time, I only remember two-qubit and three-qubit examples being available. I was novice enough to not know where to look, but that’s a problem for every novice who doesn’t know where to look.
One of the problems with two-qubit and three-qubit examples is that you can probably eyeball the solution. If my oracle is a Toffoli gate, aka “CCX”, aka “controlled controlled NOT,” aka “AND,” I am looking for inputs that make the oracle true. An AND gate is true when both inputs are 1. Therefore, Grover’s Algorithm is going to tell me, when I measure the two control qubits, that I need two 1’s as inputs to output a 1 when my oracle is an AND gate. If you understand logic gates at all, these demonstrations are thoroughly uninspiring.
By the way, you hopefully just noticed that we needed two 1’s as inputs for both the CZ gate and the Toffoli gate. If you’re learning about Grover’s Algorithm for the first time, such a realization might add further confusion. This is why better examples are needed.
Why, then, are the examples so small? Because building oracles is hard.
Examples Are Useless
What is the use case for Grover’s Algorithm with either a CZ oracle or a CCX oracle? For that matter, what is the use case for Grover’s Algorithm with most of the oracles you find easily online? The answer, as alluded to in the immediately previous section, is nothing. If you can eyeball the solution, you don’t need to implement this algorithm at all. Unfortunately, that initially makes the whole algorithm seem useless.
Keep reading, though, because I will conclude this article with a small, useful example. And, although you can still figure that example out with pencil and paper, it hopefully shows how Grover’s Algorithm might be helpful with more complicated problems.
Inconsistent Diffusion Operators
Another potential challenge to understanding Grover’s Algorithm is the inconsistency in constructing diffusion operators. The image above is not necessarily an exhaustive list of diffusion operators, but it shows examples of what you might see first if you search the Internet. There are, of course, variations that are identical conceptually, just with more qubits, more operations, and more overall complexity.
Again, diffusion operators are where amplitude amplification happens. Your oracle gives you probable answers, possibly quite a few of them. But, some may be more correct than others. This part of the algorithm amplifies the best answers at the expense of the worst answers.
How does amplitude amplification work, you ask?
Textbook explanations must be unsatisfying, otherwise we ought to stop seeing new tutorials by now. So I’m going to take a completely different approach: a visual approach. In fact, I’m going to let you play with this circuit using Quirk. The URL is quite long, so here is a shortened link: https://cb.run/fFY2. I encourage you to walk through it Bloch sphere, gate, Bloch sphere, gate, ….
The reason why the algorithm is not completely intuitive is because of a combination of entanglement and Hadamard transformations. A Hadamard gate does not simply rotate from 0 to +; it actually rotates a roundabout way around both x and z axes. So, once you rotate away from 0, 1, +, and – via a Hadamard gate, the new state is probably only intuitive through linear algebra. The other two gates are fairly intuitive, which is why I selected a Bloch sphere above that emphasizes the x and z axes. An X gate rotates halfway around the x axis and a Z gate rotates halfway around the z axis. If you click on the Quirk link above, you can follow along through each transformation — H then X then Z then X then H — and literally watch as the “true” answer emerges. Hopefully you can visualize the “inversion about the mean” that every book and tutorial describes mathematically.
However, even knowing how all those gates work, you still have to wonder how the algorithm knows what we’re looking for. The first two Hadamards of the diffusion operator seem to move us somewhere arbitrary, don’t they? But, as alluded to in the first sentence of the previous paragraph, the qubits are entangled! Therefore, we’re not applying gates to individual qubits; we’re applying gates to two-thirds of an entangled state. Anytime you have Hadamards acting unpredictably, check for unwanted entanglement. In this case, though, that’s where the magic is happening. There’s our solution, our initial amplitudes that we want to amplify.
So, what’s a practical example of Grover’s Algorithm?
A better example of Grover’s Algorithm is the circuit above. It’s output (simulated) is the histogram below. Tutorials don’t show examples like this because satisfiability problems are harder to explain, plus they introduce the concepts of ancilla qubits and disentanglement. Tutorials on Grover’s Algorithm can get quite lengthy without even getting into those topics.
But, I use it as an example of a better problem. If you look at the top three qubits, you can hopefully see the problem I’m trying to solve. After the initial Hadamard gates, there is a Toffoli gate. As explained earlier, the Toffoli gate performs an AND operation. So, the top two qubits must be 1 to satisfy the oracle. The third qubit, then, is a NOT operation. So, that qubit must be 0 to satisfy the oracle. And, following that, is another AND operation, because I want the first two qubits to be 1 AND the third qubit to be 0. Textually, we can describe the problem as I want ((coffee AND energy drinks) AND (NOT tea)). The histogram above shows that there is, in fact, no tea at my party, but there’s bottomless coffee and a selection of my favorite energy drinks.
While that is admittedly still a simple example, you can hopefully imagine more complex examples. Define a problem that includes an assortment of ANDs, NANDs, ORs, XORs, or whatever you require. The oracle gets wicked quickly, which is why you don’t see this explained. Worse, tutorials are shifting away from this entirely, and toward building oracles textually. That’s fine if you’re simply looking to solve a problem, but it literally turns oracles into the “black boxes” they were initially characterized as.
Qiskit’s Satisfiability Tutorial
Finally, here’s a simple-yet-practical problem that demonstrates Grover’s Algorithm’s potential. Qiskit’s tutorial describes a dinner party with four prospective guests. Guest0 and guest1 are friends, guest 2 and guest 3 are friends, but guest0 and guest3 would not want to be at the party together. So the textual problem is ((guest0 AND guest1) OR (guest2 AND guest3)) AND (NOT (guest0 AND guest3). Now, that may satisfy Qiskit and the oracle, but it doesn’t satisfy me. I like to break open black boxes and peek inside. The circuit at the top of this article is what you might find; it works.
The histogram above shows that you can invite:
- Guest0 and guest1
- Guest0, guest1, and guest2
- Guest2 and guest3
- Guest1, guest2, and guest3
All of these combinations satisfy the oracle… and me.
I remember being perplexed when I first read about Grover’s Algorithm. I promised in the introduction that I wouldn’t repeat two certain words, but I was looking. Where do I input data? How do I add a fourth qubit? Why am I not allowed to know how the “black box” oracle works?
I disregarded this algorithm for a long time because of all that. But, it turns out that Grover’s Algorithm has a bunch of proposed use cases that make sense. Just keep in mind that classical terminology may be inappropriate.
Finally, while oracle construction isn’t easy, it’s not impossible. It certainly isn’t mysterious. Go ahead and ask a question….