Understanding Grover’s Algorithm

The quantum advantage for an unordered search

Implementation of Grover’s algorithm in Qiskit

Suppose you’re given a list of objects in no particular order and you want to find a specific item among them. What algorithm could you use to keep yourself from searching the entire list?

In computer science and quantum research, this problem is nontrivial, and it’s where Grover’s algorithm becomes very useful. Intended for unstructured search problems, its use of quantum properties like superposition, entanglement, and interference speed up its execution time compared to that of classical algorithms.

In IBM’s Qiskit blog post “Learn Quantum Computing with These 7 Projects”, they suggest implementing Grover’s Algorithm as a fundamental exercise to better understanding this ever-growing field, stating:

One of the most talked-about applications of future quantum computers is the ability to perform an unstructured search through a database faster and more efficiently than a classical computer with the help of Grover’s algorithm. Grover’s algorithm could offer a quadratic speedup in these unstructured searches, meaning that, while a classical search through a list of size N could take between N/2 and N tries to find an item, Grover’s algorithm would only take √N steps. However, Grover’s algorithm is more than just a searching tool; it uses a routine called amplitude amplification that might provide quadratic speedups for other algorithms as well.

So again, suppose you are given an unordered list of 𝑁 items, and you want to find one of these items (we will call this special item the “winner” 𝑤). According to the experts, Grover’s algorithm provides a solution!

On a classical computer, the approach is trial and error one at a time. The probability of picking the correct item is equal to 1 over the number of remaining unchecked items, or 1/Nᵢ, so the complexity of the classical solution is O(N).

• Average case: we would have to check 𝑁/2 of these boxes
• Worst case: we would have to check all 𝑁 of them!

But as we have discussed before, quantum computers often have advantages when it comes to running certain algorithms, and Grover’s algorithm is one such example. These advantage include:

1. Quantum speed-up: finding the marked item in roughly the square root of N steps (so the complexity is O(√N)) with Grover’s amplitude amplification trick. A quadratic speedup is a substantial time-saver for finding marked items in long lists
2. Generality: the algorithm is generic, i.e. it does not use the list’s internal structure; therefore, it can be applied to a large group of classical problems

Classically, an unstructured search problem can be reformulated in terms of a the classical oracle 𝑈𝜔(𝑥), defined as:

This oracle function marks any value that fulfills the given criteria. The goal is to find the value of 𝑥 which makes the oracle return 1, meaning x is the our marked item 𝜔. After marking the item, we must then apply another function — the diffuser function — which improves the likelihood of the algorithm returning the location of 𝜔 as opposed to any other item.

For the quantum algorithm, we start with a set containing all the possible computational basis states for a given number of qubits, with one of these states being the winner.

• If we have 2 qubits, we can search a set of 2² = 4 items, labelled as {|00⟩,|01⟩,|10⟩,|11⟩}, i.e. states {|0⟩,|1⟩,|2⟩,|3⟩}
• If we have 3 qubits, we can search a set of 2³ = 8 items, labelled as {|000⟩,|001⟩,|010⟩,|011⟩,|100⟩,|101⟩,|110⟩,|111⟩}, i.e. states {|0⟩,|1⟩,|2⟩,|3⟩,|4⟩,|5⟩,|6⟩,|7⟩}
• Therefore, if we have 𝑁 qubits we can search a set of 2^N items, labelled as {|0⟩,|1⟩,|2⟩,|3⟩,…|2𝑁⟩}.

In this case, the oracle will return an identity matrix with one of the 1s in the diagonal having a flipped sign to represent the position of the winner. So if the given basis state is the winner, the oracle will flip the sign of the 1 corresponding to that position.

So for 2 qubits, we have a set of 4 elements, {|00⟩,|01⟩,|10⟩,|11⟩}. Let’s say the winner is |11⟩. The oracle in this case acts as follows:

which you may recognize as the controlled-Z gate. The oracle and the reflection together are referred to as “Grover’s Iterate”, and the reflection by itself is “Grover’s diffusion operator”.

With amplitude amplification, we are able to increase the probabilities of the winner while reducing the probabilities of all non-winners. Roughly √N repetitions of this process, where N is the size of the list, amplifies the amplitude value associated with the location of the marked item enough to confidently return that location.

When using the algorithm on a quantum computer, the first step is to prepare a uniform mixture of all possible items in the database. This can be accomplished by applying a Hadamard gate on each qubit, which results in the state s:

In geometric terms, it can be written like so:

where |𝜔⊥⟩ is the state orthogonal to |𝜔⟩. In this instance 𝜃 = 30 degrees, but for 𝑛 qubits, 𝜃 =arcsin1/(2^(𝑛/2)).

The goal of the algorithm will be to apply unitary transformations which have the effect of rotating the current state vector |𝑠⟩ until it approximately aligns with the state |𝜔⟩, where a measurement of the state vector will reveal the identity of 𝜔.

The amplitude amplification proceeds in two steps, which should be repeated the appropriate number of iterations (too few iterations means not finding 𝜔, and too many iterations will cause us to miss 𝜔).

When we call the oracle, it flips the sign of the real answer |𝜔⟩. In other words, it changes the sign of 𝜃:

The geometric interpretation is shown below:

Note that the amplitude in front of the |𝜔⟩ state becomes negative, which in turn means that the average amplitude has been lowered.

We then do inversion about the mean (which is a reflection with respect to state |𝑠⟩), which involves an additional reflection (𝑈𝑠) about the state |𝑠⟩:

so that the state |𝑠⟩ stays invariant. The combined effect of 𝑈𝑠𝑈𝜔 is to rotate the state |𝑠⟩ by a net angle of 2𝜃, so that the transformed state is now at an angle 3𝜃 with respect to the x-axis (the state |𝜔⊥⟩).

For the optimal number of iterations through the algorithm, the formula is

Conclusion

I know with the geometric interpretation, Grover’s algorithm can get pretty confusing, but the takeaway should be a general understanding of amplitude amplification which allows a speed-up in runtime efficiency, and how this gives a quantum advantage.

In my next post, I will cover the general implementation of Grover’s algorithm in Qiskit, as well a specific instance where it can be useful, using an exercise from IBM’s 2020 Quantum Challenge. Seeing it implemented in code will illustrate how it’s actually a relatively straightforward algorithm.

For any additional questions, the documentation for Qiskit can be found here, and the official Qiskit textbook by IBM can be found here. To get more involved with Qiskit, check out their blog here and their slack workspace here.