# Grover's algorithm

**Grover's algorithm** is a quantum algorithm, proposed by Lov K. Grover of Bell Labs in 1996, that searches an unstructured space of N items for a marked item using only O(√N) queries to an oracle, a quadratic speedup over the O(N) queries a classical search requires.<sup>[1](https://arxiv.org/abs/quant-ph/9605043)</sup> In Grover's original framing, a classical algorithm, deterministic or probabilistic, needs to look at about N/2 names in a random phone directory on average to find a given number with 50% probability, while the quantum algorithm obtains the answer in O(√N) steps and is within a small constant factor of the fastest possible quantum algorithm.<sup>[1](https://arxiv.org/abs/quant-ph/9605043)</sup>

| Key fact | Detail |
|---|---|
| Origin | Proposed by Lov K. Grover (Bell Labs, Murray Hill NJ); submitted 29 May 1996; presented at the 28th Annual ACM Symposium on the Theory of Computing (STOC), May 1996, pages 212–219<sup>[1](https://arxiv.org/abs/quant-ph/9605043)</sup> |
| Query complexity | O(√N) oracle queries for N items, versus N/2 classical queries on average for a 50% success probability<sup>[1](https://arxiv.org/abs/quant-ph/9605043)</sup> |
| Core operation | Grover operator \( \mathcal{Q} = H^{\otimes n} \mathcal{S}_0 H^{\otimes n} \mathcal{S}_f = D \, \mathcal{S}_f \), a phase oracle followed by the diffusion operator \( D = 2\lvert\psi\rangle\langle\psi\rvert - I \)<sup>[2](https://quantum.cloud.ibm.com/docs/en/api/qiskit/0.46/qiskit.algorithms.Grover)</sup> |
| Optimal iterations | \( t = \lfloor \pi/(4\theta) \rfloor \) with \( \theta = \sin^{-1}\sqrt{s/N} \); for one solution among N items, \( t \approx \frac{\pi}{4}\sqrt{N} \)<sup>[3](https://quantum.cloud.ibm.com/learning/en/courses/fundamentals-of-quantum-algorithms/grover-algorithm/number-of-iterations)</sup> |
| Optimality | Christof Zalka (T-6, Los Alamos National Laboratory) proved in 1997 that Grover's algorithm is exactly optimal for any success probability, requiring about \( \frac{\pi}{4}\sqrt{N} \) queries for near-certain success<sup>[4](https://arxiv.org/abs/quant-ph/9711070)</sup> |
| Generalization | Quantum amplitude amplification (Brassard, Høyer, Mosca, and Tapp, 2000) finds a good element after O(1/√a) applications of a state-preparation algorithm \( \mathcal{A} \) and its inverse, where a is the success probability<sup>[5](https://arxiv.org/abs/quant-ph/0005055)</sup> |
| Hardware status | Demonstrated on up to a few qubits on trapped-ion, superconducting, and silicon-spin platforms; a four-qubit silicon processor reached a (94.57 ± 2.63)% average success probability<sup>[6](https://www.nature.com/articles/s41565-024-01853-5)</sup> |

## How the algorithm works

The algorithm operates on n qubits, so the search space has \( N = 2^{n} \) basis states. It has four stages: initialization, oracle, amplification, and measurement.<sup>[7](https://www.nature.com/articles/s41467-017-01904-7)</sup>

**Initialization.** Hadamard gates applied to every qubit create the equal superposition \( \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \lvert x \rangle \), in which every item has the same amplitude.<sup>[8](https://quantum.cloud.ibm.com/learning/en/courses/utility-scale-quantum-computing/grovers-algorithm)</sup>

**Oracle.** The oracle is a quantum subroutine that marks the target state by flipping the sign of its amplitude, typically through phase kickback (qubit's phase change from interacting with a controlled operation); mathematically it applies a phase of −1 to states x for which the [Boolean function](https://www.edgepedia.org/boolean-function) f(x) = 1.<sup>[8](https://quantum.cloud.ibm.com/learning/en/courses/utility-scale-quantum-computing/grovers-algorithm)</sup> At this point the marked state has no higher probability of being measured than any other; only its phase differs.<sup>[9](https://quantum.cloud.ibm.com/learning/en/modules/computer-science/grovers)</sup>

**Diffusion.** The diffusion operator \( D = 2\lvert\psi\rangle\langle\psi\rvert - I \) performs an inversion about the average amplitude, increasing the amplitude of the marked state.<sup>[2](https://quantum.cloud.ibm.com/docs/en/api/qiskit/0.46/qiskit.algorithms.Grover)</sup><sup> • </sup><sup>[8](https://quantum.cloud.ibm.com/learning/en/courses/utility-scale-quantum-computing/grovers-algorithm)</sup> In circuit form it is \( H^{\otimes n} \mathcal{S}_0 H^{\otimes n} \), where \( \mathcal{S}_0 \) flips the phase of the all-zero state; the surrounding Hadamard layers change the reflection axis from \( \lvert 0 \rangle^{\otimes n} \) to the uniform superposition \( \lvert u \rangle \).<sup>[2](https://quantum.cloud.ibm.com/docs/en/api/qiskit/0.46/qiskit.algorithms.Grover)</sup><sup> • </sup><sup>[9](https://quantum.cloud.ibm.com/learning/en/modules/computer-science/grovers)</sup>

**Geometric picture.** The state lives in the two-dimensional plane spanned by the uniform superposition of unmarked states \( \lvert A_0 \rangle \) and the superposition of solutions \( \lvert A_1 \rangle \). Both the oracle and the diffusion step are reflections in this plane, and two reflections compose into a rotation that moves the state by an angle \( 2\theta \) toward \( \lvert A_1 \rangle \) in each iteration.<sup>[9](https://quantum.cloud.ibm.com/learning/en/modules/computer-science/grovers)</sup>

## Choosing the number of iterations

Each Grover iteration rotates the state by a fixed angle, so the number of iterations must be chosen carefully: applying too many rotates past the target and the success probability falls again.<sup>[9](https://quantum.cloud.ibm.com/learning/en/modules/computer-science/grovers)</sup> With s solutions among N items, the rotation angle is \( \theta = \sin^{-1}\sqrt{s/N} \), and the recommended number of iterations is \( t = \lfloor \pi/(4\theta) \rfloor \), giving success probability \( p = \sin^{2}((2t+1)\theta) \).<sup>[3](https://quantum.cloud.ibm.com/learning/en/courses/fundamentals-of-quantum-algorithms/grover-algorithm/number-of-iterations)</sup> For a unique solution this becomes \( t \approx \frac{\pi}{4}\sqrt{N} \), and the success probability satisfies \( p(N,1) \geq 1 - 1/N \) for all N.<sup>[3](https://quantum.cloud.ibm.com/learning/en/courses/fundamentals-of-quantum-algorithms/grover-algorithm/number-of-iterations)</sup>

**Unknown solution count.** If s is unknown, one simple approach chooses t uniformly at random from \( \{1, \ldots, \lfloor \pi\sqrt{N}/4 \rfloor \} \), which finds a solution with probability greater than 40% whenever one exists; repeating the procedure brings the probability close to 1.<sup>[3](https://quantum.cloud.ibm.com/learning/en/courses/fundamentals-of-quantum-algorithms/grover-algorithm/number-of-iterations)</sup> A refined method finds a solution with O(√(N/s)) queries even when s is unknown, and needs O(√N) queries to confirm that no solution exists when s = 0.<sup>[3](https://quantum.cloud.ibm.com/learning/en/courses/fundamentals-of-quantum-algorithms/grover-algorithm/number-of-iterations)</sup>

## Optimality and parallelization

Boyer, Brassard, Høyer, and Tapp established a tight lower bound on quantum searching, and Christof Zalka improved it to a matching bound, showing that for any success probability Grover's algorithm is exactly, not just asymptotically, optimal; for near-certain success the oracle must be queried about \( \frac{\pi}{4}\sqrt{N} \) times.<sup>[4](https://arxiv.org/abs/quant-ph/9711070)</sup> Zalka also showed that quantum searching cannot be parallelized better than by assigning different parts of the search space to independent quantum computers.<sup>[4](https://arxiv.org/abs/quant-ph/9711070)</sup> This quadratic speedup is therefore the best achievable for unstructured search on a quantum computer.<sup>[10](https://www.sciencedirect.com/science/article/pii/S0377221725001705)</sup>

## Generalizations

**Amplitude amplification.** Brassard, Høyer, Mosca, and Tapp generalized Grover's algorithm in 2000. Given a quantum algorithm \( \mathcal{A} \) that produces a good element with probability a, amplitude amplification finds one after an expected number of applications of \( \mathcal{A} \) and \( \mathcal{A}^{-1} \) proportional to \( 1/\sqrt{a} \), compared with an expected 1/a repetitions of the classical procedure; it works whether or not a is known in advance.<sup>[5](https://arxiv.org/abs/quant-ph/0005055)</sup> In this framework Grover's algorithm is the special case where \( \mathcal{A} \) produces an equal superposition and exactly one solution is promised.<sup>[5](https://arxiv.org/abs/quant-ph/0005055)</sup> The same group showed that the quadratic speedup extends to a large family of search problems with good classical heuristics, and combined ideas from Grover's and Shor's algorithms into amplitude estimation, applied to approximate counting.<sup>[5](https://arxiv.org/abs/quant-ph/0005055)</sup>

**Flexible state preparation.** In the Qiskit implementation, the state preparation \( \mathcal{A} \) need not be a layer of Hadamard gates, which is what distinguishes amplitude amplification from plain Grover search.<sup>[11](https://docs.quantum.ibm.com/api/qiskit/qiskit.circuit.library.GroverOperator)</sup> When the number of solutions is unknown, the algorithm tries different powers of the Grover operator and checks after each whether a good state was measured.<sup>[2](https://quantum.cloud.ibm.com/docs/en/api/qiskit/0.46/qiskit.algorithms.Grover)</sup>

## Hardware demonstrations

Small instances of the algorithm have been run on several platforms. A complete three-qubit Grover search was performed on a chain of five trapped \( ^{171}\mathrm{Yb}^{+} \) ions in 2017, using both a phase oracle and a Boolean oracle with an ancilla qubit.<sup>[7](https://www.nature.com/articles/s41467-017-01904-7)</sup> For the single-solution case the theoretical algorithm success probability is 78.1%, against 25% for the optimal classical strategy of one query followed by a random guess; the measured average was 38.9% for Boolean oracles and 43.7% for phase oracles, both above the classical 25%.<sup>[7](https://www.nature.com/articles/s41467-017-01904-7)</sup> In the two-solution case the theoretical quantum success probability is 100% versus about 46.4% classically, with measured averages of 67.9% and 75.3%.<sup>[7](https://www.nature.com/articles/s41467-017-01904-7)</sup> A four-qubit silicon spin processor executed the algorithm on three nuclear spin qubits with a (94.57 ± 2.63)% average success probability.<sup>[6](https://www.nature.com/articles/s41565-024-01853-5)</sup> Grover search has also been implemented on superconducting architectures, spin qubits in silicon, molecules using NMR techniques, and trapped-ion qudits.<sup>[12](https://www.nature.com/articles/s41467-026-68533-x)</sup><sup> • </sup><sup>[13](https://www.nature.com/articles/s41467-026-68746-0)</sup>

## Practical limits

The speedup is a query-model result: it counts only calls to the oracle and treats the oracle's internal structure as a black box.<sup>[14](https://doi.org/10.1103/PhysRevX.14.041029)</sup> Several conditions limit real-world use.

**Oracle cost and structure.** Grover's algorithm has no a priori quantum speedup once one is given access to the source code of the oracle, which may reveal internal structure of the problem; Stoudenmire and Waintal constructed a quantum-inspired classical algorithm that performs Grover's task for Boolean satisfiability problems in a linear number of oracle simulations, exponentially fewer than Grover's approximately \( \sqrt{2^{n}} \) calls.<sup>[14](https://doi.org/10.1103/PhysRevX.14.041029)</sup>

**Noise.** The speedup can only be guaranteed in a fault-tolerant regime where circuits run with negligible noise.<sup>[15](https://www.mdpi.com/2673-8392/6/4/89)</sup> Because the oracle and diffusion operator rely on multi-controlled Z gates whose two-qubit gate depth increases sharply as the qubit count rises, Grover's algorithm is in essence suited to fault-tolerant execution.<sup>[16](https://qiskit.qotlabs.org/docs/tutorials/grovers-algorithm)</sup> In the presence of noise, the success probability decays as the exponential of the exponential of the number of qubits, which makes a practical speedup unrealistic even under optimistic hardware assumptions, according to the Phys. Rev. X analysis.<sup>[14](https://doi.org/10.1103/PhysRevX.14.041029)</sup>

**Data access.** To search a database, the data must be stored in quantum-accessible memory and accessible in superposition; for superpolynomial-query algorithms like Grover search, the quantum random-access memory requires error-corrected components.<sup>[15](https://www.mdpi.com/2673-8392/6/4/89)</sup><sup> • </sup><sup>[17](https://pmc.ncbi.nlm.nih.gov/articles/PMC5806018/)</sup> Empirical studies that combine classical emulation with detailed complexity bounds have found that some classical heuristic algorithms did not offer significant quantum speedups despite a theoretical per-step speedup.<sup>[18](https://quantum-journal.org/papers/q-2023-10-10-1133/)</sup>

## References

1. [Lov K. Grover (1996). A fast quantum mechanical algorithm for database search. arXiv:quant-ph/9605043; STOC 1996, pp. 212–219.](https://arxiv.org/abs/quant-ph/9605043)
2. [Grover (v0.46), Qiskit API documentation, IBM Quantum](https://quantum.cloud.ibm.com/docs/en/api/qiskit/0.46/qiskit.algorithms.Grover)
3. [Choosing the number of iterations, Fundamentals of Quantum Algorithms, IBM Quantum Learning](https://quantum.cloud.ibm.com/learning/en/courses/fundamentals-of-quantum-algorithms/grover-algorithm/number-of-iterations)
4. [Christof Zalka (1997). Grover's quantum searching algorithm is optimal. arXiv:quant-ph/9711070; Phys. Rev. A 60, 2746 (1999).](https://arxiv.org/abs/quant-ph/9711070)
5. [Gilles Brassard, Peter Høyer, Michele Mosca, Alain Tapp (2000). Quantum Amplitude Amplification and Estimation. arXiv:quant-ph/0005055.](https://arxiv.org/abs/quant-ph/0005055)
6. [Grover's algorithm in a four-qubit silicon processor above the fault-tolerant threshold, Nature Nanotechnology (2024)](https://www.nature.com/articles/s41565-024-01853-5)
7. [Figgatt, C., Maslov, D., Landsman, K.A. et al. (2017). Complete 3-Qubit Grover search on a programmable quantum computer. Nature Communications 8, 1918.](https://www.nature.com/articles/s41467-017-01904-7)
8. [Grover's algorithm, Utility-Scale Quantum Computing course, IBM Quantum Learning](https://quantum.cloud.ibm.com/learning/en/courses/utility-scale-quantum-computing/grovers-algorithm)
9. [Grover's algorithm, IBM Quantum Learning module](https://quantum.cloud.ibm.com/learning/en/modules/computer-science/grovers)
10. [Speeding up Grover's algorithm, Computers & Operations Research / ScienceDirect (2025)](https://www.sciencedirect.com/science/article/pii/S0377221725001705)
11. [GroverOperator, Qiskit circuit library documentation, IBM Quantum](https://docs.quantum.ibm.com/api/qiskit/qiskit.circuit.library.GroverOperator)
12. [Demonstration of measurement-free universal logical quantum computation, Nature Communications (2026)](https://www.nature.com/articles/s41467-026-68533-x)
13. [Efficient implementation of a quantum algorithm with a trapped ion qudit, Nature Communications (2026)](https://www.nature.com/articles/s41467-026-68746-0)
14. [E. M. Stoudenmire, Xavier Waintal (2024). Opening the Black Box inside Grover's Algorithm. Phys. Rev. X 14, 041029.](https://doi.org/10.1103/PhysRevX.14.041029)
15. [Grover Quantum Algorithm: Applications and Limits, Engineering (MDPI, 2024)](https://www.mdpi.com/2673-8392/6/4/89)
16. [Grover's algorithm tutorial, Qiskit documentation](https://qiskit.qotlabs.org/docs/tutorials/grovers-algorithm)
17. [Quantum machine learning: a classical perspective, Quantum Science and Technology / PMC](https://pmc.ncbi.nlm.nih.gov/articles/PMC5806018/)
18. [Cade, C., Folkertsma, M., Niesen, I., Weggemans, J. (2023). Quantifying Grover speed-ups beyond asymptotic analysis. Quantum 7, 1133.](https://quantum-journal.org/papers/q-2023-10-10-1133/)

---
*Topic: Encyclopedia › Physical world and mathematics › Physics › Quantum physics › Quantum information science › Quantum computing and algorithms › Quantum algorithms › Quantum search and amplitude amplification*

*Initially written Sep 17, 2026 · Reviewed: Sep 17, 2026; Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license