Grover’s algorithm : Searching Algorithm


Hey, Guys Learner is here with some facts of Grover’s algorithm.
As we all know future is Quantum Computing and Grover’s Algorithm is one of the important algorithms of Quantum Computing.
So..Let’s explore Grover’s Algorithm more….

What’s Grover’s Algorithm?

Grover’s algorithm is probabilistic, in the sense that it gives the correct answer with high probability. The probability of failure can be decreased by repeating the algorithm.
Grover’s algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just {\displaystyle O({\sqrt {N}})} O({\sqrt {N}}) evaluations of the function, where N is the size of the function’s domain. It was devised by Lov Grover in 1996.

I’m damn sure it will explains you in a better way.

See Animation
The analogous problem in classical computation cannot be solved in fewer than {\displaystyle O(N)} O(N) evaluations (because, in the worst case, the N-th member of the domain might be the correct member). At roughly the same time that Grover published his algorithm, Bennett, Bernstein, Brassard, and Vazirani proved that no quantum solution to the problem can evaluate the function fewer than {\displaystyle O({\sqrt {N}})} O({\sqrt {N}}) times, so Grover’s algorithm is asymptotically optimal.

What it solves?

It solves search in the unsorted database.

Steps of Grover’s Algorithm

The steps of Grover’s algorithm are as follows:

  1. Initialize the system to the state |s\ranglele = \frac{1}{\sqrt{N}} \sum_x |x\ranglele
  2. Perform the following “Grover iteration” r(N) times. The function r(N) is described below.
    1. Apply the operator Uω
    2. Apply the operator Us = 2∣sleles∣ − I.
  3. Perform the measurement Ω. The measurement result will be λω with probability approaching 1 for N>>1. From λω, ω may be obtained.

Uses of Grover’s Algorithm

Although the purpose of Grover’s algorithm is usually described as “searching a database”, it may be more accurate to describe it as “inverting a function”. Roughly speaking, if we have a function y=f(x) that can be evaluated on a quantum computer, Grover’s algorithm allows us to calculate x when given y. Inverting a function is related to the searching of a database because we could come up with a function that produces a particular value of y if x matches the desired entry in a database, and another value of y for other values of x.

Grover’s algorithm can also be used for estimating the mean and median of a set of numbers, and for solving the collision problem. In addition, it can be used to solve NP-complete problems by performing exhaustive searches over the set of possible solutions. This would result in a considerable speedup over classical solutions, even though it does not provide the “holy grail” of a polynomial-time solution.

Below, we present the basic form of Grover’s algorithm, which searches for a single matching entry. The algorithm can be further optimized if there is more than one matching entry and the number of matches is known beforehand.

Do you wanna know more?

Know more about Grover’s Algorithm

Wanna Contribute?

Contribute here
{Code with Codeater}

Leave a Reply