Grover’s algorithm

Grover algorithm used in quantum computing to search an unordered sequence of data and with an additional need for storage space. It was invented by Lov K. Grover in 1996 .

If we had to search within a million boxes to find a ball, we would need with a classic computer to look at 500,000 boxes, while with a quantum computer we could find the ball just by looking at 1,000 boxes, through a trick known as Grover’s algorithm.

Operating principle

When looking for data and having a disordered sequence, a linear inspection must be performed, which takes time, so the Grover algorithm is a rather substantial improvement since it avoids the need for prior sorting. The gain obtained is from the square root, which contrasts with other improvements of the quantum algorithms that obtain improvements of exponential order over their classical counterparts.

It is probabilistic in nature, so it produces the correct answer with a certain probability of error, however, it can be obtained as low as desired by means of iterations.

 

Purpose

Searching in a sequence could be described more appropriately as a function: y = f (x), which can be evaluated in a quantum computer, this algorithm allows us to calculate the value of x when given as input the value of y.

This Grover algorithm is also used to calculate the mean and median of a data set.

 

Leave a Comment