The Search Problem: Grover's Search

As the amount of data is always increasing in databases, it becomes even more essential to have a reliable way to search for information efficiently. One of the common ways to search in an unstructured (not sorted) database is through linear search. However, as the database grows larger the number of queries needed increases linearly, until it may take minutes or even hours to search. This is what Grover’s algorithm aims to solve in the future.

Grover’s algorithm is a quantum algorithm that leverages amplitude amplification to demonstrate a quadratic speedup to unstructured search by using superposition and interference of quantum mechanics. This means that Grover’s algorithm requires the square root amount of queries to search a database, compared to linear search.

There are three main steps to Grover’s algorithm: superposition, amplitude amplification, and measurement.

The first step is quite simple because it is applying the H gate to each qubit, where the number of qubits is determined by taking the square root of the input size (in some cases this would lead to a decimal, thus the number would have to be rounded up to the nearest whole number).

The second step is amplitude amplification. This step is done for a certain amount of iterations to make the correct item in the search have a high probability and the incorrect items in the search have a low, if not zero, probability. The first part of each iteration is to apply an Oracle, which flips the sign of the state corresponding to the item that is needed to be found. The Oracle affects only the item that is trying to be searched for because based on the design of the algorithm, it knows the properties to affect. This is similar to using a magnet to find a metal needle in a haystack. The second part of each iteration is to apply Grover’s Operator, which flips all amplitudes over the average. As a result, the incorrect items’ amplitudes/probabilities decrease, and the correct item’s amplitude/probability increases. To determine the optimal number of iterations to use during this step, Grover uses the following formula:

The last step is to measure the circuit. The state with the highest probability of being the solution to the query will be the result.

Despite this quadratic speedup, Grover’s algorithm is a long-term algorithm, meaning it will require much more powerful quantum computers compared to current noisy quantum computers. It is estimated that a quantum computer of 10,000 logical qubits is needed to see an advantage over linear search.