Grover's algorithm, also known as the quantum search algorithm, is 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. It was devised by the Indian-American computer scientist Lov Grover in 1996 and needs only quadratically fewer evaluations of the function than any classical search algorithm requires, making it one of the best known examples of a proven quantum speedup for a general search problem.
Facts
Time Complexity
Time Complexity (category)Sub-Linear / Root Time -- O(sqrt n) 1 Connections
Credited To
Source Grover's Algorithm (Wikipedia)
In Field
Source Grover's Algorithm (Wikipedia)
Invented By
Lov Grover published his quantum search algorithm in 1996, offering a quadratic speedup for unstructured search.
Sources
1. Grover's Algorithm (Wikipedia)
Wikipedia infobox: time complexity sub-linear-root
sub-linear-root
In Group: Sequential and Unstructured Search Algorithms, Introduction
In quantum computing, Grover's algorithm, also known as the quantum search algorithm, is 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 ) {\displaystyle O({\sqrt {N}})} evaluations of the function, where N {\displaystyle N} is the size of the function's domain.
Credited To: Lov Grover, Lead paragraph
It was devised by an Indian-American computer scientist Lov Grover in 1996.
- In Field: Quantum Computing, Lead paragraph
View the SourceWikidata: Grover's Algorithm
Wikidata Q1028292, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.