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