CODEWITHSUNDEEP
pythonalgorithmquantum-computing
Qiasm
Qiasm

Reputation: 356

What is Grover's algorithm in a big simplification?

I'm new in quantum computing. I mean extremely new. I saw that there is some king of an algorithm called Grover's search algorithm. I have read that it searches through the database containing N-elements in order to find the specific element. I also read that standard computers would be doing it for many, many years while quantum computers would do it in just a few seconds. And that is what confuses me the most. How I understand this: Let's say we want to search the database containing 50.000 different names and we are looking for a name "Jack". The standard computer wouldn't do it for years right? I think there's matter of seconds or minutes as searching through the database containing names which is probably text won't take long...

Example in python:

names = ["Mark", "Bob", "Katty", "Susan", "Jack"]

for i in range(len(names)):
    if names[i] == "Jack":
        print("It's Jack!")
    else:
        print("It's not Jack :(")

That's how I understand it. So let's imagine this list contains 50.000 names and we want to search for "Jack". I guess it wouldn't take long.

So how does this Grover's algorithm works? I really can't figure it out.

Upvotes: 2

Views: 424

Answers (1)

Mariia Mykhailova
Mariia Mykhailova

Reputation: 2032

Grover's search is not indeed a good replacement for classical database lookup methods. (Note that classical databases will have classical indices in them that will speed up the lookup way beyond your implementation.) You can see this paper for a discussion of practical applications of Grover search.

It is more correct to think about the oracle as a tool to recognize the answer, not to find it. For example, if you're looking to solve a SAT problem, the oracle circuit will encode the Boolean formula for a specific instance of a problem you're trying to solve.

If you were to use Grover's algorithm for database search, the oracle would have to encode the condition you're searching for, but also the criteria of whether the element is in a database. For example, if you're looking for a name starting with A, the oracle needs to recognize all strings starting with A, but it also needs to recognize which of the strings are present in the database - otherwise the algorithm will yield a random string starting with A, which is probably not what you were looking for.

Grover's algorithm has practical application when generalized to amplitude amplification, which shows up as a component of many other quantum algorithms. Amplitude amplification is a way of improving the success likelihood of a probabilistic quantum algorithm.

Upvotes: 3

Related Questions