UQC

Quantum Search

Grover's Algorithm

The Search Problem

Imagine you have an unsorted database of N items and need to find one specific item that satisfies some condition. Classically, you might need to check all N items in the worst case.

Grover's algorithm finds the answer in approximately √N steps, a quadratic speedup. For 1 million items, that's 1,000 steps instead of 1,000,000.

The Speedup

O(N)
Classical
O(√N)
Grover's

See It In Action

Watch the Oracle mark the target with a phase flip, then see the Diffusion operator amplify it by reflecting all amplitudes about their mean.

How It Works

Oracle, Mark
Recognize the answer and flip its phase.Put a negative flag on the solution.
Diffusion, Amplify
Reflect amplitudes about their mean.The marked one grows. Others shrink.

What You're Seeing

Oracle: Marks the target by flipping its amplitude negative (phase flip).

Diffusion: Reflects all amplitudes about their mean, the target pops up while others shrink.

Result: After 3 iterations, the target has ~96% probability of being measured. Classical search would need ~8 checks on average.

Grover's Algorithm Visualized

Watch the quantum search algorithm find a target in √N steps

Grover's Algorithm

Iteration 0 / 3
ORACLE

Mark target with negative phase

DIFFUSION

Reflect amplitudes about mean

Database Search

Target: |0111⟩(item 7)
Target Probability:
6.3%

Click any cell to set as search target

Geometric View

Angle: 14.5°
|s'⟩|t⟩start|ψ⟩θ

State vector rotates ~29° per iteration

|t⟩ = target, |s'⟩ = other states

Quantum Amplitudes

Target
Others
Negative
+1+0.50-0.5-1
|0000⟩
6%
|0001⟩
6%
|0010⟩
6%
|0011⟩
6%
|0100⟩
6%
|0101⟩
6%
|0110⟩
6%
|0111⟩
6%
|1000⟩
6%
|1001⟩
6%
|1010⟩
6%
|1011⟩
6%
|1100⟩
6%
|1101⟩
6%
|1110⟩
6%
|1111⟩
6%
Speed:
Space Play/Pause→ Next StepR ResetG Toggle Geometric

Step by Step

Initialize
All qubits in superposition.
Apply Oracle
Flip the phase of the solution.
Apply Diffusion
Reflect amplitudes about the mean. The solution grows.
Repeat
About √N times. Each pass, the right answer gets louder.
Measure
Correct answer is now overwhelmingly likely.

What does "reflection" mean?

A mirror placed at the mean.

The diffusion operator performs a reflection about the mean. Each amplitude bounces to the opposite side of the mean, the same distance away.

Before Diffusion

mean
0.219
others
+0.25
target
-0.25

After Diffusion

mean
0.219
others
+0.188 shrunk
target
+0.688 grew

Formula

new = 2 × mean − old

Think of it like a mirror at the mean. The target was far below; it bounces way above. The others were just slightly above; they drop just slightly below.

The circuit behind it

Both operators built from gates you already know.

Oracle Circuit

Flips the phase of the target state. For a specific target, this is a multi-controlled Z gate that activates only when all qubits match the target pattern.

If target = |1001⟩: Apply Z when q0=1, q1=0, q2=0, q3=1

Diffusion Circuit

  1. 1H on all qubits, exit superposition basis
  2. 2X on all qubits, flip bits
  3. 3Multi-controlled Z, phase flip |11...1⟩
  4. 4X on all qubits, flip back
  5. 5H on all qubits, return to superposition

Key Insight

The diffusion operator is H⊗n · (2|0⟩⟨0| − I) · H⊗n. The Hadamards transform to/from the computational basis, and the middle part flips the phase of |00...0⟩. Together: "reflection about the mean."

Hands-on exercise

20 minutes

Goal , Implement Grover's search algorithm and observe quantum speedup.

Open in Google Colab

Reflection

  1. 01Why does Grover's algorithm provide a quadratic speedup instead of an exponential one?
  2. 02In what real-world scenarios might a quadratic speedup be practically significant?
PreviousQuantum CircuitsNextCapstone Project