Grover's algorithm

In <a href="/facts/Quantum_computing/nbbcgmvq">quantum computing</a>, Grover's algorithm, also known as the quantum search algorithm, is a <a href="/facts/Quantum_algorithm/ceJaJ6Eq">quantum algorithm</a> for unstructured search that finds <a href="/facts/With_high_probability/eBttFkd4">with high probability</a> the unique input to a <a href="/facts/Black_box/hJeAGnIz">black box</a> 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 <a href="/facts/Domain_of_a_function/FQvoeUpX">domain</a>. It was devised by <a href="/facts/Lov_Grover/lhxI0oHw">Lov Grover</a> in 1996.
The analogous problem in classical computation would have a <a href="/facts/Query_complexity/FalJqMSd">query complexity</a>[disambiguation needed] 
 
 
 
 O
 (
 N
 )
 
 
 {\displaystyle O(N)}
 
 (i.e., the function would have to be evaluated 
 
 
 
 O
 (
 N
 )
 
 
 {\displaystyle O(N)}
 
 times: there is no better approach than trying out all input values one after the other, which, on average, takes 
 
 
 
 N
 
 /
 
 2
 
 
 {\displaystyle N/2}
 
 steps).
<a href="/facts/Charles_H._Bennett_(physicist)/8IKbwhLJ">Charles H. Bennett</a>, Ethan Bernstein, <a href="/facts/Gilles_Brassard/sBxLIE3P">Gilles Brassard</a>, and <a href="/facts/Umesh_Vazirani/ej4NSg84">Umesh Vazirani</a> proved that any quantum solution to the problem needs to evaluate the function 
 
 
 
 Ω
 (
 
 
 N
 
 
 )
 
 
 {\displaystyle \Omega ({\sqrt {N}})}
 
 times, so Grover's algorithm is <a href="/facts/Asymptotically_optimal_algorithm/fnfvbMYE">asymptotically optimal</a>. Since classical algorithms for <a href="/facts/NP-completeness/NFPv56DU">NP-complete problems</a> require exponentially many steps, and Grover's algorithm provides at most a quadratic speedup over the classical solution for unstructured search, this suggests that Grover's algorithm by itself will not provide <a href="/facts/Time_complexity/77T62gmf">polynomial-time</a> solutions for NP-complete problems (as the square root of an exponential function is still an exponential, not a polynomial, function).
Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover's algorithm provides only a quadratic speedup. However, even quadratic speedup is considerable when 
 
 
 
 N
 
 
 {\displaystyle N}
 
 is large, and Grover's algorithm can be applied to speed up broad classes of algorithms. Grover's algorithm could <a href="/facts/Brute-force_attack/TXl8pkfb">brute-force</a> a 128-bit symmetric cryptographic key in roughly 264 iterations, or a 256-bit key in roughly 2128 iterations. It may not be the case that Grover's algorithm poses a significantly increased risk to encryption over existing classical algorithms, however.

Grover's algorithm open-in-new

Grover's algorithm