Grover's algorithm

src: i.ytimg.com

Grover's algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just ${\displaystyle O({\sqrt {N}})}$ evaluations of the function, where N is the size of the function's domain. It was devised by Lov Grover in 1996.

The analogous problem in classical computation cannot be solved in fewer than ${\displaystyle O(N)}$ evaluations (because, in the worst case, the N-th member of the domain might be the correct member). At roughly the same time that Grover published his algorithm, Bennett, Bernstein, Brassard, and Vazirani proved that any quantum solution to the problem needs to evaluate the function ?(${\displaystyle {\sqrt {N}}}$) times, so Grover's algorithm is asymptotically optimal.

It has been shown that a non-local hidden variable quantum computer could implement a search of an N-item database at most in ${\displaystyle O({\sqrt[{3}]{N}})}$ steps. This is faster than the ${\displaystyle O({\sqrt {N}})}$ steps taken by Grover's algorithm. Neither search method will allow quantum computers to solve NP-Complete problems in polynomial time.

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 ${\displaystyle N}$ is large. Grover's algorithm could brute-force a 128-bit symmetric cryptographic key in roughly 2⁶⁴ iterations, or a 256-bit key in roughly 2¹²⁸ iterations. As a result, it is sometimes suggested that symmetric key lengths be doubled to protect against future quantum attacks.

Like many quantum algorithms, Grover's algorithm is probabilistic in the sense that it gives the correct answer with a probability of less than 1. Though there is technically no upper bound on the number of repetitions that might be needed before the correct answer is obtained, the expected number of repetitions is a constant factor that does not grow with ${\displaystyle N}$. 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.

Video Grover's algorithm

Applications

Although the purpose of Grover's algorithm is usually described as "searching a database", it may be more accurate to describe it as "inverting a function". In fact since the oracle for an unstructured database requires at least linear complexity, the algorithm cannot be used for actual databases. Roughly speaking, if we have a function ${\displaystyle y=f(x)}$ that can be evaluated on a quantum computer, Grover's algorithm allows us to calculate ${\displaystyle x}$ when given ${\displaystyle y}$. Inverting a function is related to the searching of a database because we could come up with a function that produces one particular value of ${\displaystyle y}$ ("true", for instance) if ${\displaystyle x}$ matches a desired entry in a database, and another value of ${\displaystyle y}$ ("false") for other values of ${\displaystyle x}$.

Grover's algorithm can also be used for estimating the mean and median of a set of numbers, and for solving the collision problem. The algorithm can be further optimized if there is more than one matching entry and the number of matches is known beforehand. Grover's algorithm can be used to crack passwords as well.

Maps Grover's algorithm

Setup

Consider an unsorted database with N entries. The algorithm requires an N-dimensional state space H, which can be supplied by n = log₂ N qubits. Consider the problem of determining the index of the database entry that satisfies some search criterion. Let f be the function that maps database entries to 0 or 1, where f(x) = 1 if and only if x satisfies the search criterion (x = ?). We are provided with (quantum black box) access to a subroutine 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}}}$

An alternative definition of U_? may be encountered assuming the presence of an ancillary qubit system (like in the quantum circuit depicted below). The operation then represents a conditional inversion (NOT gate) conditioned by the value of f(x) on the main system:

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

or briefly,

${\displaystyle U_{\omega }|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle .}$

This is a natural way to realize a binary operation using the method of uncomputation. Note that if the ancillary qubit is prepared in the state ${\displaystyle |-\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}=H|1\rangle }$, the effective operation of this controlled NOT gate becomes equivalent to the original form, leaving the ancillary system disentangled from the main system:

${\displaystyle U_{\omega }{\big (}|x\rangle \otimes |-\rangle {\big )}={\frac {1}{\sqrt {2}}}\left(U_{\omega }|x\rangle |0\rangle -U_{\omega }|x\rangle |1\rangle \right)={\frac {1}{\sqrt {2}}}\left(|x\rangle |f(x)\rangle -|x\rangle |1\oplus f(x)\rangle \right)={\begin{cases}{\frac {1}{\sqrt {2}}}\left(|x\rangle |1\rangle -|x\rangle |0\rangle \right)=-|x\rangle \otimes |-\rangle &{\text{if }}f(x)=1,\\{\frac {1}{\sqrt {2}}}\left(|x\rangle |0\rangle -|x\rangle |1\rangle \right)=|x\rangle \otimes |-\rangle &{\text{if }}f(x)=0\end{cases}}}$

In either setting, our goal is to identify the index ${\displaystyle |\omega \rangle }$.

src: slideplayer.com

Algorithm steps

The steps of Grover's algorithm are given as follows. Let ${\displaystyle |s\rangle }$ denote the uniform superposition over all states

${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$

Then the operator

${\displaystyle U_{s}=2\left|s\right\rangle \left\langle s\right|-I}$

is known as the Grover diffusion operator.

Here is the algorithm:

1. Initialize the system to the state
   ${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle }$.
2. Perform the following "Grover iteration" r(N) times. The function r(N), which is asymptotically O(N^1/2), is described below.
   1. Apply the operator ${\displaystyle U_{\omega }}$.
   2. Apply the operator ${\displaystyle U_{s}}$.
3. Perform the measurement ?. The measurement result will be eigenvalue ?_? with probability approaching 1 for N >> 1. From ?_?, ? may be obtained.

src: i.ytimg.com

The first iteration

A preliminary observation, in parallel with our definition

${\displaystyle U_{s}=2|s\rangle \langle s|-I,}$

is that ${\displaystyle U_{\omega }}$ can be expressed in an alternate way:

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

In other words, both transformations are of Householder transformation type. To prove this it suffices to check how ${\displaystyle U_{\omega }}$ acts on basis states:

${\displaystyle {\begin{aligned}(I-2|\omega \rangle \langle \omega |)|\omega \rangle &=|\omega \rangle -2|\omega \rangle \langle \omega |\omega \rangle =-|\omega \rangle =U_{\omega }|\omega \rangle ,\\(I-2|\omega \rangle \langle \omega |)|x\rangle &=|x\rangle -2|\omega \rangle \langle \omega |x\rangle =|x\rangle =U_{\omega }|x\rangle &&\forall x\neq \omega .\end{aligned}}}$

The following computations show what happens in the first iteration:

${\displaystyle {\begin{aligned}\langle \omega |s\rangle &=\langle s|\omega \rangle ={\tfrac {1}{\sqrt {N}}},\\\langle s|s\rangle &=N{\tfrac {1}{\sqrt {N}}}\cdot {\tfrac {1}{\sqrt {N}}}=1,\\U_{\omega }|s\rangle &=(I-2|\omega \rangle \langle \omega |)|s\rangle =|s\rangle -2|\omega \rangle \langle \omega |s\rangle =|s\rangle -{\tfrac {2}{\sqrt {N}}}|\omega \rangle ,\\U_{s}\left(|s\rangle -{\tfrac {2}{\sqrt {N}}}|\omega \rangle \right)&=\left(2|s\rangle \langle s|-I\right)\left(|s\rangle -{\tfrac {2}{\sqrt {N}}}|\omega \rangle \right)=2|s\rangle \langle s|s\rangle -|s\rangle -{\tfrac {4}{\sqrt {N}}}|s\rangle \langle s|\omega \rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle \\&=2|s\rangle -|s\rangle -{\tfrac {4}{\sqrt {N}}}\cdot {\tfrac {1}{\sqrt {N}}}|s\rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle =|s\rangle -{\tfrac {4}{N}}|s\rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle \\&={\tfrac {N-4}{N}}|s\rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle .\end{aligned}}}$

It is worth noting the special case of N = 4 with a single marked state. This has ${\displaystyle U_{s}U_{w}|s\rangle =|\omega \rangle }$, meaning that in a single application of the Grover iterator the marked state is returned.

After application of the operators ${\displaystyle U_{\omega }}$ and ${\displaystyle U_{s}}$, the square amplitude of the queried element has increased from ${\displaystyle \left|\langle \omega |s\rangle \right|^{2}={\tfrac {1}{N}}}$ to ${\displaystyle \left|\langle \omega |U_{s}U_{\omega }|s\rangle \right|^{2}={\tfrac {(3N-4)^{2}}{N^{3}}}=9(1-{\tfrac {4}{3N}})^{2}\cdot {\tfrac {1}{N}}}$.

src: i0.wp.com

Description of U_?

Grover's algorithm requires a "quantum oracle" operator ${\displaystyle U_{\omega }}$, which can recognize solutions to the search problem and give them a negative sign. In order to keep the search algorithm general, we will leave the inner workings of the oracle as a black box, but will explain how the sign is flipped. The oracle contains a function ${\displaystyle f}$ that returns ${\displaystyle f(x)=1}$ if ${\displaystyle |x\rangle }$ is a solution to the search problem and ${\displaystyle f(x)=0}$ otherwise. The oracle is a unitary operator operating on two qubits:

${\displaystyle |x\rangle |q\rangle {\overset {U_{\omega }}{\longrightarrow }}|x\rangle |q\oplus f(x)\rangle ,}$

where ${\displaystyle |x\rangle }$ is the index qubit and ${\displaystyle |q\rangle }$ is the oracle qubit.

As usual, ${\displaystyle \oplus }$ denotes addition modulo 2. The operation flips the oracle qubit if ${\displaystyle f(x)=1}$ and leaves it unchanged otherwise. In Grover's algorithm we want to flip the sign of the state ${\displaystyle |x\rangle }$ if it labels a solution. This is achieved by setting the oracle qubit in the state ${\displaystyle (|0\rangle -|1\rangle )/{\sqrt {2}}}$, which is flipped to ${\displaystyle (|1\rangle -|0\rangle )/{\sqrt {2}}}$ if ${\displaystyle |x\rangle }$ is a solution:

${\displaystyle |x\rangle \left(|0\rangle -|1\rangle \right)/{\sqrt {2}}{\overset {U_{\omega }}{\longrightarrow }}(-1)^{f(x)}|x\rangle \left(|0\rangle -|1\rangle \right)/{\sqrt {2}}.}$

We regard ${\displaystyle |x\rangle }$ as flipped, thus the oracle qubit is not changed, so by convention the oracle qubits are usually not mentioned in the specification of Grover's algorithm. Thus the operation of the oracle ${\displaystyle U_{\omega }}$ is simply written as

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

src: i.ytimg.com

Geometric proof of correctness

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 }$. We will consider the first iteration, acting on the initial ket ${\displaystyle |s\rangle }$. Since ${\displaystyle |\omega \rangle }$ is one of the basis vectors in ${\displaystyle |s\rangle }$ the overlap is

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

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 }$. The operator ${\displaystyle U_{s}}$ is a reflection through ${\displaystyle |s\rangle }$. Therefore, the state vector remains in the plane spanned by ${\displaystyle |s'\rangle }$ and ${\displaystyle |\omega \rangle }$ after each application of the operators ${\displaystyle U_{s}}$ and ${\displaystyle U_{\omega }}$, and 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}}}}$.

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}$.

src: slideplayer.com

Algebraic proof of correctness

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{pmatrix}-1&0\\2/{\sqrt {N}}&1\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}.}$

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

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{pmatrix}-1&0\\2/{\sqrt {N}}&1\end{pmatrix}}{\begin{pmatrix}-1&-2/{\sqrt {N}}\\0&1\end{pmatrix}}={\begin{pmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{pmatrix}}.}$

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{pmatrix}\exp(2it)&0\\0&\exp(-2it)\end{pmatrix}}M^{-1}}$ where ${\displaystyle M={\begin{pmatrix}-i&i\\\exp(it)&\exp(-it)\end{pmatrix}}.}$

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

${\displaystyle (U_{s}U_{\omega })^{r}=M{\begin{pmatrix}\exp(2rit)&0\\0&\exp(-2rit)\end{pmatrix}}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{pmatrix}\langle \omega |\omega \rangle &\langle \omega |s\rangle \end{pmatrix}}(U_{s}U_{\omega })^{r}{\begin{pmatrix}0\\1\end{pmatrix}}\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{pmatrix}0\\1\end{pmatrix}}\approx (|\omega \rangle \,|s\rangle )M{\begin{pmatrix}i&0\\0&-i\end{pmatrix}}M^{-1}{\begin{pmatrix}0\\1\end{pmatrix}}=|\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 O(1/N).

src: www.pnas.org

Extension to space with multiple targets

If, instead of 1 matching entry, there are k matching entries, the same algorithm works, but the number of iterations must be ?(N/k)^1/2/4 instead of ?N^1/2/4.

There are several ways to handle the case if k is unknown. For example, one could run Grover's algorithm several times, with

${\displaystyle \pi {\frac {N^{1/2}}{4}},\pi {\frac {(N/2)^{1/2}}{4}},\pi {\frac {(N/4)^{1/2}}{4}},\ldots }$

iterations. For any k, one of the iterations will find a matching entry with a sufficiently high probability. The total number of iterations is at most

${\displaystyle \pi {\frac {N^{1/2}}{4}}\left(1+{\frac {1}{\sqrt {2}}}+{\frac {1}{2}}+\cdots \right)=\pi {\frac {N^{1/2}}{4}}\left(2+{\sqrt {2}}\right),}$

which is still O(N^1/2). It can be shown that this can be improved. If the number of marked items is k, where k is unknown, there is an algorithm that finds the solution in ${\displaystyle {\sqrt {N/k}}}$ queries. This fact is used in order to solve the collision problem.

src: slideplayer.com

Quantum partial search

A modification of Grover's algorithm called quantum partial search was described by Grover and Radhakrishnan in 2004. 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 ${\displaystyle K}$ blocks, each of size ${\displaystyle b=N/K}$. Obviously, 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 don't find the target, then we know it's in the block we didn't search. The average number of iterations drops from ${\displaystyle N/2}$ to ${\displaystyle (N-b)/2}$.

Grover's algorithm requires ${\displaystyle \pi /4{\sqrt {N}}}$ iterations. Partial search will be faster by a numerical factor that depends on the number of blocks ${\displaystyle K}$. Partial search uses ${\displaystyle n_{1}}$ global iterations and ${\displaystyle n_{2}}$ local iterations. The global Grover operator is designated ${\displaystyle G_{1}}$ and the local Grover operator is designated ${\displaystyle G_{2}}$.

The global Grover operator acts on the blocks. Essentially, it is given as follows:

1. Perform ${\displaystyle j_{1}}$ standard Grover iterations on the entire database.
2. Perform ${\displaystyle j_{2}}$ local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block.
3. Perform one standard Grover iteration.

The optimal values of ${\displaystyle j_{1}}$ and ${\displaystyle j_{2}}$ 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 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.

src: slideplayer.com

Optimality

It is known that Grover's algorithm is optimal. That is, any algorithm that accesses the database only by using the operator U_? must apply U_? at least as many times as Grover's algorithm. 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 (but does not prove) that NP is not contained in BQP.

The number of iterations for k matching entries, ?(N/k)^1/2/4, is also optimal.

src: file.scirp.org

Applicability and limitations

When applications of Grover's algorithm are considered, it should be emphasized that the database is not represented explicitly. Instead, an oracle is invoked to evaluate an item by its index. Reading a full data-base 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 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. These and other considerations about using Grover's algorithm are discussed in a paper by Viamontes, Markov and Hayes.

src: slideplayer.com

See also

• Amplitude amplification
• Shor's algorithm
• De Broglie-Bohm theory

src: slideplayer.com

Notes

src: file.scirp.org

References

• 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
• Grover's Algorithm: Quantum Database Search, C. Lavor, L.R.U. Manssur, R. Portugal
• Grover's algorithm on arxiv.org

src: slideplayer.com

External links

• Davy Wybiral. "Quantum Circuit Simulator". 
• 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. 
• Hazewinkel, Michiel, ed. (2001) [1994], "Quantum computation, theory of", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 

Source of article : Wikipedia