It is well-known that Grover's algorithm is asymptotically optimal. However, is a better algorithm possible by constant factors? And if so, is it known?

Suppose a fixed number of iterations $r$ and ratio $\rho$ of market elements such that, by using the geometric interpretation, the angle does not exceed $\pi/2$ (something like a truncated Grover). For example, for $r = 1$, think in a ratio $\rho \leq 0.25$.

My question is that in such conditions, Grover hits the highest possible probability of measuring a market element (the best amplification) for an quantum algorithm that uses $r$ calls of the oracle.


1 Answer 1


Grover's search is exactly (not just asymptotically) optimal: https://arxiv.org/abs/quant-ph/9711070


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.