Grover’s Search Algorithm explained

Grover’s Search Algorithm:

Grover’s Search Algorithm performs a search over an understood and unsorted database of N entries for accessing a particular entry. Using a classical computation model a solution can be obtained by checking every item in the database to find the desired one. This search in the worst case will require a time-complexity O(N).

Grover developed an algorithm that finds a marked item that is the item of interest x* in a set of N elements (x₁, x₂,…, x_n). It completes the search in time complexity O(√N) by utilizing the nature of quantum systems.

All N items in the database are simultaneously encoded in n qubits, where n is the number of qubits necessary to represent the search space of 2ⁿ = N. The items in the database are labelled as n-bit Boolean strings in {0, 1}ⁿ, not indexed from 1 to N.