3. Amplification: Grover’s Algorithm

Grover’s Algorithm

Imagine you have a phone book with $N$ names, but it's not alphabetized. You want to find a specific number.

• Classical Search: You have to look through them one by one. On average, you check $N/2$ entries.
• Quantum Search: Grover's Algorithm can find it in roughly $\sqrt{N}$ steps.

If $N = 1,000,000$, a classical computer checks 500,000 times. A quantum computer checks 1,000 times.

How it works: It uses a process called Amplitude Amplification. It repeatedly rotates the state vector towards the correct answer, increasing its probability while decreasing the probability of wrong answers.