What is Grover’s Search Algorithm and why will you use it?
Imagine if you come back from a journey with all your luggage locked.
Unfortunately, you lost your keys, and you should find their copy out of 100 of them saved into a box.
That activity would require hours and would be boring to do.
Imagine if you don’t remember a sentence saved in a file and don’t remember anything else about it. The only solution to find the sentence would be to open all your computer files (imagine how many notes, pdfs and powerpoints you have to open.
Even if it may seem something funny, it’s in reality how computers work. In general, you can’t notice that file classification and the speed of modern computers make anything easier.
With Classical Computers, search algorithms, statistically speaking, need N/2 trials to find a solution out of N possibilities. Potentially, they could reach N times as if I have to try all the keys before finding the right one to open the luggage.
Whatever is N or N/2, the order of the search space is N. In mathematics, we define this structure as O(N).
Quantum computers it’s something completely different. It turns out that you can use a quantum computer to solve the search problem after examining the search space about π √N/4 times. In that case, we can define it as O(√N)
You may think as if it’s not such a huge difference, 4 and √4 aren’t so different, after all. However, when numbers become bigger, the difference becomes more visible
In other words, the more a problem grows, the more the algorithm becomes essential.
When we talk about Search Algorithm, you may think that they aren’t necessary after all. Who cares how to open suitcases! Let’s imagine the best way to reduce the energy state of a protein. What algorithm would you use? Wouldn’t Grover’s Algorithm be important?
When you start from easy examples, you can reach more complex ones.
What’s Grover’s Algorithm?
Grover’s algorithm or quantum search algorithm refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just O(√N) evaluations of the function, where N is the size of the function’s domain. Lov Grover defined it in 1996.
How does the algorithm work?
Imagine finding a solution to a list of items you don’t know anything about. If you want to evaluate any of them, the superposition would collapse, and your algorithm would be inefficient.
That doesn’t happen with a procedure called amplitude amplification, which is how a quantum computer significantly enhances its probabilities. This procedure stretches out (amplifies) the amplitude of the marked item, decreasing other items’ amplitude.
After that, measuring the final state will return the correct solution with near-certainty.
We can consider different steps
Step 1: The amplitude amplification procedure starts in the uniform superposition |s⟩. In that case, we need to be sure that we have the same probability amplitude.
Step 2: Apply the oracle reflection UfUf to the state |s⟩.
In other words, it marks the target element by opposing its sign (you can think of it as if it’s flipped from the graph). In mathematical terms, it multiplies the equation for −1
Step 3: Apply an additional reflection. That makes the market target have the highest probability.
Step 4: Define if the solution is part of the results; otherwise, go to step 2 to repeat the application until about √N times.
Implementing the algorithm using Qiskit!
2 Qubits
To implement the algorithm, we need one rotation
3 Qubits
Curious Applications
Here you can find some applications that start from being solutions for some games but can be useful to solve the world biggest problems
Travelling salesman problem
The Travelling Salesman Problem describes a salesman who must travel between N cities. The order in which he does so is something he does not care about, as long as he visits each once during his trip and finishes where he was at first. Each city is connected to another close by towns, nodes, aeroplanes, or roads or railway.
The idea is to find the fastest, cheapest and less expensive way to reach those cities.
The Traveling Salesman Problem is typical of a large “hard” optimisation class defined in the 1800s based on finding a Hamiltonian cycle.
A Hamiltonian path is a path in a graph that contains each vertex of the graph exactly once. A Hamiltonian cycle is a Hamiltonian path, which is also a cycle.
Collision problem
Imagine if you have two elements and you only have the value for one of those. The 2 values are equal with two functions you don’t know anything about. How would you evaluate the second one?
That problem is complex and challenging to understand. Indeed, it’s present in some applications, such as cryptography.
In quantum computing, the Brasard-Hoyer-Tappar algorithm or BHT algorithm is a quantum algorithm that solves the collision problem.
The algorithm was discovered by Gilles Brassard, Peter Hoyer, and Alain Tapp in 1997. They used Grover’s algorithm, discovered the previous year.
Graph colouring
The idea is to visualise a graph with 3 different colours and an arbitrary number of vertices connected by edges) the goal is to find an assignment of colours to all vertices.
We can extract that knowledge to optimise connections between places (if we don’t think about colours anymore).
Conclusions
In this article, we defined Grover’s Algorithm, how to use it and how it works. Currently, People don’t use Grover’s Algorithm on a daily basis. That’s because Quantum Computers are basically recent to compete with Classical Computers. However, when Quantum Computers improve their performances, Grover’s Algorithm will be one of the most exciting applications for that scope.
