Previously, we have exposed the The Deutsch-Jozsa algorithm, one of the first example of an algorithm exponentially faster (1 evaluation) than any possible deterministic classical algorithm (2^{n-1}+1 evaluations). It was a great finding, but unfortunately, not of a practical great interest.

In this article, we would like to introduce another quantum algorithm, the so called **Grover's algorithm**, after the name of its founder, Lov Grover^{[1]}.

Compared to the Deutsch alfgorithm, Grover's algorithm belongs to a completely different class of algorithms represented by the **quantum search algorithm**. These provide a less striking but still remarkable **quadratic speedup** over the best possible classical algorithms.

##### Context:

Suppose you are given a large unstructured list of N items. Among these items there is one item with a unique property that we wish to locate; we will call this one the winner w.

To find the winner -- the marked item -- using classical computation, one would have to check on average N/2 of these boxes, and in the worst case, all N of them.

On a quantum computer, however, we can find the marked item in roughly **√N** steps with Grover's amplitude amplification trick.

##### Principle:

The 'database' or unstructured list is comprised of all the possible computational basis states our qubits can be in. For example, if our list contains 4 items, the list is the states |00>, |01>, |10>, and |11>. More generally, if the list is composed of 2^{N} items, the list will contain the 2^{N} states of N starting qubits.

The winner state w will be identified by a function f such as:

f(x) = 0 for x != w

f(x) = 1 for x = w

**Oracle**

In our quantum circuit, this function will be implemented as an Oracle that add a **negative phase** to the solution state.

This section of the article is only available for our subscribers. Please **click here** to subscribe to a subscription plan to view this part of the article.

By definition f(x)=0 or f(x) =1, ff we set the Oracle qubit |y> in the state 1/√2(|0> - |1>)

By examining both outputs, we can generalize the equation as:

We regard |x⟩ as flipped, thus the oracle qubit |y> is not changed, so by convention the oracle qubits are usually not mentioned in the specification of Grover's algorithm.

Thus the operation of the oracle is simply written as:

[1] Grover, Lov K. (1997). "A framework for fast quantum mechanical algorithms". https://arxiv.org/abs/quant-ph/9711043. Grover has been ranked as the 9th most prominent computer scientist from India.