Editing Grover's algorithm

{{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>

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

== Problem description ==
As input for Grover's algorithm, suppose we have a function <math>f\colon \{0,1,\ldots,N-1\} \to \{0,1\}</math>. In the "unstructured database" analogy, the domain represent indices to a database, and {{nowrap|1=''f''(''x'') = 1}} if and only if the data that ''x'' points to satisfies the search criterion. We additionally assume that only one index satisfies {{nowrap|1=''f''(''x'') = 1}}, and we call this index ''ω''. Our goal is to identify ''ω''.

We can access ''f'' with a [[subroutine]] (sometimes called an [[Oracle machine|oracle]]) in the form of a [[unitary operator]] ''U<sub>ω</sub>'' that acts as follows:

<math display="block">\begin{cases}
 U_\omega |x\rang = -|x\rang & \text{for } x = \omega \text{, that is, } f(x) = 1, \\
 U_\omega |x\rang = |x\rang & \text{for } x \ne \omega \text{, that is, } f(x) = 0.
\end{cases}</math><!-- Explanation of bar/pipe notation required. -->

This uses the <math>N</math>-dimensional [[mathematical formulation of quantum mechanics|state space]] <math>\mathcal{H}</math>, which is supplied by a [[quantum register|register]] with <math>n = \lceil \log_{2} N \rceil</math> [[qubit]]s.
This is often written as

<math display="block">U_\omega|x\rang = (-1)^{f(x)}|x\rang.</math>

Grover's algorithm outputs ''ω'' with probability at least ''1/2'' using <math>O(\sqrt{N})</math> applications of ''U<sub>ω</sub>''. This probability can be made arbitrarily large by running Grover's algorithm multiple times. If one runs Grover's algorithm until ''ω'' is found, the [[Expected value|expected]] number of applications is still <math>O(\sqrt{N})</math>, since it will only be run twice on average.

=== Alternative oracle definition ===
This section compares the above oracle <math>U_\omega</math> with an oracle <math>U_f</math>.

''U<sub>ω</sub>'' is different from the standard [[Oracle machine|quantum oracle]] for a function ''f''. This standard oracle, denoted here as ''U<sub>f</sub>'', uses an [[ancilla bit|ancillary qubit]] system. The operation then represents an inversion ([[Quantum gate#Pauli X|NOT gate]]) on the main system conditioned by the value of ''f''(''x'') from the ancillary system:

<math display="block">\begin{cases}
 U_f |x\rang |y\rang = |x\rang |\neg y\rang & \text{for } x = \omega \text{, that is, } f(x) = 1, \\
 U_f |x\rang |y\rang = |x\rang |y\rang & \text{for } x \ne \omega \text{, that is, } f(x) = 0,
\end{cases}</math>

or briefly,

<math display="block">
U_f |x\rang |y\rang = |x\rang |y \oplus f(x)\rang.
</math>

These oracles are typically realized using [[uncomputation]].

If we are given ''U<sub>f</sub>'' as our oracle, then we can also implement ''U<sub>ω</sub>'', since ''U<sub>ω</sub>'' is ''U<sub>f</sub>'' when the ancillary qubit is in the state <math>|-\rang = \frac1{\sqrt2}\big(|0\rang - |1\rang\big) = H|1\rang</math>:

<math display="block">
\begin{align}
U_f \big( |x\rang \otimes |-\rang \big)
&= \frac1{\sqrt2} \left( U_f |x\rang |0\rang - U_f |x\rang |1\rang \right)\\
&= \frac1{\sqrt2} \left(|x\rang |0 \oplus f(x)\rang - |x\rang |1 \oplus f(x)\rang  \right)\\
&= \begin{cases}
 \frac1{\sqrt2} \left(-|x\rang |0\rang + |x\rang |1\rang\right) & \text{if } f(x) = 1, \\
 \frac1{\sqrt2} \left( |x\rang |0\rang - |x\rang |1\rang \right) & \text{if } f(x) = 0
\end{cases} \\
&= (U_\omega |x\rang) \otimes |-\rang
\end{align}
</math>

So, Grover's algorithm can be run regardless of which oracle is given.<ref name=Nielsen-Chuang/> If ''U<sub>f</sub>'' is given, then we must maintain an additional qubit in the state <math>|-\rang</math> and apply ''U<sub>f</sub>'' in place of ''U<sub>ω</sub>''.

== Algorithm ==
[[File:Grover's algorithm circuit.svg|500px|thumb|right|[[Quantum circuit]] representation of Grover's algorithm]]
The steps of Grover's algorithm are given as follows:
# Initialize the system to the uniform superposition over all states<br/><math>|s\rangle = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle. </math>
# Perform the following "Grover iteration" <math>r(N)</math> times:
## Apply the operator <math>U_\omega</math>
## Apply the ''Grover diffusion'' operator <math>U_s = 2 \left|s\right\rangle\!\! \left\langle s\right| - I</math>
# [[Measurement in quantum mechanics|Measure]] the resulting quantum state in the computational basis.

For the correctly chosen value of <math>r</math>, the output will be <math>|\omega\rang</math> with probability approaching 1 for ''N'' ≫ 1. Analysis shows that this eventual value for <math>r(N)</math> satisfies <math>r(N) \leq \Big\lceil\frac{\pi}{4}\sqrt{N}\Big\rceil</math>.

Implementing the steps for this algorithm can be done using a number of gates linear in the number of qubits.<ref name=Nielsen-Chuang/> Thus, the gate complexity of this algorithm is <math>O(\log(N)r(N))</math>, or <math>O(\log(N))</math> per iteration.

== Geometric proof of correctness==
[[File:Grovers algorithm geometry.png|thumb|upright=1.4|Picture showing the geometric interpretation of the first iteration of Grover's algorithm. The state vector <math>|s\rang</math> is rotated towards the target vector <math>|\omega\rang</math> as shown.]]
There is a geometric interpretation of Grover's algorithm, following from the observation that the quantum state of Grover's algorithm stays in a two-dimensional subspace after each step. Consider the plane spanned by <math>|s\rang</math> and <math>|\omega\rang</math>; equivalently, the plane spanned by <math>|\omega\rang</math> and the perpendicular [[Bra–ket notation|ket]] <math>\textstyle |s'\rang = \frac{1}{\sqrt{N - 1}}\sum_{x \neq \omega} |x\rang</math>.

Grover's algorithm begins with the initial ket <math>|s\rang</math>, which lies in the subspace. The operator <math>U_{\omega}</math> is a reflection at the hyperplane orthogonal to <math>|\omega\rang</math> for vectors in the plane spanned by <math>|s'\rang</math> and <math>|\omega\rang</math>, i.e. it acts as a reflection across <math>|s'\rang</math>. This can be seen by writing <math>U_\omega</math> in the form of a [[Householder transformation|Householder reflection]]:

<math display="block"> U_\omega = I - 2|\omega\rangle\langle \omega|.</math>

The operator <math> U_s = 2 |s\rangle \langle s| - I</math> is a reflection through <math>|s\rang</math>. Both operators <math>U_s</math> and <math>U_{\omega}</math> take states in the plane spanned by <math>|s'\rang</math> and <math>|\omega\rang</math> to states in the plane. Therefore, Grover's algorithm stays in this plane for the entire algorithm.

It is straightforward to check that the operator <math>U_s U_{\omega}</math> of each Grover iteration step rotates the state vector by an angle of <math>\theta = 2\arcsin\tfrac{1}{\sqrt{N}} </math>. So, with enough iterations, one can rotate from the initial state <math>|s\rang</math> to the desired output state <math>|\omega\rang</math>. The initial ket is close to the state orthogonal to <math>|\omega\rang</math>:

<math display="block"> \lang s'|s\rang = \sqrt{\frac{N-1}{N}}. </math>

In geometric terms, the angle <math>\theta/2</math> between <math>|s\rang</math> and <math>|s'\rang</math> is given by

<math display="block"> \sin \frac{\theta}{2} = \frac{1}{\sqrt{N}}. </math>

We need to stop when the state vector passes close to <math>|\omega\rang</math>; after this, subsequent iterations rotate the state vector ''away'' from <math>|\omega\rang</math>, reducing the probability of obtaining the correct answer. The exact probability of measuring the correct answer is

<math display="block"> \sin^2\left( \Big( r + \frac{1}{2} \Big)\theta\right),</math>

where ''r'' is the (integer) number of Grover iterations. The earliest time that we get a near-optimal measurement is therefore <math>r \approx \pi \sqrt{N} / 4</math>.

== Algebraic proof of correctness ==
To complete the algebraic analysis, we need to find out what happens when we repeatedly apply <math>U_s U_\omega</math>. A natural way to do this is by eigenvalue analysis of a matrix. Notice that during the entire computation, the state of the algorithm is a linear combination of <math>s</math> and <math>\omega</math>. We can write the action of <math>U_s</math> and <math>U_\omega</math> in the space spanned by <math>\{|s\rang, |\omega\rang\}</math> as:

<math>\begin{align}
U_s : a |\omega \rang + b |s \rang &\mapsto [|\omega \rang \, | s \rang] \begin{bmatrix}
-1 & 0 \\
2/\sqrt{N} & 1 \end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}. \\

U_\omega : a |\omega \rang + b |s \rang &\mapsto [|\omega \rang \, | s \rang] \begin{bmatrix}
-1 & -2/\sqrt{N} \\
0 & 1 \end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}.
\end{align}</math>

So in the basis <math>\{ |\omega\rang, |s\rang \}</math> (which is neither orthogonal nor a basis of the whole space) the action <math>U_sU_\omega</math> of applying <math>U_\omega</math> followed by <math>U_s</math> is given by the matrix

<math display="block"> U_sU_\omega = \begin{bmatrix} -1 & 0 \\ 2/\sqrt{N} & 1 \end{bmatrix}
\begin{bmatrix}
-1 & -2/\sqrt{N} \\
0 & 1 \end{bmatrix}
 = 
\begin{bmatrix}
1 & 2/\sqrt{N} \\
-2/\sqrt{N} & 1-4/N \end{bmatrix}.</math>

This matrix happens to have a very convenient [[Jordan form]]. If we define <math>t = \arcsin(1/\sqrt{N})</math>, it is

<math display="block"> U_sU_\omega = M \begin{bmatrix} e^{2it} & 0 \\ 0 & e^{-2it}\end{bmatrix} M^{-1}</math>

where <math>M = \begin{bmatrix}-i & i \\ e^{it} & e^{-it} \end{bmatrix}.</math>

It follows that ''r''-th power of the matrix (corresponding to ''r'' iterations) is 

<math display="block"> (U_sU_\omega)^r = M \begin{bmatrix} e^{2rit} & 0 \\ 0 & e^{-2rit}\end{bmatrix} M^{-1}.</math>

Using this form, we can use trigonometric identities to compute the probability of observing ''&omega;'' after ''r'' iterations mentioned in the previous section, 

<math display="block">\left|\begin{bmatrix}\lang\omega|\omega\rang & \lang\omega|s\rang\end{bmatrix}(U_sU_\omega)^r \begin{bmatrix}0 \\ 1\end{bmatrix} \right|^2 = \sin^2\left( (2r+1)t\right).</math>

Alternatively, one might reasonably imagine that a near-optimal time to distinguish would be when the angles 2''rt'' and −2''rt'' are as far apart as possible, which corresponds to <math>2rt \approx \pi/2</math>, or <math>r = \pi/4t = \pi/4\arcsin(1/\sqrt{N}) \approx \pi\sqrt{N}/4</math>. Then the system is in state

<math display="block"> [|\omega \rang \, | s \rang] (U_sU_\omega)^r \begin{bmatrix}0\\1\end{bmatrix} \approx [|\omega \rang \, | s \rang] M \begin{bmatrix} i & 0 \\ 0 & -i\end{bmatrix} M^{-1} \begin{bmatrix}0\\1\end{bmatrix} = | \omega \rang \frac{1}{\cos(t)} - |s \rang \frac{\sin(t)}{\cos(t)}.</math>

A short calculation now shows that the observation yields the correct answer ''&omega;'' with error <math>O\left (\frac{1}{N} \right)</math>.

== Extensions and variants ==

=== Multiple matching entries ===
{{Further|Amplitude amplification}}
If, instead of 1 matching entry, there are ''k'' matching entries, the same algorithm works, but the number of iterations must be <math display="inline"> \frac{\pi}{4}{\left( \frac{N}{k} \right)^{1/2}} </math>instead of <math display="inline"> \frac{\pi}{4}{N^{1/2}}.</math>

There are several ways to handle the case if ''k'' is unknown.<ref>{{Cite web|last=Aaronson|first=Scott|date=April 19, 2021|title=Introduction to Quantum Information Science Lecture Notes|url=https://www.scottaaronson.com/qclec.pdf}}</ref> A simple solution performs optimally up to a constant factor: run Grover's algorithm repeatedly for increasingly small values of ''k'', e.g., taking ''k'' = ''N'', ''N''/2, ''N''/4, ..., and so on, taking <math>k = N/2^t</math> for iteration ''t'' until a matching entry is found.

With sufficiently high probability, a marked entry will be found by iteration <math>t = \log_2(N/k) + c</math> for some constant ''c''. Thus, the total number of iterations taken is at most

<math display="block"> \frac{\pi}{4} \Big(1 + \sqrt{2} + \sqrt{4} + \cdots + \sqrt{\frac{N}{k2^c}}\Big) = O\big(\sqrt{N/k}\big). </math>

Another approach if ''k'' is unknown is to derive it via the [[quantum counting algorithm]] prior. 

If <math>k = N/2</math> (or the traditional one marked state Grover's Algorithm if run with <math>N = 2</math>), the algorithm will provide no amplification. If <math>k > N/2</math>, increasing ''k'' will begin to increase the number of iterations necessary to obtain a solution.<ref>Nielsen-Chuang</ref> On the other hand, if <math>k \geq N/2</math>, a classical running of the checking oracle on a single random choice of input will more likely than not give a correct solution.

A version of this algorithm is used in order to solve the [[collision problem]].<ref name=Boyer>{{Citation
| first1=Michel |last1=Boyer
| first2=Gilles |last2=Brassard
| first3=Peter |last3=Høyer
| first4=Alain |last4=Tapp
| title=Tight Bounds on Quantum Searching
| journal=Fortschritte der Physik
| volume=46
| pages=493–506
| year=1998
| issue=4–5
| arxiv=quant-ph/9605034
| bibcode = 1998ForPh..46..493B
| doi=10.1002/3527603093.ch10| isbn=9783527603091
}}</ref><ref>{{Citation
| first=Andris |last=Ambainis
| s2cid=11326499
| title=Quantum search algorithms
| journal=SIGACT News
| volume=35
| number=2
| pages=22–35
| year=2004
| arxiv=quant-ph/0504012
| bibcode = 2005quant.ph..4012A|doi=10.1145/992287.992296}}
</ref>

===Quantum partial search===
A  modification of Grover's algorithm called quantum partial search was described by Grover and Radhakrishnan in 2004.<ref>{{cite arXiv
| eprint=quant-ph/0407122v4
| title=Is partial quantum search of a database any easier?
|first1=L. K. |last1=Grover |first2=J. |last2=Radhakrishnan | date=2005-02-07
}}</ref> In partial search, one is not interested in finding the exact address of the target item, only the first few digits of the address. Equivalently, we can think of "chunking" the search space into blocks, and then asking "in which block is the target item?". In many applications, such a search yields enough information if the target address contains the information wanted. For instance, to use the example given by L. K. Grover, if one has a list of students organized by class rank, we may only be interested in whether a student is in the lower 25%, 25–50%, 50–75% or 75–100% percentile.

To describe partial search, we consider a database separated into <math>K</math> blocks, each of size <math>b = N/K</math>. The partial search problem is easier. Consider the approach we would take classically – we pick one block at random, and then perform a normal search through the rest of the blocks (in set theory language, the complement). If we do not find the target, then we know it is in the block we did not search. The average number of iterations drops from <math>N/2</math> to <math>(N-b)/2</math>.

Grover's algorithm requires <math display="inline">\frac{\pi}{4}\sqrt{N}</math> iterations. Partial search will be faster by a numerical factor that depends on the number of blocks <math>K</math>. Partial search uses <math>n_1</math> global iterations and <math>n_2</math> local iterations. The global Grover operator is designated <math>G_1</math> and the local Grover operator is designated <math>G_2</math>.

The global Grover operator acts on the blocks. Essentially, it is given as follows:
#Perform <math>j_1</math> standard Grover iterations on the entire database.
#Perform <math>j_2</math> local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block.
#Perform one standard Grover iteration.

The optimal values of <math>j_1</math> and <math>j_2</math> are discussed in the paper by Grover and Radhakrishnan. One might also wonder what happens if one applies successive partial searches at different levels of "resolution". This idea was studied in detail by [[Vladimir Korepin]] and Xu, who called it binary quantum search. They proved that it is not in fact any faster than performing a single partial search.

==Optimality ==
Grover's algorithm is optimal up to sub-constant factors. That is, any algorithm that accesses the database only by using the operator ''U<sub>ω</sub>'' must apply ''U<sub>ω</sub>'' at least a <math>1-o(1)</math> fraction as many times as Grover's algorithm.<ref>{{Cite journal|last=Zalka|first=Christof|date=1999-10-01|title=Grover's quantum searching algorithm is optimal|url=https://link.aps.org/doi/10.1103/PhysRevA.60.2746|journal=Physical Review A|volume=60|issue=4|pages=2746–2751|doi=10.1103/PhysRevA.60.2746|arxiv=quant-ph/9711070|bibcode=1999PhRvA..60.2746Z|s2cid=1542077}}</ref> The extension of Grover's algorithm to ''k'' matching entries, {{pi}}(''N''/''k'')<sup>1/2</sup>/4, is also optimal.<ref name=Boyer /> This result is important in understanding the limits of quantum computation.

If the Grover's search problem was solvable with {{math|log<sup>c</sup>}} ''N'' applications of ''U<sub>ω</sub>'', that would imply that [[NP (complexity class)|NP]] is contained in [[BQP]], by transforming problems in NP into Grover-type search problems. The optimality of Grover's algorithm suggests that quantum computers cannot solve [[NP-completeness|NP-Complete]] problems in polynomial time, and thus NP is not contained in BQP.

It has been shown that a class of non-local [[Hidden-variable theory|hidden variable]] quantum computers could implement a search of an <math>N</math>-item database in at most <math>O(\sqrt[3]{N})</math> steps. This is faster than the <math>O(\sqrt{N})</math> steps taken by Grover's algorithm.<ref>{{Cite web|url=http://www.scottaaronson.com/papers/qchvpra.pdf|title=Quantum Computing and Hidden Variables|last=Aaronson|first=Scott}}</ref>

==See also==
* [[Amplitude amplification]]
* [[BHT algorithm|Brassard–Høyer–Tapp algorithm]] (for solving the [[collision problem]])
* [[Shor's algorithm]] (for factorization)
* [[Quantum walk search]]

==Notes==
<references/>

== References ==
* Grover L.K.: ''[https://arxiv.org/abs/quant-ph/9605043 A fast quantum mechanical algorithm for database search]'', Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p.&nbsp;212
* Grover L.K.: ''[https://arxiv.org/abs/quant-ph/0109116 From Schrödinger's equation to quantum search algorithm]'', American Journal of Physics, 69(7): 769–777, 2001. Pedagogical review of the algorithm and its history.
* Grover L.K.: [https://cryptome.org/qc-grover.htm QUANTUM COMPUTING: How the weird logic of the subatomic world could make it possible for machines to calculate millions of times faster than they do today] ''The Sciences'', July/August 1999, pp.&nbsp;24–30.
* Nielsen, M.A. and Chuang, I.L. ''Quantum computation and quantum information''. Cambridge University Press, 2000. Chapter 6.
* [https://web.archive.org/web/20140201230754/http://www.bell-labs.com/user/feature/archives/lkgrover/ What's a Quantum Phone Book?], Lov Grover, Lucent Technologies

==External links==
{{Wikiquote}}
* {{cite web
 |url          = http://davy.wtf/quantum/?example=Grover%27s%20Algorithm
 |title        = Quantum Circuit Simulator
 |author       = Davy Wybiral
 |access-date  = 2017-01-13
 |archive-url  = https://web.archive.org/web/20170116155032/http://davy.wtf/quantum/?example=Grover%27s%20Algorithm
 |archive-date = 2017-01-16
 |url-status     = dead
}}
* {{cite web
| url=http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm
| title=Grover's Quantum Search Algorithm
| author=Craig Gidney
| date=2013-03-05
| access-date=2013-03-08
| archive-date=2020-11-17
| archive-url=https://web.archive.org/web/20201117095032/http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm
| url-status=dead
}}
* {{cite web
| url=http://people.irisa.fr/Francois.Schwarzentruber/mit1_algo2_2013/grover_s_algorithm/
| title=Grover's algorithm
| author=François Schwarzentruber
| date=2013-05-18}}
* {{cite web
| url=http://demonstrations.wolfram.com/QuantumCircuitImplementingGroversSearchAlgorithm/
| title=Quantum Circuit Implementing Grover's Search Algorithm
| author=Alexander Prokopenya
| publisher=[[Wolfram Alpha]]}}
* {{springer|title=Quantum computation, theory of|id=p/q130020}}
* {{cite web
| url=https://github.com/rmaestre/quantumSystem
| title=Grover's Algorithm implemented in R and C
| author=Roberto Maestre
| website=[[GitHub]]
| date=2018-05-11}}
* {{cite web
| url=http://tph.tuwien.ac.at/~oemer/qcl.html
| title=QCL - A Programming Language for Quantum Computers
| author=Bernhard Ömer
| quote=Implemented in /qcl-0.6.4/lib/grover.qcl
| access-date=2022-04-30}}

{{Quantum computing}}

{{DEFAULTSORT:Grover's Algorithm}}
[[Category:Quantum algorithms]]
[[Category:Search algorithms]]
[[Category:Post-quantum cryptography]]