Grover's algorithm

[1] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani proved that any quantum solution to the problem needs to evaluate the function

[2] Since classical algorithms for NP-complete problems require exponentially many steps, and Grover's algorithm provides at most a quadratic speedup over the classical solution for unstructured search, this suggests that Grover's algorithm by itself will not provide polynomial-time solutions for NP-complete problems (as the square root of an exponential function is still an exponential, not a polynomial, function).

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).

Grover's algorithm essentially solves the task of function inversion.

The database in this analogy is a table of all of the function's outputs, indexed by the corresponding input.

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.

[13] Fortunately, fast Grover's oracle implementation is possible for many constraint satisfaction and optimization problems.

[14] The major barrier to instantiating a speedup from Grover's algorithm is that the quadratic speedup achieved is too modest to overcome the large overhead of near-term quantum computers.

[15] However, later generations of fault-tolerant quantum computers with better hardware performance may be able to realize these speedups for practical instances of data.

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

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

The operation then represents an inversion (NOT gate) on the main system conditioned by the value of f(x) from the ancillary system: or briefly, These oracles are typically realized using uncomputation.

of each Grover iteration step rotates the state vector by an angle of

The exact probability of measuring the correct answer is where r is the (integer) number of Grover iterations.

Notice that during the entire computation, the state of the algorithm is a linear combination of

, it is It follows that r-th power of the matrix (corresponding to r iterations) is Using this form, we can use trigonometric identities to compute the probability of observing ω after r iterations mentioned in the previous section, 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

Then the system is in state A short calculation now shows that the observation yields the correct answer ω with error

With sufficiently high probability, a marked entry will be found by iteration

for some constant c. Thus, the total number of iterations taken is at most Another approach if k is unknown is to derive it via the quantum counting algorithm prior.

, a classical running of the checking oracle on a single random choice of input will more likely than not give a correct solution.

Partial search will be faster by a numerical factor that depends on the number of blocks

This idea was studied in detail by Vladimir 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.

[21] The extension of Grover's algorithm to k matching entries, π(N/k)1/2/4, is also optimal.

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