Grover's algorithm

Grover's algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just ON^1/2 evaluations of the function, where N is the size of the function's domain.

Quotes

• Quantum computational approaches improve upon classical methods for a number of specialized tasks. The extent of quantum computing’s applicability is still being determined. It does not provide efficient solutions to all problems; neither does it provide a universal way of circumventing the slowing of Moore’s law. Strong limitations on the power of quantum computation are known; for many problems, it has been proven that quantum computation provides no significant advantage over classical computation. Grover’s algorithm, the other major algorithm of the mid- 1990s, provides a small speedup for unstructured search algorithms. But it is also known that this small speedup is the most that quantum algorithms can attain. Grover’s search algorithm applies to unstructured search. For other search problems, such as searching an ordered list, quantum computation provides no significant advantage over classical computation. Simulation of quantum systems is the other significant application of quantum computation known in the mid-1990s. Of interest in its own right, the simulation of increasingly larger quantum systems may provide a bootstrap that will ultimately lead to the building of a scalable quantum computer.
  After Grover’s algorithm, there was a hiatus of more than five years before a significantly new algorithm was discovered. During that time, other areas of quantum information processing, such as quantum error correction, advanced significantly. In the early 2000s, several new algorithms were discovered. Like Shor’s algorithm, these algorithms solve specific problems with narrow, if important, applications. Novel approaches to constructing quantum algorithms also developed. Investigations of quantum simulation from a quantum-information-processing point of view have led to improved classical techniques for simulating quantum systems, as well as novel quantum approaches. Similarly, the quantum-information-processing point of view has led to novel insights into classical computing, including new classical algorithms. Furthermore, alternatives to the standard circuit model of quantum computation have been developed that have led to new quantum algorithms, breakthroughs in building quantum computers, new approaches to robustness, and significant insights into the key elements of quantum computation.
  • Eleanor Rieffel and Wolfgang Polak, Quantum Computing: A Gentle Introduction (2011), 1. Introduction