Grover search and amplitude amplification

Algorithms and benchmarks / Search

Finds a marked item among N possibilities with about the square root of N checks instead of about N. Amplitude amplification generalises the idea to speed up any procedure that succeeds with some probability.

Era: Fault-tolerant
Problem class: Search
Area: Quantum computing and simulation
Speedup: Quadratic: O(square root of N) oracle calls instead of about N/2 for a classical search with 50% success (Grover 1996); the speedup is provably optimal for unstructured search.

How it works

A uniform superposition over all candidates is prepared; an oracle flips the sign of the marked items and a reflection about the average boosts their amplitude. Repeating these two steps about the square root of N times makes a marked item likely to be measured.

Typical use cases

Subroutines in optimisation, constraint satisfaction and cryptanalysis of symmetric ciphers, where it halves the effective key length.

Resource estimates

No resource estimate with stated assumptions was verified for this family in this release.

Demonstrations

2017: Complete three-qubit Grover search on trapped ions, with Toffoli gate process fidelities of 89.6% (three qubits) and 70.5% (four qubits) and better-than-classical success in every case. (C. Figgatt et al. 2017)

Hardware platforms that fit

Trapped ions: A complete three-qubit Grover search ran on trapped atomic ions (Figgatt et al. 2017).
Superconducting qubits: Grover search is one of the circuits of the QED-C application-oriented benchmark suite, run across gate-based devices (QED-C repository).

What you need to run it

Classical simulation: A state-vector simulator holds 2^n complex amplitudes, so memory doubles with every qubit: about 30 qubits fit in 16 GiB at double precision. Circuits with little entanglement can go further with tensor-network methods. See the guide for the calculator.
Noisy hardware (NISQ): Only a few qubits: the circuit depth grows with the square root of N and the oracle, so noise quickly washes out the signal.
Fault-tolerant machine: Useful sizes need error-corrected logical qubits and fast logical gates; see the limitation on quadratic speedups.
Annealer or analogue simulator: Not applicable for this family.

Calculate the memory of a simulation

Where to run it in Europe

Trapped ions

Piast-Q (Poland; Inaugurated, per the EuroHPC JU): Trapped ions; digital quantum computer. Access: EuroHPC JU call for quantum access in pilot mode. Deployment milestones Piast-Q
LRZ Quantum Integration Centre (QIC) (Germany; In operation, per the source): Superconducting systems from IQM (54 qubits, up to 150 in future), a 20-qubit AQT ion-trap system, and a neutral-atom system being developed by planqc (MAQCS project). Access: LRZ quantum computing consulting.

Superconducting qubits

VLQ (Czechia; Inaugurated, per the EuroHPC JU): Superconducting; digital quantum computer. Access: EuroHPC JU call for quantum access in pilot mode. Deployment milestones VLQ
Euro-Q-Exa (Germany; Inaugurated, per the EuroHPC JU): Superconducting; digital quantum computer. Access: EuroHPC JU call for quantum access in pilot mode. Deployment milestones Euro-Q-Exa
EuroQCS-Spain (Spain; Inaugurated, per the EuroHPC JU): Superconducting annealing; analogue quantum computer. Access: EuroHPC JU call for quantum access in pilot mode. Deployment milestones EuroQCS-Spain
Quantum Inspire (Netherlands; In operation, per the source): Online platform with superconducting transmon QPUs, a neutral-atom emulator and simulators; a Spin-2+ electron spin QPU is listed as archived. Access: Quantum Inspire registration.
LRZ Quantum Integration Centre (QIC) (Germany; In operation, per the source): Superconducting systems from IQM (54 qubits, up to 150 in future), a 20-qubit AQT ion-trap system, and a neutral-atom system being developed by planqc (MAQCS project). Access: LRZ quantum computing consulting.
Finnish Quantum-Computing Infrastructure (FiQCI) (Finland; In operation, per the source): Hybrid HPC and quantum computing platform: VTT Q50 (53 qubits) and Aalto Q20 (20 qubits), superconducting systems made by IQM, used through the LUMI supercomputer environment. Access: FiQCI calls for academic projects.
Quantum Spain quantum computer at BSC-CNS (Spain; In operation, per the source): Superconducting; digital quantum computer with a 35-qubit processor, integrated into the MareNostrum 5 supercomputer. Access: Spanish Supercomputing Network (RES) quantum access. Deployment milestones Quantum Spain quantum computer at BSC-CNS

The full infrastructure catalogue · The infrastructure deployment tracker

Software

European tools in the software directory

Other open-source frameworks

Qiskit (IBM (United States); non-European)
Cirq (Google Quantum AI (United States); non-European)

A listing is not an endorsement; check each tool for the features you need.

Limitations and open questions

Babbush et al. (2021) conclude that quadratic speedups are unlikely to give an advantage on early fault-tolerant machines unless error correction improves significantly, even with logical gates more than ten times faster.
The oracle must be built as a reversible circuit; its cost usually dominates and is often ignored in headline claims.

In the Quantum Algorithm Zoo

Searching (Quantum Algorithm Zoo, external site): Oracular Algorithms; speedup as the Zoo states it: Polynomial

Index: the Quantum Algorithm Zoo by Stephen P. Jordan, last updated 2026-09-10, checked 2026-10-23. The portal links to it and copies no description from it. Browse the full Quantum Algorithm Zoo (external site)

Named in European procurements

Used in: EuroHPC procurement MeluXina-Q (Required in the benchmark suite (scored under the award criteria))

As the tender documents state; how a benchmark is weighted against others is described in each procurement.

Sources

L. K. Grover (1996). A fast quantum mechanical algorithm for database search. Proceedings of the 28th ACM Symposium on Theory of Computing (1996); arXiv:quant-ph/9605043. Read: abstract page, retrieved 2026-10-23.
G. Brassard, P. Høyer, M. Mosca, A. Tapp (2002). Quantum Amplitude Amplification and Estimation. AMS Contemporary Mathematics 305, 53 (2002); arXiv:quant-ph/0005055. Read: abstract page, retrieved 2026-10-23.
R. Babbush, J. McClean, M. Newman, C. Gidney, S. Boixo, H. Neven (2021). Focus beyond quadratic speedups for error-corrected quantum advantage. PRX Quantum 2, 010103 (2021); arXiv:2011.04149. Read: abstract page, retrieved 2026-10-23.
C. Figgatt et al. (2017). Complete 3-Qubit Grover Search on a Programmable Quantum Computer. Nature Communications 8, 1918 (2017); arXiv:1703.10535. Read: abstract page, retrieved 2026-10-23.