Grover's algorithm

Grover's algorithm, along with variants like amplitude amplification, can be used to speed up a broad range of algorithms.[5][6][7] In particular, algorithms for NP-complete problems generally contain exhaustive search as a subroutine, which can be sped up by Grover's algorithm.[6] The current best algorithm for 3SAT is one such example. Generic constraint satisfaction problems also see quadratic speedups with Grover.[8] 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.

Grover's algorithm can also give provable speedups for black-box problems in quantum query complexity, including element distinctness[9] and the collision problem[10] (solved with the 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.

As input for Grover's algorithm, suppose we have a function ${\displaystyle f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}}$. In the "unstructured database" analogy, the domain represent indices to a database, and 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 f(x) = 1, and we call this index ω. Our goal is to identify ω.

We can access f with a subroutine (sometimes called an oracle) in the form of a unitary operator U_ω that acts as follows:

${\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0.\end{cases}}}$

This uses the ${\displaystyle N}$-dimensional state space ${\displaystyle {\mathcal {H}}}$, which is supplied by a register with ${\displaystyle n=\lceil \log _{2}N\rceil }$ qubits. This is often written as

${\displaystyle U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle .}$

Grover's algorithm outputs ω with probability at least 1/2 using ${\displaystyle O({\sqrt {N}})}$ applications of U_ω. 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 number of applications is still ${\displaystyle O({\sqrt {N}})}$, since it will only be run twice on average.

Quantum circuit representation of Grover's algorithm

The steps of Grover's algorithm are given as follows:

1. Initialize the system to the uniform superposition over all states
   ${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$
2. Perform the following "Grover iteration" ${\displaystyle r(N)}$ times:
   1. Apply the operator ${\displaystyle U_{\omega }}$
   2. Apply the Grover diffusion operator ${\displaystyle U_{s}=2\left|s\right\rangle \left\langle s\right|-I}$
3. Measure the resulting quantum state in the computational basis.

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

Implementing the steps for this algorithm can be done using a number of gates linear in the number of qubits.[3] Thus, the gate complexity of this algorithm is ${\displaystyle O(\log(N)r(N))}$, or ${\displaystyle O(\log(N))}$ per iteration.

Picture showing the geometric interpretation of the first iteration of Grover's algorithm. The state vector ${\displaystyle |s\rangle }$ is rotated towards the target vector ${\displaystyle |\omega \rangle }$ 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 ${\displaystyle |s\rangle }$ and ${\displaystyle |\omega \rangle }$; equivalently, the plane spanned by ${\displaystyle |\omega \rangle }$ and the perpendicular ket ${\displaystyle \textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle }$.

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

${\displaystyle U_{\omega }=I-2|\omega \rangle \langle \omega |.}$

The operator ${\displaystyle U_{s}=2|s\rangle \langle s|-I}$ is a reflection through ${\displaystyle |s\rangle }$. Both operators ${\displaystyle U_{s}}$ and ${\displaystyle U_{\omega }}$ take states in the plane spanned by ${\displaystyle |s'\rangle }$ and ${\displaystyle |\omega \rangle }$ 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 ${\displaystyle U_{s}U_{\omega }}$ of each Grover iteration step rotates the state vector by an angle of ${\displaystyle \theta =2\arcsin {\tfrac {1}{\sqrt {N}}}}$. So, with enough iterations, one can rotate from the initial state ${\displaystyle |s\rangle }$ to the desired output state ${\displaystyle |\omega \rangle }$. The initial ket is close to the state orthogonal to ${\displaystyle |\omega \rangle }$:

${\displaystyle \langle s'|s\rangle ={\sqrt {\frac {N-1}{N}}}.}$

In geometric terms, the angle ${\displaystyle \theta /2}$ between ${\displaystyle |s\rangle }$ and ${\displaystyle |s'\rangle }$ is given by

${\displaystyle \sin {\frac {\theta }{2}}={\frac {1}{\sqrt {N}}}.}$

We need to stop when the state vector passes close to ${\displaystyle |\omega \rangle }$; after this, subsequent iterations rotate the state vector away from ${\displaystyle |\omega \rangle }$, reducing the probability of obtaining the correct answer. The exact probability of measuring the correct answer is

${\displaystyle \sin ^{2}\left({\Big (}r+{\frac {1}{2}}{\Big )}\theta \right),}$

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

To complete the algebraic analysis, we need to find out what happens when we repeatedly apply ${\displaystyle U_{s}U_{\omega }}$. 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 ${\displaystyle s}$ and ${\displaystyle \omega }$. We can write the action of ${\displaystyle U_{s}}$ and ${\displaystyle U_{\omega }}$ in the space spanned by ${\displaystyle \{|s\rangle ,|\omega \rangle \}}$ as:

${\displaystyle U_{s}:a|\omega \rangle +b|s\rangle \mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.}$

${\displaystyle U_{\omega }:a|\omega \rangle +b|s\rangle \mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.}$

So in the basis ${\displaystyle \{|\omega \rangle ,|s\rangle \}}$ (which is neither orthogonal nor a basis of the whole space) the action ${\displaystyle U_{s}U_{\omega }}$ of applying ${\displaystyle U_{\omega }}$ followed by ${\displaystyle U_{s}}$ is given by the matrix

${\displaystyle U_{s}U_{\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}}.}$

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

${\displaystyle U_{s}U_{\omega }=M{\begin{bmatrix}e^{2it}&0\\0&e^{-2it}\end{bmatrix}}M^{-1}}$ where ${\displaystyle M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.}$

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

${\displaystyle (U_{s}U_{\omega })^{r}=M{\begin{bmatrix}e^{2rit}&0\\0&e^{-2rit}\end{bmatrix}}M^{-1}.}$

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

${\displaystyle \left|{\begin{bmatrix}\langle \omega |\omega \rangle &\langle \omega |s\rangle \end{bmatrix}}(U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\right|^{2}=\sin ^{2}\left((2r+1)t\right).}$

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

${\displaystyle [|\omega \rangle \,|s\rangle ](U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\approx [|\omega \rangle \,|s\rangle ]M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}{\begin{bmatrix}0\\1\end{bmatrix}}=|\omega \rangle {\frac {1}{\cos(t)}}-|s\rangle {\frac {\sin(t)}{\cos(t)}}.}$

A short calculation now shows that the observation yields the correct answer ω with error ${\displaystyle O\left({\frac {1}{N}}\right)}$.

Grover's algorithm is optimal up to sub-constant factors. That is, any algorithm that accesses the database only by using the operator U_ω must apply U_ω at least a ${\displaystyle 1-o(1)}$ fraction as many times as Grover's algorithm.[21] The extension of Grover's algorithm to k matching entries, π(N/k)^1/2/4, is also optimal.[18] This result is important in understanding the limits of quantum computation.

If the Grover's search problem was solvable with log^c N applications of U_ω, that would imply that 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-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 quantum computers could implement a search of an ${\displaystyle N}$-item database in at most ${\displaystyle O({\sqrt[{3}]{N}})}$ steps. This is faster than the ${\displaystyle O({\sqrt {N}})}$ steps taken by Grover's algorithm.[22]

• Amplitude amplification
• Brassard–Høyer–Tapp algorithm (for solving the collision problem)
• Shor's algorithm (for factorization)
• Quantum walk search

• Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
• Grover L.K.: 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.: 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. 24–30.
• Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.
• What's a Quantum Phone Book?, Lov Grover, Lucent Technologies

Wikiquote has quotations related to Grover's algorithm.

• Davy Wybiral. "Quantum Circuit Simulator". Archived from the original on 2017-01-16. Retrieved 2017-01-13.
• Craig Gidney (2013-03-05). "Grover's Quantum Search Algorithm".
• François Schwarzentruber (2013-05-18). "Grover's algorithm".
• Alexander Prokopenya. "Quantum Circuit Implementing Grover's Search Algorithm". Wolfram Alpha.
• "Quantum computation, theory of", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Roberto Maestre (2018-05-11). "Grover's Algorithm implemented in R and C". GitHub.
• Bernhard Ömer. "QCL - A Programming Language for Quantum Computers". Retrieved 2022-04-30. Implemented in /qcl-0.6.4/lib/grover.qcl