Grover algorithm

The Grover algorithm is a quantum algorithm for searching in an unsorted database with entries in steps and with memory requirements (see O notation ). It was published by Lov Grover in 1996 and is the only known algorithm to date for which it has been proven that quantum computers are in principle faster than classical computers . ${\displaystyle N}$ ${\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}$ ${\displaystyle {\mathcal {O}}\left(\log N\right)}$

On a classic computer, the fastest possible search algorithm in an unsorted database is the linear search , which requires computational steps. The Grover algorithm thus delivers a quadratic acceleration, which is considerable for large ones. ${\displaystyle {\mathcal {O}}\left(N\right)}$ ${\displaystyle N}$

Like most quantum algorithms, the Grover algorithm is a probabilistic algorithm ; That is, it gives the correct answer with a high probability , whereby the probability of an incorrect answer can be reduced by simply repeating the algorithm.

Applications

The Grover algorithm does not actually allow a direct search in unsorted databases, but the inverse of a finite function , because for a given value a value corresponds to a search for a value in the domain of . ${\displaystyle y=f(x)}$ ${\displaystyle y}$ ${\displaystyle x=f^{-1}(y)}$ ${\displaystyle x}$ ${\displaystyle f}$

The Grover algorithm can also be used to compute the mean and median of a set of numbers, as well as to solve the collision problem . It can also be used to solve NP-complete problems by going through the set of all possible problems. Although NP-complete problems can be solved considerably faster with this, the Grover algorithm does not allow a solution in polynomial time complexity either .

Detailed process

The following sequence of the algorithm relates to the search for a single search entry. The algorithm can be further optimized in order to find one of several possible entries, the number of which is known in advance.

requirements

Given is an unsorted database with entries, which is represented in a -dimensional state space by qubits . The entries are numbered with . Then we choose an acting observable with different eigenstates ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle \log _{2}N}$ ${\displaystyle 0,1,\dots ,(N-1)}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle \Omega }$ ${\displaystyle N}$

${\displaystyle \left\{\left\vert 0\right\rangle ,\left\vert 1\right\rangle ,\cdots ,\left\vert N-1\right\rangle \right\}}$

(in Bra-Ket notation) and the associated eigenvalues

${\displaystyle \left\{\lambda _{0},\lambda _{1},\cdots ,\lambda _{N-1}\right\}.}$

A unitary operator is also given, which represents a subroutine , the so-called oracle , which efficiently compares the database entries according to the search criterion. The algorithm does not determine how the oracle works, but it has to process the superposition of the quantum states and recognize the eigenstate sought : ${\displaystyle U_{\omega }}$ ${\displaystyle \left\vert \omega \right\rangle }$

${\displaystyle U_{\omega }\left\vert \omega \right\rangle =-\left\vert \omega \right\rangle }$

${\displaystyle U_{\omega }\left\vert x\right\rangle =\left\vert x\right\rangle \qquad \forall x\neq \omega }$

The aim of the algorithm is to identify this eigenstate or, equivalently, the eigenvalue . ${\displaystyle \left\vert \omega \right\rangle }$ ${\displaystyle \omega }$

Step sequence

1. Initialize the system in the state

   ${\displaystyle \left\vert s\right\rangle ={\frac {1}{\sqrt {N}}}\sum _{x}\left\vert x\right\rangle }$

2. Carry out the following so-called Grover iteration times. (The function is described below.) ${\displaystyle r(N)}$ ${\displaystyle r}$
   1. Apply the operator (first household transformation ). ${\displaystyle U_{\omega }=I-2\left\vert \omega \right\rangle \left\langle \omega \right\vert }$
   2. Apply the operator (second household transformation ). ${\displaystyle U_{s}=-(I-2\left\vert s\right\rangle \left\langle s\right\vert )}$
3. Take the measurement of . The measurement result is close to with a probability if . With the measurement of , the system is in the state . ${\displaystyle \Omega }$ ${\displaystyle \lambda _{\omega }}$ ${\displaystyle 1}$ ${\displaystyle N\gg 1}$ ${\displaystyle \lambda _{\omega }}$ ${\displaystyle \omega }$

Geometric view and determination of the number of steps r (N)

The initial state is

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

Let us consider the plane spanned by and . Let be a ket vector in this plane, perpendicular to . Since is one of the basis vectors, it follows ${\displaystyle \left\vert s\right\rangle }$ ${\displaystyle \left\vert \omega \right\rangle }$ ${\displaystyle \vert \omega ^{\times }\rangle }$ ${\displaystyle \left\vert \omega \right\rangle }$ ${\displaystyle \left\vert \omega \right\rangle }$

${\displaystyle \langle \omega \mid s\rangle ={\frac {1}{\sqrt {N}}}}$

Geometrically this means that and are at an angle to each other, where is given by ${\displaystyle \left\vert \omega \right\rangle }$ ${\displaystyle \left\vert s\right\rangle }$ ${\displaystyle {\tfrac {\pi }{2}}-\theta }$ ${\displaystyle \theta =\theta (N)}$

${\displaystyle \cos \left({\frac {\pi }{2}}-\theta \right)={\frac {1}{\sqrt {N}}}}$

consequently is

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

The operator is a reflection on the hyperplane that is too orthogonal ; for vectors in the plane spanned by and spanned, it acts as a reflection on the straight line . The operator is a reflection on the straight line through . The state vector remains after the application of and in the plane spanned by and . In this way, the operator rotates the state vector by an angle from to with each step of the Grover iteration . ${\displaystyle U_{\omega }}$ ${\displaystyle \left\vert \omega \right\rangle }$ ${\displaystyle \left\vert s\right\rangle }$ ${\displaystyle \left\vert \omega \right\rangle }$ ${\displaystyle \vert \omega ^{\times }\rangle }$ ${\displaystyle U_{s}}$ ${\displaystyle \left\vert s\right\rangle }$ ${\displaystyle U_{s}}$ ${\displaystyle U_{\omega }}$ ${\displaystyle \left\vert s\right\rangle }$ ${\displaystyle \left\vert \omega \right\rangle }$ ${\displaystyle U_{s}\ U_{\omega }}$ ${\displaystyle 2\theta }$ ${\displaystyle \left\vert \omega \right\rangle }$

The algorithm must stop as soon as the state vector comes closest. Further iterations would turn it away again and thus reduce the probability of the correct answer again. For the optimal number of iterations for an exact match with applies ${\displaystyle \left\vert \omega \right\rangle }$ ${\displaystyle r}$ ${\displaystyle \left\vert \omega \right\rangle }$

${\displaystyle {\frac {\pi }{2}}-\theta =2\theta r,}$

so

${\displaystyle r(N)={\frac {\pi }{4\theta (N)}}-{\frac {1}{2}}}$

But since it has to be a whole number , we set equal to the rounded number . So the probability of measuring a wrong answer is . The probability of error in database entries is therefore asymptotic , i.e. i.e., it is negligibly small for large ones . ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle {\tfrac {\pi }{4\theta }}-{\tfrac {1}{2}}}$ ${\displaystyle {\mathcal {O}}\left(1-\cos ^{2}\theta \right)={\mathcal {O}}\left(\sin ^{2}\theta \right)}$ ${\displaystyle N}$ ${\displaystyle {\mathcal {O}}\left({\tfrac {1}{N}}\right)}$ ${\displaystyle N}$

For true , so ${\displaystyle N\gg 1}$ ${\displaystyle \theta \approx N^{-{\frac {1}{2}}}}$

${\displaystyle r(N)\longrightarrow {\frac {\pi {\sqrt {N}}}{4}}}$

Extensions

If the database contains not just one but searched entries, the algorithm also works, but the number of iterations to be carried out now applies instead . If unknown, the Grover algorithm is carried out in ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle {\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{k}}}}$ ${\displaystyle {\tfrac {\pi }{4}}{\sqrt {N}}}$ ${\displaystyle k}$

${\displaystyle {\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{1}}},\;{\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{2}}},\;{\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{4}}},\;{\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{8}}},\ldots }$

Iterations through. A searched entry is found for anything with a sufficiently high probability. The total number of iterations is at most ${\displaystyle k}$

${\displaystyle \pi {\frac {\sqrt {N}}{4}}\left(1+{\frac {1}{\sqrt {2}}}+{\frac {1}{2}}+\cdots \right)={\mathcal {O}}\left({\sqrt {N}}\right)}$

Grover algorithm optimality

The Grover algorithm is optimal in the sense that there can be no quantum algorithm with fewer than calculation steps . This result is important to understand the limits of quantum computing. For example, if the search problem could be solved with steps in the worst case , then NP would be contained in BQP . ${\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}$ ${\displaystyle {\mathcal {O}}\left(\log ^{c}N\right)}$

Likewise, the number i. A. Necessary iterations for searched entries, so , optimal. ${\displaystyle k}$ ${\displaystyle \pi {\sqrt {\tfrac {N}{2k}}}}$

Qualitative argument

In order to gain a heuristic understanding of the quantum mechanical procedure in comparison to the classical procedure, and for generalizations, it makes sense to consider the following special case: the information sought should lie on a specific grid point of a square grid. The search thus classically requires steps if the edge length of the square is. Quantum mechanical states, on the other hand, are rays in Hilbert space , i. That is, they are only determined up to a factor, and if one starts from the center of the square, the direction of the ray is given by a set of points which corresponds only to the circumference and not to the content of the square, i.e. a set . In order to find a special point on the selected beam, one only has to carry out interference experiments with other quantum mechanical states, which is possible with practically no additional expenditure of time. The information you are looking for is obtained in quantum mechanical steps. ${\displaystyle N}$ ${\displaystyle {\sqrt {N}}}$ ${\displaystyle \theta }$ ${\displaystyle \sim {\mathcal {O}}\left({\sqrt {N}}\right)}$ ${\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}$

Related topics

A completely different problem, in which quantum computers also bring about a substantial acceleration, concerns the factorization of a very large number (see Shor's algorithm ).

literature

• M. Homeister: Understanding Quantum Computing Springer Vieweg, Wiesbaden 2018, fifth edition, ISBN 978-3-6582-2883-5 , pp. 137ff.
• B. Lenze: Mathematik und Quantum Computing Logos Verlag, Berlin 2020, second edition, ISBN 978-3-8325-4716-5 , p. 57ff.
• RJ Lipton, KW Regan: Quantum Algorithms via Linear Algebra: A Primer MIT Press, Cambridge MA 2014, ISBN 978-0-2620-2839-4 , pp. 115ff.
• MA Nielsen, IL Chuang: Quantum Computation and Quantum Information Cambridge University Press, Cambridge MA 2010, ISBN 978-1-1070-0217-3 , pp. 248ff.
• W. Scherer: Mathematics of Quanteninformatik Springer-Verlag, Berlin-Heidelberg 2016, ISBN 978-3-6624-9079-2 , p. 235ff.
• CP Williams: Explorations in Quantum Computing Springer-Verlag, London 2011, second edition, ISBN 978-1-8462-8886-9 , pp. 245ff.

Web links

• Grover LK: From Schrödinger's equation to quantum search algorithm , American Journal of Physics, 69 (7): 769-777, 2001. Overview of the algorithm and its history (English)
• Grover LK: 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. (English)
• What's a Quantum Phone Book? ( February 1, 2014 memento on the Internet Archive ), Lov Grover, Bell Labs
• Quantum search algorithms on arxiv.org

Individual evidence

1. ↑ Grover, LK: A fast quantum mechanical algorithm for database search , Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
2. ↑ It is true that the Shor algorithm, a polynomially fast probabilistic factoring algorithm for quantum computers, is known, while no known classical factoring algorithm has polynomial runtime; however, so far there is no mathematical proof that such an algorithm does not exist.
3. ^ Bennett CH, Bernstein E., Brassard G., Vazirani U .: The strengths and weaknesses of quantum computation . SIAM Journal on Computing 26 (5): 1510-1523 (1997)