Grover's algorithm

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

Grover's algorithm

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

It is assumed that the function 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 on this ", 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 "That classically requires brute force all options.

The GSA finds any root of the equation using function calls , using 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 roots, according to the scheme of Grover, you can find one of them on a quantum computer during (even 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 appeals to . 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 cannot be improved [3] .
• A higher quantum acceleration than the quadratic one cannot be obtained for the nonvanishing fraction of all possible black boxes. [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 there is a unitary operator that mirrors the Hilbert space with respect to the hyperplane perpendicular to the vector , - the state corresponding to the root of equation (1), - uniform superposition of all states. Then GSA consists in applying the operator to the state number of times equal to the integer part . The result will almost coincide with the state .

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. . The quantum algorithm finds a maximum of appeals to f .
• Structured search algorithm (Farhi, Gutman). Looking for a solution to equation (1) with the additional condition where split line 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 on which function takes the same value. The algorithm requires appeals to f .

Continuous versions of Grover’s algorithm

• Let the Hamiltonian of a quantum system be where and are operators and respectively. Then continuous unitary evolution with Hamiltonian starting from naturally leads to . 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 under the action of the Hamiltonian depending on f , according to the adiabatic theorem, for a time on the order of leads to state .

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. where is the angle between and makes up . 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