Editing Quantum algorithm (section)

==Algorithms based on amplitude amplification==
[[Amplitude amplification]] is a technique that allows the amplification of a chosen subspace of a quantum state. Applications of amplitude amplification usually lead to quadratic speedups over the corresponding classical algorithms. It can be considered as a generalization of Grover's algorithm.{{citation needed|date=February 2024}}

===Grover's algorithm===
{{main|Grover's algorithm}}

Grover's algorithm searches an unstructured database (or an unordered list) with N entries for a marked entry, using only <math>O(\sqrt{N})</math> queries instead of the <math>O({N})</math> queries required classically.<ref>
{{Cite arXiv|eprint=quant-ph/9605043|first=Lov K.|last=Grover|author-link=Lov Grover|title=A fast quantum mechanical algorithm for database search|date=1996}}</ref> Classically, <math>O({N})</math> queries are required even allowing bounded-error probabilistic algorithms.

Theorists have considered a hypothetical generalization of a standard quantum computer that could access the histories of the hidden variables in [[De Broglie–Bohm theory|Bohmian mechanics]]. (Such a computer is completely hypothetical and would ''not'' be a standard quantum computer, or even possible under the standard theory of quantum mechanics.) Such a hypothetical computer could implement a search of an N-item database in at most <math>O(\sqrt[3]{N})</math> steps. This is slightly faster than the <math>O(\sqrt{N})</math> steps taken by Grover's algorithm. However, neither search method would allow either model of quantum computer to solve [[NP-completeness|NP-complete]] problems in polynomial time.<ref>{{Cite web|url=https://www.scottaaronson.com/papers/qchvpra.pdf|title=Quantum Computing and Hidden Variables|last=Aaronson|first=Scott}}</ref>

===Quantum counting===
[[Quantum counting]] solves a generalization of the search problem. It solves the problem of counting the number of marked entries in an unordered list, instead of just detecting whether one exists. Specifically, it counts the number of marked entries in an <math>N</math>-element list with an error of at most <math>\varepsilon</math> by making only <math>\Theta\left(\varepsilon^{-1} \sqrt{N/k}\right)</math> queries, where <math>k</math> is the number of marked elements in the list.<ref>
{{Cite book
 |last1 = Brassard |first1 = G.
 |last2=Hoyer |first2=P.
 |last3=Tapp |first3=A.
 |chapter = Quantum counting
 |date = 1998
 |title = Automata, Languages and Programming
 |arxiv = quant-ph/9805082
 |doi=10.1007/BFb0055105
 |volume = 1443
 |pages=820–831
|series = Lecture Notes in Computer Science
 |isbn = 978-3-540-64781-2
 |s2cid = 14147978
 }}</ref><ref>
{{Cite book
 |last1=Brassard |first1=G.
 |last2=Hoyer |first2=P.
 |last3=Mosca |first3=M.
 |last4=Tapp |first4=A.
 |year=2002
 |chapter=Quantum Amplitude Amplification and Estimation
 |title=Quantum Computation and Quantum Information
 |editor=Samuel J. Lomonaco, Jr.
 |series=AMS Contemporary Mathematics
 |volume=305
 |pages=53–74
 |doi=10.1090/conm/305/05215
 |arxiv=quant-ph/0005055
|bibcode=2000quant.ph..5055B|isbn=9780821821404
 |s2cid=54753
 }}</ref> More precisely, the algorithm outputs an estimate <math>k'</math> for <math>k</math>, the number of marked entries, with accuracy <math>|k-k'| \leq \varepsilon k</math>.