Grover’s Algorithm

One of my earliest glimpses of quantum computing was in an article about Grover’s algorithm. I read the article several times. I understood the mechanics of Grover’s algorithm but not the big picture behind it. When you run the algorithm, you start with some qubits, and you change their states. After some amount of fiddling, you measure the system, and (with high probability) the correct answer appears before your eyes! Is this a real algorithm, or is it merely sleight of hand?

Several weeks later, during an hour-long train ride, I scribbled some calculations and convinced myself that the algorithm was destined to work.

The algorithm was originally published in an article entitled A fast quantum mechanical algorithm for database search. So, many months later, when I gave a lecture about Grover’s algorithm, I told students the algorithm was useful for searching through database records. One of the students asked me how database tables...

How long does it take to find what you need?

After moving from one town to another, you have 64 unlabeled boxes. One of the boxes contains your coffee pot, and you desperately need a cup of coffee. You line up the boxes in no particular order and open the first box in line. No luck. If your coffee pot were in that box, you’d have seen it right away.

You open the second box, then the third, and then the fourth. Still, no luck. If your worst fear comes true, you won’t find the pot until you’ve opened the 64th box. But chances are, the coffee pot is somewhere in the middle of the line – maybe the 32nd box. That’s still not encouraging.

What if you could turn your search into a computer programming problem? Instead of opening boxes, you search an unordered list for the words “coffee pot”? If the list has 64 elements, you may have to check all 64 items. On average, you’ll check about half of those items – roughly 32 of...

The idea behind Grover’s algorithm

The strategy underlying Grover’s algorithm is quite clever. Instead of thinking about 64 boxes the way we did in the previous section, let’s imagine that you have only four boxes. This set of four boxes is called the search space.

You’re a quantum computing enthusiast, so you’ve electronically coded the contents of these boxes and labeled the boxes |00⟩, |01⟩, |10⟩, and |11⟩. Now your search space consists of the four values |00⟩, |01⟩, |10⟩, and |11⟩. In your quantum computing circuit, you represent these values with two qubits, both of which are in the state. When you take the tensor product, you get . Remember that each of the numbers in this vector is an amplitude. The square of each amplitude is the probability of getting a certain outcome when you measure the two qubits. (See Figure 8.1.)

Figure 8.1 – A state vector...

Matrices for Grover’s algorithm

As we saw in the previous sections, each application of the Grover iterate has two parts:

1. In the first part, the oracle marks the target amplitude.
2. In the second part, the diffuser inverts all amplitudes about the mean.

Each part is a collection of quantum gates, and those gates apply a matrix to the circuit’s qubits. In this section, we’ll describe the matrix representations of the oracle and the diffuser.

A matrix for the oracle

Let’s assume that we have only two qubits. After these qubits go through Hadamard gates, we have a matrix representation of . If we want to mark the |10⟩ amplitude, we must do the following:

In general, the oracle’s matrix is the identity matrix with one of the 1s along the diagonal changed to a -1. Simple as this is, it’s also somewhat disconcerting. To know which diagonal element becomes -1, you have to know which item is...

When to use Grover’s algorithm

Before signing a contract to use Grover’s algorithm, you must read the fine print. To run Grover’s algorithm, you need an oracle that marks your search’s target amplitude. Think about the analogy at the start of this chapter. You have 64 boxes, and you wonder which box contains your coffee pot. Along comes an omniscient oracle who knows which box contains the pot. The oracle puts a mark on that box for everyone to see.

The oracle “knows” which item is the target and marks that item. But, in quantum computing, someone or something has to write the oracle’s code. Why can’t we just ask that code-writing agent which item it marked? Why bother doing inversion about the mean? Why trouble yourself by applying the Grover iterate?

For Grover’s algorithm to be useful, a search problem must have certain characteristics. Among them is the requirement that you can code the oracle without knowing...

Gates and circuits for Grover’s algorithm

Qiskit’s PhaseOracle and Grover classes provide turnkey solutions to complicated problems. Turnkey solutions can get results quickly and painlessly, but solutions of this kind have limitations. Turnkey solutions seldom apply to problems that have unusual constraints, and unusual constraints pop up often in real life. What’s more, when you apply a turnkey solution, you gain little or no insight about the way you solved the problem.

So, in this section, we will drill down into the circuitry to implement Grover’s algorithm. We will focus on satisfiability because it applies to so many kinds of problems.

Gates for the oracle

In Chapter 7, we introduced a circuit to demonstrate phase kickback. I’ve copied a drawing of the circuit here:

Figure 8.26 – The target kicks the change back to its source

Phase kickback isn’t limited to gates with two qubits. Figure 8.27 contains a three...

Epilogue – what does have to do with Grover’s algorithm?

When you run Grover’s algorithm, the optimal number of iterations is , where is the number of things you’re searching through. In this formula, you have qubits and .

Usually, the formula requires a few tweaks. For example, you can’t use the formula to search through exactly 1,000 items, because 1,000 isn’t a power of 2. Instead, you add 24 fake items to your list. Then, you use 10 qubits to search through items. And what if isn’t an integer? The value of is approximately 25.1327, and you can’t apply the Grover iterate 25.1327 times. In this case, there are ways to decide whether Grover’s sweet spot is 25 or 26, but we won’t get into that here.

In this section, our goal is to convey some idea of the role plays in the number of Grover iterate applications. Our explanation has many gaps and involves several approximations. We won’t come to...

Summary

Grover’s algorithm speeds up the search of an unordered list. We represent a list of size N with n qubits, where N = 2n. Eventually, when we measure the qubits, we see a combination of n bits. Each possible combination stands for an element in the list. Each step of Grover’s algorithm increases the probability that the measurement outcome represents the target of our search.

The optimal number of steps depends on the number of elements in our unordered list. Each step of Grover’s algorithm makes approximately the same number increase in the target combination’s amplitude. Since an amplitude is the square root of a probability, the optimal number of steps grows with . That’s better than a classical search, where the optimal number of steps grows with N.

Grover’s search can be useful when it’s easy to verify that a particular element is the search target but difficult to find the search target among all the choices. Problems...

Questions

1. How many qubits do we need to search for something in a list containing 1,000,000 entries? How many steps will the search take?
2. Write the matrix of the diffuser to search through an eight-value list.
3. Modify the code in this chapter’s Coding Grover’s algorithm with matrices section so that the target is a randomly chosen state between |000⟩ and |111⟩.
4. For what values of x, y, and z is the following expression true?

   (x | y | ~z) & (x | ~y | z) & (x | ~y | ~z) &
   (~x | y | z) & (~x | y | ~z) & (~x | ~y | z) &
   (~x | ~y | ~z)

Legend: | means or, ~ means not, and & means and.

5. Run the following code:

   from qiskit import QuantumCircuit, execute
   from qiskit import Aer
   from qiskit.visualization import array_to_latex
   circ = QuantumCircuit(3)
   circ.x(2)
   circ.h(2)
   circ.barrier()
   circ.toffoli(0, 1, 2)
   display(circ.draw('latex'))
   device = Aer.get_backend('unitary_simulator')
   job = execute...