Editing Grover's algorithm (section)

=== 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.