Quantum Search

Grover’s Algorithm was proposed by Lov Grover in 1996. Like the Deutsch-Jozsa Algorithm, a quantum algorithm is empirically faster than our fastest classical solution to the same problem. How much faster? Grover’s Algorithm provides a quadratic speedup over its classical counterpart. While at first sight, it is not as remarkable as the exponential speedup of the DJ Algorithm, one can argue that Grover’s solution is immediately useful and provides a great blueprint for solving similar problems.

The problem that Lov Grover solved using his algorithm is related to searching an unordered collection of items. Imagine an unordered list of elements from which we want to search for a particular item. For example, in the following array, we want to find -6, the second-to-last element.

Take a moment and think about how you would approach this problem classically. Take the general case and ask yourself:

• What’s the fastest way to find an element in an unordered collection?

Classical solution

Since there is no internal structure or metadata that we can use to speed up our search, the best we can do classically is a linear search. In a linear search, we start from the beginning of the list and iterate over all elements. In each iteration, we inspect the current element and see if that is the one that we were looking for initially. If we have encountered that item, great, we stop our search. Otherwise, we move ahead and check the rest of the list until the last element. What’s the time complexity of such a solution? If we’re lucky, the first item we inspect is the one we sought. In that case, the complexity is $O(1)$. In the worst case, we iterate through the list, and either the element is right at the end, or it does not exist at all. In that case, the time complexity is $O(N)$. So, in the average case, we’ll have to inspect $50\%$ or $\frac{N}{2}$ elements of the list.

It genuinely seems like this is the best we can do no matter how we approach the problem. But that would be myopic on our part. We can solve this problem much faster on a quantum computer using Grover’s Algorithm, which has an asymptotic time complexity of $O(\sqrt{N})$.

At this point, some people might argue that binary search with $O(log\space N)$ complexity after sorting the data would be much faster than the proposed $O(\sqrt{N})$. But there are two things we need to remind ourselves of here. Sorting this array would most probably require a comparison-based sort, giving an overhead of $O(N\space log\space N)$. Also, we are talking about a generic, unstructured search via an algorithm that does not depend on the structure of the data itself. So, sorting would defeat that purpose.

With that short clarification out of the way, let’s dissect Grover’s Algorithm, which not only provides us the required generic algorithm but also extracts a quadratic speedup over its classical counterpart.

Quantum solution

Grover’s Algorithm uses three foundational techniques from quantum computing. We’ve already used two techniques in the previous chapter on the DJ Algorithm, superposition and a quantum oracle. The third technique is dubbed amplitude amplification, and we will study it in detail in this chapter.

First, let’s revisit the array above in which we had to find -6. Since we work directly with qubits, it’s helpful to reformulate the array where every element is a bit string. That way, we can input and encode all this information in our quantum computer before searching for the required element. Writing the binary representation of all those elements would lead to messy working. Let’s instead restructure the problem as follows:

• From all possible computational basis states that $n$ qubits can be in, find a particular state, say $x$.

This way it’s helpful to think of the search-space for $x$ being all bit-strings of length $n$, which corresponds to $2^{n}$ possible items in the collection list. For three qubits, our search space would be the states $|000\rangle, \space |001\rangle\space ,...,\space |111\rangle$ or $|0\rangle, \space |1\rangle\space ,...,\space |7\rangle$. And let’s say our $x$, which is what we have to find, is $|101\rangle$ or $|5\rangle$.

Superposition

The notation above is a handy way of representing the same problem. You would have noticed that we encountered an analogous situation in our study of the DJ Algorithm. This state-space of allowing all possible bit-strings of a certain length allows us to exploit superposition. We already know that superposition allows us to input a whole fleet of states at once into the quantum algorithm for processing. Maybe that can lend something fruitful in our search problem too?

Let’s apply the same trick here as well. This is simple enough to do. The Hadamard gate $H$, puts a qubit into an equal superposition. We take $n$ qubits and put them in equal superposition, a state that is represented by $\frac{|0\rangle+\space|1\rangle}{\sqrt{2}}$ for one qubit, and for $n$ qubits, as $\frac{\sum{_{x}|x\rangle}{}}{\sqrt{2^{n}}}$. For clarity, we can substitute $N=2^{n}$ to get $\frac{\sum{_{x}|x\rangle}{}}{\sqrt{N}}$.

So now, we have our qubits in equal superposition. We input this to our quantum algorithm. But what is the quantum algorithm? Again, let’s circle back to our trusty old friend, the DJ Algorithm, and see what we can do next.

Oracle formulation

Let’s try creating an oracle for our quantum search algorithm too. After all, that’s what we did right after the equal superposition stage in the DJ Algorithm. However, the oracle that we are going to create for this problem is slightly non-intuitive. Instead of addressing the problem directly with an oracle that searches and returns the required state, it is easier to create an oracle that verifies whether a given element or solution is indeed what we are looking for. This also allows us to make a generic solution for any state space that we want our algorithm to work in, which we wanted initially.

We can map this problem of checking a solution to a function. This function $f$ will take a state as input and then output $0$ if the state is a valid solution and $1$ if the state is an invalid solution. Formally, for a state $x$, $f(x)=0$ is a valid solution $(x=w)$ and $f(x)=1$ if $x$ is an invalid solution $(x\neq w)$ , where $w$ is the element we want to find. Now, to mark states with invalid solutions, our oracle can add a negative phase to them. This conveniently distinguishes our valid state from a positive phase.

Taken together, our solution checking oracle, $U_f$, for the search algorithm can be defined as follows:

$$U_{f}= \left\{ \begin{array}{ll} |x\rangle & x=w\\ -|x\rangle & x\neq w \end{array} \right.$$

In other words, this oracle takes a state and acts on it as follows: $U_f|x\rangle=(-1)^{f(x)}|x\rangle$. We’ve created an oracle like this using the $CNOT$ gate coupled with the ancillary qubit in $|-\rangle$ to bring about a phase kickback that adds a negative phase to the control qubits, leaving the target ancillary qubit alone.

Premature measurement

So far, we have generated the equal superposition state, $|E\rangle$, for our search space and applied the oracle, $U_f$ to it, which can check if a given state $|x\rangle$ is the required state that we want to search, $|w\rangle$. Does this help our cause in any way? Not exactly, but there is a method to all this madness. Here’s why.

Despite the application of the oracle, our qubits are still in an equal superposition, where our final state is equally likely to be any one of the $2^n$ possible states. This gives us a probability of $\frac{1}{2^n}$ for measuring the state we set out to find initially. Remember, the negative phase we added did not change the probability of measurement because $|1|^{2}=|-1|^{2}$. So, if we were to measure our qubits now, it is quite likely that we would not get the value/solution we were looking for. And herein lies the conundrum. We need a mechanism with which we can amplify the probability of that coveted state, which is enshrouded in the superposition somewhere, and reduce the probability of the rest of the states that we do not wish to find.

This is where the true essence of Grover’s Algorithm shines through. By using a process known as amplitude amplification, we shall manipulate these state amplitudes and, in the process, reach closer and closer to the coveted element that we seek. Let’s dive into the process in the next lesson.