Skip to main content
Glossary

Quantum glossary

Grover's algorithm

Also: grover search, amplitude amplification

A quantum algorithm that finds a marked item among N in about √N queries, where classical search needs about N.

It works by repeatedly rotating the state towards the marked item. It is a rotation, not a convergence: run too many iterations and you rotate past the answer. The quadratic speedup is provably optimal for unstructured search.

≈ (π/4)√N iterations

See it for yourself

Related terms

  • Oracle — A subroutine that encodes the problem, often by flipping the phase of the states that are solutions.
  • Interference — Amplitudes for the same outcome adding up (constructive) or cancelling (destructive).