En une phrase
Provides a provable quadratic speedup for searching an unstructured space — the second foundational quantum algorithm.
Points clés
- ▸Finds a marked item among N possibilities in about √N steps instead of N.
- ▸Works by amplitude amplification: repeatedly boosting the target state's probability.
- ▸Proven optimal — no quantum algorithm can search unstructured data faster.
En langage simple
Imagine looking for one name in an unsorted phone book of a million entries. Classically you might check half a million on average. Grover's algorithm lets a quantum computer find it in roughly a thousand steps by nudging the probability toward the right answer a little on each round until measuring almost always returns it. The speedup is 'only' quadratic, not exponential, but it applies to an enormous range of search and optimization problems.
Pourquoi c'est important
Grover's algorithm generalizes far beyond database search to any brute-force problem, and it halves the effective key length of symmetric ciphers, informing modern cryptographic key-size recommendations.
Termes du glossaire associés
Grover's Algorithm
AlgorithmsA quantum search algorithm that finds a marked item in an unsorted list quadratically faster than any classical algorithm.
Hadamard Gate
GatesThe H gate — creates an equal superposition of |0⟩ and |1⟩ from a basis state.
Measurement
FundamentalsThe act of observing a qubit's state, which collapses the superposition to a definite 0 or 1.