Grover's algorithm

English

Etymology

Named after Indian-American computer scientist Template:W, who devised the algorithm in 1996.

Proper noun

1. Template:Lb A quantum algorithm that finds with high probability the unique input to a black-box function that produces a particular output value.
   • 2006, E. Arikan, 22: An Upper Bound on the Rate of Information Transfer by Grover's Algorithm, Rudolf Ahlswede et al. (editors), General Theory of Information Transfer and Combinatorics, Springer, Template:W 4123, page 452,

     Thus, Grover's algorithm has optimal order of complexity. Here, we present an information-theoretic analysis of Grover's algorithm and show that the square-root speed-up by Grover's algorithm is the best possible by any algorithm using the same quantum oracle.

   • 2018, Joseph F. Fitzsimons, Eleanor G. Rieffel, Valerio Scarani, 11: Quantum Frontier, Justyna Zander, Pieter J. Mosterman (editors), Computation for Humanity, Taylor & Francis (CRC Press), page 286,

     The best possible classical algorithm uses $O(N)$ time. This speed up is only polynomial, but, unlike for Shor's algorithm, it has been proven that Grover's algorithm outperforms any possible classical approach.

   • 2022 [2008 Morgan & Claypool], Marco Lanzagorta, Jeffrey Uhlmann, Quantum Computer Science, Springer Nature, page 49,

     However, we cannot output the entire solution dataset using a single application of Grover's algorithm. Indeed, the superposition of states for the last iteration of Grover's algorithm, with known $k$, looks like:

     $|Q_A⟩=G^r|\mathrm{\Psi }(0)⟩\approx \sin ((2r+1)\varphi )\frac{1}{\sqrt{k}}\sum _{𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛𝑠}|y⟩$      (3.59)

     where the probability of finding a nonsolution is presumed to be small and has been neglected in the equation.

Translations

• French: Template:T
• German: Template:T
• Italian: Template:T-needed