Grover’s algorithm’s amplitude amplification

The easiest way to understand it is with a tiny example rather than equations.

Let’s use 4 possible records.

00 → Record A
01 → Record B
10 → Record C   ← FRAUD
11 → Record D

We want to find Record C.

Start with equal probability

00 → 25%
01 → 25%
10 → 25%  ← target
11 → 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.5
01 → +0.5
10 → +0.5   ← target
11 → +0.5

the oracle changes the target:

00 → +0.5
01 → +0.5
10 → -0.5   ← marked
11 → +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.5
average = +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 →  0
01 →  0
10 → +1.0   ← target
11 →  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: