You get a bonus - 1 coin for daily activity. Now you have 1 coin

Grover's algorithm

Lecture



The Grover algorithm (born Grover search algorithm , GSA) is a quantum algorithm for solving the search problem, that is, finding a solution to the equation

  Grovers algorithm

Grover's algorithm

  Grovers algorithm

Where   Grovers algorithm is a Boolean function of n variables. [one]

It is assumed that the function   Grovers algorithm given in the form of a black box, or an oracle, that is, in the course of a solution, we can only ask the oracle a question like: "what is   Grovers algorithm on this   Grovers algorithm ", And after receiving the answer to use it in further calculations. That is, the problem of solving equation (1) is a general form of the enumeration problem; here you need to find the "password to the device   Grovers algorithm "That classically requires brute force all   Grovers algorithm options.

The GSA finds any root of the equation using   Grovers algorithm function calls   Grovers algorithm , using   Grovers algorithm qubits. [2] The algorithm was discovered by the American mathematician Lov Grover in 1996.

Content

  • 1Properties
  • 2Algorithms using the Grover scheme
  • 3Continuous versions of the Grover algorithm
  • 4Application
  • 5SM. also
  • 6Notes
  • 7Links

Properties

If equation (1) has   Grovers algorithm roots, according to the scheme of Grover, you can find one of them on a quantum computer during   Grovers algorithm (even   Grovers algorithm not known in advance), that is, the basic quantum complexity is the square root of the classical.

The classical algorithm for solving such a problem (linear search) obviously requires   Grovers algorithm appeals to   Grovers algorithm . The Grover algorithm allows us to solve the search problem in the time of the order of the square root of the classical one, which is a tremendous acceleration. GSA is proven to be optimal in the following ways:

  • Constant   Grovers algorithm cannot be improved [3] .
  • A higher quantum acceleration than the quadratic one cannot be obtained for the nonvanishing fraction of all possible black boxes.   Grovers algorithm [4] .

The GSA is an example of a mass task dependent on an oracle. For more particular problems, it is possible to obtain greater quantum acceleration. For example, Shor’s factorization algorithm yields an exponential gain compared to the corresponding classical algorithms.

The fact that f is given in the form of a black box does not affect in general the complexity of both quantum and classical algorithms. Knowledge of the “device” of the function f (for example, knowledge of its defining scheme of functional elements) generally cannot help in solving equation (1). A database search corresponds to the inverse of a function that takes a specific value if the argument x corresponds to the required record in the database.

Let be   Grovers algorithm there is a unitary operator that mirrors the Hilbert space with respect to the hyperplane perpendicular to the vector   Grovers algorithm ,   Grovers algorithm - the state corresponding to the root of equation (1),   Grovers algorithm - uniform superposition of all states. Then GSA consists in applying the operator   Grovers algorithm to the state   Grovers algorithm number of times equal to the integer part   Grovers algorithm . The result will almost coincide with the state   Grovers algorithm .

Algorithms using the Grover scheme

  • Algorithm of searching for extremum of integer function (P. Hoyer and others). Search for the largest value of the function.   Grovers algorithm . The quantum algorithm finds a maximum of   Grovers algorithm appeals to f .
  • Structured search algorithm (Farhi, Gutman). Looking for a solution to equation (1) with the additional condition   Grovers algorithm where   Grovers algorithm split line   Grovers algorithm two rows of the same length. The algorithm has a complexity of the order of the square root of the classical time.
  • Algorithm for finding matching lines in the database (Ambainis). Looking for a couple of different arguments   Grovers algorithm on which function   Grovers algorithm takes the same value. The algorithm requires   Grovers algorithm appeals to f .

Continuous versions of Grover’s algorithm

  • Let the Hamiltonian of a quantum system be   Grovers algorithm where   Grovers algorithm and   Grovers algorithm are operators   Grovers algorithm and   Grovers algorithm respectively. Then continuous unitary evolution with Hamiltonian   Grovers algorithm starting from   Grovers algorithm naturally leads to   Grovers algorithm . The complexity of such a continuous GSA analog is exactly the same as for the discrete case.
  • Adiabatic GSA version . Slow evolution of the ground state type   Grovers algorithm under the action of the Hamiltonian depending on f , according to the adiabatic theorem, for a time on the order of   Grovers algorithm leads to state   Grovers algorithm .

Application

The meaning of GSA is to “amplitude jump” (amplitude amplification) of the target state by decreasing the amplitude of all other states. Geometrically, the GSA consists in rotating the current state vector of a quantum computer in the direction exactly to the target state (moving along the shortest path ensures the GSA is optimal). Each step gives a rotation at an angle.   Grovers algorithm where is the angle between   Grovers algorithm and   Grovers algorithm makes up   Grovers algorithm . Further continuation of the iterations of the operator G will continue the circumvention of the circle in the real plane generated by these vectors.

Grover's “amplitude jump” is apparently a fundamental physical phenomenon in the many-body quantum theory. For example, its accounting is necessary to estimate the probabilities of events that seem to be "rare". The process that implements the GSA scheme leads to an explosive growth of initially negligible amplitude, which can quickly bring it to actually observed values.

Grover’s algorithm can also be used to find the median and arithmetic mean of a number series. In addition, it can be used to solve NP-complete problems by exhaustive search among a variety of possible solutions. This may entail a significant increase in speed compared to classical algorithms, although not providing a “polynomial solution” in general.

see also

  • Quantum computer

Notes

  1. Sometimes GSA is not exactly called database search.
  2. The complexity of the algorithm, for the task with the oracle, also called the time of its work, is determined by the number of calls to the oracle.
  3. Christof Zalka, Grover's quantum searching algorithm is optimal, Phys.Rev. A60 (1999) 2746-2751 [1]
  4. Uri Yuri Ozhigov, Search for Extreme Point, Proc.Roy.Soc.Lond. A455 (1999) 2165-2172 [2]

Links

  • L. Grover. Quantum mechanics helps to find a needle in a haystack (for download)
  • Loginov O. V. and Tsyganov A. V. Grover’s Quantum Algorithm, St. Petersburg State University
  • The source code of a quantum computer simulator in C ++ and the implementation of Grover’s algorithm with a detailed description and circuits of quantum gates
created: 2016-04-02
updated: 2021-03-13
132495



Rating 9 of 10. count vote: 2
Are you satisfied?:



Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Quantum informatics

Terms: Quantum informatics