Grover's Algorithm, named after computer scientist Lov Grover, is a quantum algorithm designed to search an unsorted database or solve the pre-image of a function. Unlike classical search algorithms, which require linear time to search through a database, Grover's Algorithm offers a quadratic speedup, making it one of the most well-known algorithms in quantum computing.
The problem Grover's Algorithm addresses is the unstructured search problem: finding a specific item in an unsorted database of (N) items. Classically, this requires O(N) queries on average, but Grover's Algorithm can find the target item with only O(sqrt{N) queries. This quadratic speedup is significant and represents the optimal bound for quantum search algorithms.
The core technique used in Grover's Algorithm is quantum amplitude amplification. The algorithm iteratively applies a specific sequence of quantum gates to amplify the probability amplitude of the target state (the item being searched for) while suppressing the amplitudes of other states. After a sufficient number of iterations, a measurement will likely yield the target state.
Grover's Algorithm has applications beyond simple search, including solving NP-complete problems, combinatorial optimization, and more. Variants of the algorithm have been developed to handle different types of search problems and constraints, expanding its applicability and efficiency in various contexts.
Implementing Grover's Algorithm on current quantum computers is an area of active research and experimentation. While the quadratic speedup is not as dramatic as the exponential speedup offered by some other quantum algorithms (such as Shor’s Algorithm), Grover's Algorithm still provides a compelling demonstration of quantum advantage and has inspired further exploration of quantum algorithms.
It's worth noting that Grover's Algorithm requires full knowledge of the function defining the search problem, and the quadratic speedup assumes that the database is unstructured. In cases where additional information about the structure of the problem is available, classical algorithms might perform comparably or even better.
Grover's Algorithm is a foundational result in quantum computing, showcasing the potential of quantum algorithms to outperform classical methods in specific tasks. Its discovery has contributed to the understanding of quantum computation's capabilities and limitations and continues to influence the development of new quantum algorithms and applications.
It is important to note that the term “database” used in conjunction with this algorithm does not refer to a software database as it is commonly referred to in computer science. Nor does it refer to a spreadsheet used as a database, a CSV file, or any other external file. It can refer to classical data that is mapped as quantum information, but it still won’t resemble anything a computer scientist or data scientist might recognize. The same caveats are required for the terms “query” and “oracle.”
Another way of thinking about Grover’s search algorithm is that it finds the inputs to a function for which the output is already known. For example, consider the equation 1 + 3 = X. Normally, we start with the inputs and the function. In this case, we have two inputs, the integers one and three, and the function is addition. We want to know the sum of our inputs. With Grover’s algorithm, we may start with X + Y = 4. We want to know the integers that we can add together in order to get the desired output, in this case four. Note that X and Y can have multiple values.
Some important facts to keep in mind when considering the use of Grover’s algorithm include:
It is important to note that the proposed speedup of Grover’s algorithm refers to its complexity, not to its runtime. The downgrading of the maximum speedup from quadratic to quartic is indicative of how fewer steps are required to find solutions, but additional steps are required to suppress, detect, and correct errors. To determine the true usefulness of this algorithm for real-world applications, therefore, the reduction in complexity must be balanced against the faster execution of classical processors. Consequently, as is the case with all quantum algorithms, the realization of computational advantages is likely to be found with very large problems.
For a more detailed analysis of the algorithm, a Medium article titled “Grover’s Algorithm — Quantum Computing” by Andre Ye delves into the task, oracles, amplitude amplification, and the process. Visualizations of the process are provided, as well as a two-qubit example. Although this article includes quantum circuits using a quantum computing framework, no code is provided.
For even more details, a GeeksforGeeks article titled “Introduction to Grover’s Algorithm” provides a mathematical overview, a proof of correctness, as well as pseudocode. Unlike the Medium article referenced above, this article includes Python code. However, the framework used in these two articles is not the only quantum computing framework. One alternative framework provides its own Python code on its “Grover’s Algorithm” page.
Grover's algorithm applications are diverse, but it’s possible to simplify a list with high-level classifications. The starting entry always has to be unstructured search, as that is how this algorithm is defined. These particular applications should be NP problems, otherwise they can efficiently be solved classically. Additional proposed applications, whether they have proven speedups or not, include:
The GeeksforGeeks article mentions a few additional applications, however the one that stands out is cryptography. Indeed, Grover’s algorithm can be used to factor numbers, and thus break cryptographic keys, however its speedup is only quartic with error correction, whereas Shor’s speedup is exponential. The lesson learned for all these proposed applications, except unstructured search, is to always verify that Grover’s isn’t just any solution to a problem, but that it is the optimal solution.
As noted with pattern recognition, modifications of the algorithm are sometimes proposed. Introducing a different encoding is just one of these types of proposed modifications.
Grover's search algorithm has several challenges and limitations, some of which have already been mentioned. A consolidated list includes, but is not limited to:
While Grover’s algorithm has only a quadratic speedup, which is slowed to a quartic speedup with error correction, it must be remembered that the result will always include all possible solutions. If X + Y = 4, for example, the results should show 0-4, 1-3, 2-2, 3-1, and 4-0. And this is only for a trivial problem that you would not actually run on a quantum computer. Now imagine a classically-hard problem with multiple solutions, and all those solutions are found with one run of the algorithm. The chapter on Grover’s algorithm is one of the longest chapters in the book, and it’s still being written.
Finally, Grover’s algorithm has a lesser-known cryptographic function involving hash functions. In principle, it can determine all the inputs, or keys, that could convert into the target hash value. So, while Shor’s factoring algorithm gets notoriety for threatening public encryption schemes, Grover’s algorithm threatens the way passwords and other sensitive information gets stored. However, one reason why this might be mentioned infrequently is that the simple defense to it is to use longer hash functions. To learn more about this, it’s commonly referenced in relation to blockch