*Sed ut perspiciatis unde omnis iste natus error sit voluptatem accusantium
Grover’s search algorithm | simplified
June 11, 2021
In this blog, I’ll try to make you understand how exactly Grover’s search algorithm works and how it differs from the classical computing algorithms with much simplicity
Quantum computing
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.
Introduction
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.
Algorithm
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).
- Here you can assume oracle and diffuser simply two black boxes that perform certain operations on the qubits.
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:
- Pick a random value you wanna search from the qubits.
- Put all the qubits to superposition by passing it to Hadamard gate H.
- Construct oracle f that flips the amplitude of the object to be searched.
- Construct the Diffuser that inverts around the mean.
- Repeat the oracle √N times for a single target and √(N/t) for multiple targets.
- And finally, validate the states with the values in the database.
- And take a sip of coffee. you’re done.
- Superposition is the ability of a quantum system to be in multiple states at the same time
Note: If you increase the iterations the performance decreases.
Facts
- Quantum circuits are sensitive to electromagnetic fields, collisions, air molecules, and heat that causes a qubit to lose its quantum properties
- Quantum computers are kept in extremely cold environments, as sub-atomic particles must be as close as possible to a stationary state.
Conclusion
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.
References
These links helped me a lot in understanding the algorithm, do visit them too.
Share :