Playground

探索 Grover's Search

Quantum search algorithm - O(√N) vs classical O(N)

Amplitude Distribution

Iteration 0 / ~2 optimal
Target probability: 0.0%

Classical vs Quantum Search

Classical (Linear)
0
1
2
3
4
5
6
7
Steps: - / avg 4
Quantum (√N)
0
1
2
3
4
5
6
7
Iterations: 0 / ~2 optimal

Target Item

Select the item to search for

Grover's Algorithm

How it works

  • • Start with uniform superposition
  • • Oracle marks the target (phase flip)
  • • Diffusion amplifies marked states
  • • Repeat ~√N times
  • • Measure to find target with high probability
Speedup: O(√N) vs O(N)

Why O(√N)? The Math Behind the Magic

1. Superposition

|ψ⟩ = (1/√N) Σ |i⟩

All N items exist simultaneously. Each has amplitude 1/√N.

2. Oracle (Mark Target)

|target⟩ → -|target⟩

Flips the phase of the target without collapsing superposition.

3. Diffusion (Amplify)

2|s⟩⟨s| - I

Reflects amplitudes around the mean. Target (negative) gets pushed higher.

Amplitude Growth per Iteration

Start:1/√N ≈ 0.354
Gain/iteration:~2/√N ≈ 0.707
Target:≈ 1.0
Iterations needed:≈ (π/4)√N ≈ 2

The Key Insight

Classical:Check items one by one → N queries
Quantum:Amplify target each pass → √N queries

It's like making the needle glow brighter with each pass through the haystack, instead of checking straw by straw.