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 (2n-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.



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.



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 2N items, the list will contain the 2N 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



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". Grover has been ranked as the 9th most prominent computer scientist from India.