Published by: Amit Nikhade
June 11 . 2021
When you change the way you look at things, the things you look at change. -Max Planck
I have tried simplifying the algorithm to max level, to make it understandable for a beginner too.
Quantum computing has battered classical computers, in terms of their acceleration in solving complex problems. Quantum computers harness the phenomenon of quantum physics to store data and to perform computations. The basic unit of quantum memory is the quantum bit or qubit, similar to the bits 0’s and 1’s in classical computers. But still, there are problems where the classical ones beat the quantum computer, so using both of them according to the computational need will be a superior combination of accelerated computing.
Let us dive into one of the most significant algorithms in quantum computing by Lov Kumar Grover, who discovered Grover’s searching algorithm in 1996, An Indian scientist known as one of the most prominent computer scientists in India.
Grover’s algorithm i.e the quantum algorithm solves one of the complex scenarios in the area of computing. It’s the second major algorithm proposed for quantum computing. It solves the problem of searching through unstructured data. Let’s go a bit deeper into it.
let’s consider a situation where you have a list of unsorted numbers N as shown in the below diagram, where you want to find a value w (Red Box) from it that possesses some unique properties. So how could you find w?
Classical approach: In classical computing, we would have to check on average N/2 of these items in the list. In simple terms you would have to verify each of them one by one, In which you will require N steps i.e O(N). if random access and pre-sort are added to implement binary search on ordered data, it will require log(N) steps i.e O(log(N)). however, using a quantum algorithm will just roughly take √N steps i.e O(√N) for finding w, for instance, let’s take a list of 25 elements and we want to search for a value from the list so classically it will take N steps and with the quantum algorithm, it will take √N steps i.e classically it will take 25 steps and quadratically it will take √25=5 steps.
It utilizes superposition and phase interference to improve the search. It’s the amplitude amplification that plays a very spatial role in searching the element we want. let’s visualize the amplitude amplification.
The amplitude amplification is a procedure that increases the probability amplitude of the value to be searched and decreased the rest of the probability amplitudes
consider the below Kets (k1, k2, k3,…..kn) in a balanced superposition, we want to hunt kw so by performing amplitude amplification we and when the kets are sent for amplification process, the first oracle flips the kw ket upside down to negative phase from the probability of .0 to -.5 which separates it from other kets.
The second oracle inverts all the amplitude by calculating its mean i.e the average. This leads to a decrease in the amplitude A∉ kw. And increases the kw ket such that the kw becomes 1 and the rest of the kets becomes 0
At the final stage, the states from the second oracle are measured with encoded values relating to the item in the list. And it maps the resulting state back to the database. If the answer is incorrect the steps are repeated. the error probability is O(1/N).
Firstly, oracle is denoted as Uf and the second one as Uφ, which is Grover’s diffusion operator. These oracles are repeated √N times. If the matches are multiple m, then the oracles are repeated √(N/t) times. Grover search can also be used to search multiple elements.
The above figure is Grover’s algorithm circuit that follows the below algorithm.
Let’s take a quick look over Grover’s Quantum algorithm
The algorithm is summarized as follows:
Note: If you increase the iterations the performance decreases.
Grover’s algorithm has been outperforming the classical searching method by the quadratic acceleration. Quantum computers are embedded with the tendency to perform complex computations within an extremely short span, which will take years in comparison to classical computers.
These links helped me a lot in understanding the algorithm, do visit them too.