Finding the Needle in a Haystack on a Quantum Computer

Grover’s quantum search algorithm finds the target element from a list of unordered elements in O(√N) time.

You are given a list of numbers and a target number, and you are asked to find the index in the list at which the target number appears. If the list is sorted, you can use search algorithms such as binary search. But if the list is not sorted, there isn’t really much you can do; you simply have to traverse the whole list till you find the element. In terms of algorithmic complexity, this takes O(N) time. With a quantum computer, however, you can solve this problem in just O(√N) time. This article explains how this is achieved by the Grover’s search algorithm.

If you’re new to quantum computing, you should first read this short primer: Quantum parallelism — where quantum computers get their mojo from.

Needle in a haystack (Image from Pixabay)

Let’s start by framing the problem. We are given:

• A set of N elements X = {x_1, …, x_i, … ,x_N} such that each x_i is an m-bit string made of 0s and 1s.
• A target element x* that is also an m-bit string made of 0s and 1s
• A function f that takes as input an m-bit string and returns 1 if the string is x* and 0 otherwise. This function can be written as:

Grover’s search works in three steps as described below.

Step 1: Setup the state

A quantum state is set up in an equal superposition of the basis states. As an example, consider N=8. We set up the state using 3 qubits as:

Step 2: Phase inversion

In the second step, we flip the amplitude of each element x if f(x)=1 and leave it unchanged if f(x)=0. This is performed using a circuit that implements the below unitary gate O:

Suppose our target element x* is present in the fourth location. Applying the gate O will give us:

Step 3: Inversion around the mean

The third step known as inversion around the mean involves flipping all the elements around their collective mean. This is performed using Grover’s diffusion operator which is given by:

Applying this operator to our quantum state gives us:

This completes one round. If we were to measure the system at this point, we would get the target element as the outcome with a probability (5/(4*√2))² which equals 78%.

The second and third steps are repeated √N times to maximize this probability. After the second iteration, we get the below state which will find the target element with a probability of 95%.

Like many quantum algorithms, Grover’s search is probabilistic. It gives you the correct result with a high probability. In order to make this probability large enough to be practically useful, you may need to run it multiple times.

The same algorithm can also be used to find k-matching entries instead of a single target element. Many variations have been proposed. One of them is the Durr and Hoyer minimization algorithm which finds the index of the smallest element from a list — this has found interesting applications in quantum machine learning. For details, please refer to: Quantum Computing Methods for Supervised Learning.

If you liked the article, check out my other pieces on Medium, follow me on LinkedIn or Twitter, view my personal webpage, or email me at viraj@berkeley.edu.