Grover's algorithm

proper noun

A quantum algorithm that finds with high probability the unique input to a black-box function that produces a particular output value.

Ask AI about this wordChatGPTClaudePerplexityGoogle AIGrok

Meanings

proper noun
  1. computerA quantum algorithm that finds with high probability the unique input to a black-box function that produces a particular output value.

    |Q_A⟩=Gʳ|Ψ(0)⟩≈ sin ((2r+1)ϕ)1/(√k)∑_( mathit )solutions|y⟩ (3.59) where the probability of finding a nonsolution is presumed to be small and has been neglected in the equation.

    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
    2 more examples

    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, LNCS 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.

Origin

Named after Indian-American computer scientist Lov Grover, who devised the algorithm in 1996.

Full word history & related roots →

Translations

Bulgarian алгоритъм на Гроувър
  • алгоритъм на Гроувър (algorităm na Grouvăr)quantum algorithm
French algorithme de Grover
  • algorithme de Groverquantum algorithm
German Grover-Algorithmus
  • Grover-Algorithmusquantum algorithm
Cite this entry
APA

Grover's algorithm. (n.d.). In WatkinsX Dictionary. Retrieved November 3, 2026, from https://dictionary.watkinsx.com/word/Grover's%20algorithm

MLA

“Grover's algorithm.” WatkinsX Dictionary, https://dictionary.watkinsx.com/word/Grover's%20algorithm. Accessed November 3, 2026.

Chicago

WatkinsX Dictionary, s.v. “Grover's algorithm,” accessed November 3, 2026, https://dictionary.watkinsx.com/word/Grover's%20algorithm.

Source: Grover's algorithm on Wiktionary, CC BY-SA 4.0.