The easiest way to understand it is with a tiny example rather than equations.
Let’s use 4 possible records.
00 → Record A01 → Record B10 → Record C ← FRAUD11 → Record D
We want to find Record C.
Start with equal probability
00 → 25%01 → 25%10 → 25% ← target11 → 25%
So if we measured immediately, we have only a 25% chance of finding the fraud.
Oracle marks the target
The oracle knows the condition:
if transaction == fraud: mark it
But “mark” in quantum computing means something specific: it flips the phase of that state’s amplitude.
Initially think of the amplitude as:
00 → +0.501 → +0.510 → +0.5 ← target11 → +0.5
the oracle changes the target:
00 → +0.501 → +0.510 → -0.5 ← marked11 → +0.5
Now comes amplitude amplification
Grover applies another operation called the diffusion operator – “Look at all the amplitudes and reflect them around their average.”
Before amplification:
amplitudes:+0.5+0.5-0.5 ← target+0.5average = +0.25
Now reflect each amplitude around +0.25
For target
+0.25 │ │-0.5 ───────→ +1.0
for other
+0.5 → 0
So after the diffusion step, conceptually:
00 → 001 → 010 → +1.0 ← target11 → 0
when we measure – we get the desired result with very high probability.
So what exactly is “amplitude amplification”?
ORACLE
↓
Mark the target
by changing phase
↓
DIFFUSION
↓
Increase target amplitude
decrease other amplitudes
↓
REPEAT
↓
Target probability ↑in case if you are finding fraud transaction our of 1-million-record example(example we discussed in previous article)
Initially:
1,048,576 states ↓all have tiny, roughly equal amplitudes
Then grover repeatedly performs
Oracle ↓Diffusion ↓Oracle ↓Diffusion ↓Oracle ↓Diffusion ↓...
After approximately:
iterations, the target’s probability becomes very high.
For N=1,048,576:
So roughly 800 iterations, rather than around one million classical searches.
Let us understand why π/4 ? from where this magic number came into ?
Think of the quantum state as an arrow, Grover’s algorithm can be visualized as rotating an arrow toward the correct answer.
Initially, if there are N possibilities and only 1 correct answer, the arrow is almost completely pointing toward the “wrong answers.”
Each Grover iteration rotates the arrow a little bit toward the correct state. How big is that rotation? For one correct answer among N possibilities, the initial amplitude of the correct answer is:
We can represent this using an angle θ:
For large N this means
Each Grover iteration rotates the state by approximately: 2θ
So after k iterations, we’ve rotated approximately: 2kθ
The correct direction corresponds to:
So we want:
So
And
Since:
we get:
