Editing Grover's algorithm (section)

{{Short description|Quantum search algorithm
}}
{{Use American English|date=January 2019}}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 <math>O(\sqrt{N})</math> evaluations of the function, where <math>N</math> is the size of the function's [[domain of a function|domain]]. It was devised by [[Lov Grover]] in 1996.<ref name="grover">{{Cite book|last=Grover|first=Lov K.|title=Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 |chapter=A fast quantum mechanical algorithm for database search |date=1996-07-01|chapter-url=https://doi.org/10.1145/237814.237866|location=Philadelphia, Pennsylvania, USA|publisher=Association for Computing Machinery|pages=212–219|doi=10.1145/237814.237866|arxiv=quant-ph/9605043|bibcode=1996quant.ph..5043G|isbn=978-0-89791-785-8|s2cid=207198067}}</ref>

The analogous problem in classical computation would have a [[query complexity]] <math>O(N)</math> (i.e., the function would have to be evaluated <math>O(N)</math> times: there is no better approach than trying out all input values one after the other, which, on average, takes <math>N/2</math> steps).<ref name="grover"/>

[[Charles H. Bennett (physicist)|Charles H. Bennett]], Ethan Bernstein, [[Gilles Brassard]], and [[Umesh Vazirani]] proved that any quantum solution to the problem needs to evaluate the function <math>\Omega(\sqrt{N})</math> times, so Grover's algorithm is [[Asymptotically optimal algorithm|asymptotically optimal]].<ref name=bennett_1997>{{cite journal
| title=The strengths and weaknesses of quantum computation
|last1=Bennett |first1=C. H. |last2=Bernstein |first2=E. |last3=Brassard |first3=G. |last4=Vazirani |first4=U. |s2cid=13403194 | journal=[[SIAM Journal on Computing]]
| date=1997
| volume=26 | issue=5
| pages=1510&ndash;1523
| url=http://www.cs.berkeley.edu/~vazirani/pubs/bbbv.ps | doi=10.1137/s0097539796300933|arxiv=quant-ph/9701001}}</ref> Since classical algorithms for [[NP-completeness|NP-complete problems]] 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 [[time complexity|polynomial-time]] solutions for NP-complete problems (as the square root of an exponential function is still an exponential, not a polynomial function).<ref name=Nielsen-Chuang>{{Cite book|last1=Nielsen|first1=Michael A.|first2=Isaac L. |last2=Chuang|url=https://www.worldcat.org/oclc/665137861|title=Quantum computation and quantum information|date=2010|publisher=Cambridge University Press|isbn=978-1-107-00217-3|location=Cambridge|oclc=665137861|pages=276–305}}</ref>

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 <math>N</math> is large, and Grover's algorithm can be applied to speed up broad classes of algorithms.<ref name=Nielsen-Chuang/> Grover's algorithm could [[brute-force attack|brute-force]] a 128-bit symmetric cryptographic key in roughly 2<sup>64</sup> iterations, or a 256-bit key in roughly 2<sup>128</sup> iterations. It may not be the case that Grover's algorithm poses a significantly increased risk to encryption over existing classical algorithms, however.<ref name="djb-groverr">{{cite conference
 | last = Bernstein | first = Daniel J. | author-link = Daniel J. Bernstein
 | editor-last = Sendrier | editor-first = Nicolas
 | contribution = Grover vs. McEliece
 | contribution-url = https://cr.yp.to/codes/grovercode-20100303.pdf
 | doi = 10.1007/978-3-642-12929-2_6
 | pages = 73–80
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Post-Quantum Cryptography, Third International Workshop, PQCrypto 2010, Darmstadt, Germany, May 25-28, 2010. Proceedings
 | volume = 6061
 | year = 2010}}</ref>