一言でいうと
Provides a provable quadratic speedup for searching an unstructured space — the second foundational quantum algorithm.
要点
- ▸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.
やさしい解説
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.
なぜ重要か
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.
関連用語
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.