Definition: Grover's algorithm is a very fast quantum search algorithm. The algorithm provides a quadratic speedup for unstructured searches, unlike other classical algorithms. It is used for searching an unsorted database. It finds with high probability the unique input to a black box function that produces a particular output value, using only O√N evaluations of the function, where N is the size of the function's domain.
Grover’s Algorithm explained
One of the many advantages a quantum computer has over a classical computer is its superior speed when searching databases. Grover's algorithm exemplifies this ability.
Lov Grover, an Indian-American computer scientist, published a paper in 1996 that brought him fame in Quantum Computing. In his research, he had worked on optimizing unstructured search problems.
Grover suggests implementing a trick in quantum known as Amplitude Amplification to significantly decrease the amount of time it would take to find out winner w from an unstructured database. Grover had few inspirations while writing his paper. According to Grover, quantum systems "move" towards points with low potential. The system searches for the point with the lowest potential so that the state accumulates more probability amplitude.
Secondly, he had used Schrodinger's equation (which predicts the future behaviour of a dynamic system. The equation is based on the wavefunction, and it predicts events or outcomes analytically and precisely). In addition to this, he finds unitary versions of his discretised evolution matrices. A phase selection and subsequent diffusion of an initial or trial quantum state are the two essential elements of Grover's algorithm. Grover uses the metrics based marked state of Markovian nature but not unitary (A Markov Matrix, also known as a stochastic matrix, is used to represent steps in a Markov chain. Each input of the Markov matrix represents the probability of an outcome).
According to Grover, a search operation can be presented by using a function f(x) that works on item x, if it solves the search as a successful one then f(x)=1. If the item x is not found then f(x)=0 . The quantum computing can be used to solve the unstructured search problem in O√N which is very efficient as compared to classical search algorithms.
A simplified example of Grover's algorithm:
Let's supposeyou want to find a certain key out of N Keys laying randomly in a box.
To find the specific key you are looking for, you will need to search the box on average N/2 times, in the worst case N times. Using quantum technology, you can speed up this process to √N times.
In a box of 100 keys, this would mean trying 10 keys instead of 50-100 keys.
Another advantage of Grover’s algorithm is that it works on only O(√N log N) gates. Grover uses the concept of Oracle which is like a black box operation taking n bit binary input and generating m bits. Likewise its diffusion operators gives an inversion about the mean so that the infinitely scaled small steps become measurable.
Applications of Grover’s Algorithm
Grover’s algorithm can solve problems related to eliminating mean and median for a collection of numbers. It can also resolve collision problems:
- It can solve NP complete problems using exhaustive search to find possible solutions
- The algorithm helps speed-up unstructured search problems in quadratic order runtime for a variety of other algorithms.
- It uses phase interference and superposition in addition to amplitude amplification to locate the element to be searched.
Utimaco provides quantum-resistant solutions that enable businesses to defend their systems against assaults based on quantum computers and the execution of Grover’s algorithm for finding cryptographic keys. Our significant time and talent investments in post-quantum cryptography resulted in NIST and BSI approved PQC algorithms which can be implemented already today in our cybersecurity solutions.
