← Quantum Store · Guides · Lessons · Glossary · About · Türkçe
What is Grover’s algorithm?
Grover’s algorithm finds a marked item among N unsorted items in about √N steps, a quadratic speed-up over classical search.
A classical computer looks at N/2 items on average to find what it is looking for in an unsorted list. Grover’s algorithm does it in about (π/4)·√N “queries”. In each step an oracle flips the sign of the marked item and a diffusion step amplifies its amplitude through interference.
In the two-qubit (four-option) example a single Grover step finds the right answer with 100% probability. Because the speed-up is quadratic, Grover is less a way to break symmetric ciphers than a reason to double key lengths.
Try it yourself
The lesson Your first algorithm: Grover search lets you try this concept in the browser, with no installation.
Related packages
- İlk kuantum algoritmaları: Deutsch-Jozsa ve Bernstein-Vazirani
- Qiskit başlangıç paketi
- Qrisp ile yüksek seviyeli kuantum programlama
Related concepts
- Quantum interference · Quantum interference is the way amplitudes add up like waves, raising the probability of some results and cancelling others to zero.
- Shor’s algorithm · Shor’s algorithm factors large numbers exponentially faster than known classical methods, which is why it threatens RSA encryption.
- Quantum circuit · A quantum circuit is a quantum program made of gates applied to qubits in order, followed by measurements.