Editing Grover's algorithm (section)

== Applications and limitations ==
Grover's algorithm, along with variants like [[amplitude amplification]], can be used to speed up a broad range of algorithms.<ref>{{cite conference
 | last = Grover | first = Lov K.
 | editor-last = Vitter | editor-first = Jeffrey Scott
 | arxiv = quant-ph/9711043
 | contribution = A framework for fast quantum mechanical algorithms
 | doi = 10.1145/276698.276712
 | pages = 53–62
 | publisher = Association for Computing Machinery
 | title = Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23–26, 1998
 | year = 1998}}</ref><ref name=Ambaianis04>{{Cite journal|last=Ambainis|first=A.|date=2004-06-01|title=Quantum search algorithms|url=https://doi.org/10.1145/992287.992296|journal=ACM SIGACT News|volume=35|issue=2|pages=22–35|doi=10.1145/992287.992296|s2cid=11326499|issn=0163-5700|arxiv=quant-ph/0504012}}</ref><ref>{{Cite web|last=Jordan|first=Stephen|title=Quantum Algorithm Zoo|url=https://quantumalgorithmzoo.org|access-date=2021-04-21|website=quantumalgorithmzoo.org|language=en}}</ref> In particular, algorithms for NP-complete problems which contain exhaustive search as a subroutine can be sped up by Grover's algorithm.<ref name=Ambaianis04 /> The current theoretical best algorithm, in terms of worst-case complexity, for [[3SAT]] is one such example. Generic [[constraint satisfaction problem]]s also see quadratic speedups with Grover.<ref>{{Cite journal|last1=Cerf|first1=Nicolas J.|last2=Grover|first2=Lov K.|last3=Williams|first3=Colin P.|date=2000-05-01|title=Nested Quantum Search and NP-Hard Problems|url=https://doi.org/10.1007/s002000050134|journal=Applicable Algebra in Engineering, Communication and Computing|language=en|volume=10|issue=4|pages=311–338|doi=10.1007/s002000050134|s2cid=311132|issn=1432-0622}}</ref> These algorithms do not require that the input be given in the form of an oracle, since Grover's algorithm is being applied with an explicit function, e.g. the function checking that a set of bits satisfies a 3SAT instance. However, it is unclear whether Grover's algorithm could speed up best practical algorithms for these problems.

Grover's algorithm can also give provable speedups for black-box problems in [[Quantum complexity theory#Quantum query complexity|quantum query complexity]], including element distinctness<ref>{{Cite journal|last=Ambainis|first=Andris|date=2007-01-01|title=Quantum Walk Algorithm for Element Distinctness|url=https://epubs.siam.org/doi/10.1137/S0097539705447311|journal=SIAM Journal on Computing|volume=37|issue=1|pages=210–239|doi=10.1137/S0097539705447311|s2cid=6581885|issn=0097-5397|arxiv=quant-ph/0311001}}</ref> and the [[collision problem]]<ref>{{cite conference
 | last1 = Brassard | first1 = Gilles
 | last2 = Høyer | first2 = Peter
 | last3 = Tapp | first3 = Alain
 | editor1-last = Lucchesi | editor1-first = Claudio L.
 | editor2-last = Moura | editor2-first = Arnaldo V.
 | arxiv = quant-ph/9705002
 | contribution = Quantum Cryptanalysis of Hash and Claw-Free Functions
 | doi = 10.1007/BFb0054319
 | pages = 163–169
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings
 | volume = 1380
 | year = 1998}}</ref> (solved with the [[BHT algorithm|Brassard–Høyer–Tapp algorithm]]). In these types of problems, one treats the oracle function ''f'' as a database, and the goal is to use the quantum query to this function as few times as possible.

=== Cryptography ===
Grover's algorithm essentially solves the task of ''function inversion''. Roughly speaking, if we have a function <math>y = f(x)</math> that can be evaluated on a quantum computer, Grover's algorithm allows us to calculate <math>x</math> when given <math>y</math>. Consequently, Grover's algorithm gives broad asymptotic speed-ups to many kinds of [[brute-force attack]]s on [[symmetric-key algorithm|symmetric-key cryptography]], including [[collision attack]]s and [[pre-image attack]]s.<ref>{{Cite book|url=https://www.worldcat.org/oclc/318545517|title=Post-quantum cryptography|date=2009|publisher=Springer|others=Daniel J. Bernstein, Johannes Buchmann, Erik, Dipl.-Math Dahmén|isbn=978-3-540-88702-7|location=Berlin|oclc=318545517}}</ref> However, this may not necessarily be the most efficient algorithm since, for example, the [[Pollard's rho algorithm]] is able to find a collision in [[SHA-2]] more efficiently than Grover's algorithm.<ref>{{Cite journal|last=Bernstein|first=Daniel J.|date=2021-04-21|title=Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?|url=https://www.hyperelliptic.org/tanja/SHARCS/record2.pdf#page=113|journal=Conference Proceedings for Special-purpose Hardware for Attacking Cryptographic Systems (SHARCS '09)|volume=09|pages=105–117}}</ref>

=== Limitations ===
Grover's original paper described the algorithm as a database search algorithm, and this description is still common. The database in this analogy is a table of all of the function's outputs, indexed by the corresponding input. However, this database is not represented explicitly. Instead, an oracle is invoked to evaluate an item by its index. Reading a full database item by item and converting it into such a representation may take a lot longer than Grover's search. To account for such effects, Grover's algorithm can be viewed as solving an equation or [[constraint satisfaction problem|satisfying a constraint]]. In such applications, the oracle is a way to check the constraint and is not related to the search algorithm. This separation usually prevents algorithmic optimizations, whereas conventional search algorithms often rely on such optimizations and avoid exhaustive search.<ref name=Viamontes>{{Citation| author1=Viamontes G.F.| author2=Markov I.L.| author3=Hayes J.P.| s2cid=8929938| title=Is Quantum Search Practical?| journal= Computing in Science and Engineering| pages=62–70| volume=7| issue=3| year=2005| url=https://web.eecs.umich.edu/~imarkov/pubs/jour/cise05-grov.pdf| doi=10.1109/mcse.2005.53| arxiv=quant-ph/0405001| bibcode=2005CSE.....7c..62V}}</ref> Fortunately, fast Grover's oracle implementation is possible for many constraint satisfaction and optimization problems.<ref name=sinitsyn23>{{Cite journal| author1=Sinitsyn N. A.| author2=Yan B.| title=Topologically protected Grover's oracle for the partition problem| journal=Physical Review A|year=2023| volume=108| issue=2| page=022412| doi=10.1103/PhysRevA.108.022412|arxiv=2304.10488| s2cid=258236417}}</ref>

The major barrier to instantiating a speedup from Grover's algorithm is that the quadratic speedup achieved is too modest to overcome the large overhead of near-term quantum computers.<ref>{{Cite journal|last1=Babbush|first1=Ryan|last2=McClean|first2=Jarrod R.|last3=Newman|first3=Michael|last4=Gidney|first4=Craig|last5=Boixo|first5=Sergio|last6=Neven|first6=Hartmut|date=2021-03-29|title=Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage|journal=PRX Quantum|volume=2|issue=1|pages=010103|doi=10.1103/PRXQuantum.2.010103 | arxiv=2011.04149 |doi-access=free}}</ref> However, later generations of [[Quantum threshold theorem|fault-tolerant]] quantum computers with better hardware performance may be able to realize these speedups for practical instances of data.