Skip to content
ExperimentsExperiment 6 · Quantum search

Grover's Search — The Maze

The signature experiment: classical explorer vs amplitude amplification.

  1. 1. Learn
  2. 2. Watch
  3. 3. Interact
  4. 4. Predict
  5. 5. Run
  6. 6. Observe
  7. 7. Record
  8. 8. Answer
  9. 9. Research
① What is the problem?

Find the one marked room among 100 candidates, with no structure to guide you.

② How does a classical computer approach it?

Check candidates one by one. On average about N/2 = 50 checks, up to 100 in the worst case: O(N).

③ How does the quantum approach differ?

Prepare a superposition over 128 basis states, then repeat Oracle + Diffusion ≈ (π/4)√128 ≈ 8 times; measurement then gives the target with ≈99.6% probability: O(√N) oracle queries.

🎨 Visual metaphor
🎨 Visual metaphor🧮 Data: in-browser statevector1024 rooms = 1024 candidates = 2¹⁰ basis states (10 qubits). Target = the EXIT ★.

Normal Search

search space

Quantum Search

superposition

step 1/270
Normal: rooms checked
1 / 1024
Grover iteration (oracle queries)
0 / 25
P(target) — simulated
0.10%
Measurements ★ / ✕
0 / 0

What the animation means

  • Orange flood (superposition): every one of the 1024 rooms gets the same amplitude, 1/32. Drawn as a wave for drama — in reality all amplitudes are set at once by 10 Hadamard gates; nothing travels down corridors.
  • Oracle (purple ring): flips the sign of the exit's amplitude.
  • Interference (green path brightening): each diffusion moves amplitude to the target. The flood's brightness is √(1−P) and the green path's is √P, with P taken from the simulation.
  • Measurement: one room is sampled from the real probabilities — ≈99.95% chance of the exit after 25 queries, vs ~512 checks on average for the normal search.

P(target) vs Grover iteration (10 qubits)

00.250.50.75103691215182124iterationP(target)Simulated: x=0, y=0Simulated: x=1, y=0.01Simulated: x=2, y=0.02Simulated: x=3, y=0.05Simulated: x=4, y=0.08Simulated: x=5, y=0.11Simulated: x=6, y=0.16Simulated: x=7, y=0.2Simulated: x=8, y=0.26Simulated: x=9, y=0.31Simulated: x=10, y=0.37Simulated: x=11, y=0.43Simulated: x=12, y=0.5Simulated: x=13, y=0.56Simulated: x=14, y=0.62Simulated: x=15, y=0.68Simulated: x=16, y=0.74Simulated: x=17, y=0.79Simulated: x=18, y=0.84Simulated: x=19, y=0.88Simulated: x=20, y=0.92Simulated: x=21, y=0.95Simulated: x=22, y=0.97Simulated: x=23, y=0.99Simulated: x=24, y=1Simulated: x=25, y=1
Simulated
Grover is NOT…
…“trying every answer simultaneously and reading all the answers.” A measurement only ever returns one classical result.
Grover IS…
…using quantum superposition, an oracle and interference to increase the probability of measuring a desired solution. It needs about √N oracle queries (O(√N)) vs O(N) classically, for unstructured search.
Honest fine print
  • The oracle must be constructed as a circuit — here it is built by the simulator.
  • Measurement gives a classical outcome; success is probable (≈99.6%), not guaranteed.
  • A simulator running on a normal computer is not a quantum computer and shows no physical speedup.
  • Real hardware has noise and errors (see Experiments 11–12).
  • Not every problem gets a Grover speedup — sorted data is already fast classically.
Why 7 qubits for 100 rooms?
Qubit registers have 2ⁿ basis states. 2⁶ = 64 is too few, 2⁷ = 128 is enough: states 0–99 are valid candidates, 100–127 are unused. They still share the superposition — if measurement lands there, we simply run again.
④ What is happening mathematically?
sin θ = √(M/N). After k iterations P(success) = sin²((2k+1)θ). Optimal k = ⌊π/(4θ)⌋.
⑤ What does the simulation show?
The maze is a visual metaphor for the search space. Classical mode: a real sequential exploration. Quantum mode: each room glows with its actual simulated probability.
⑥ What did we learn?
Grover doesn't try every answer and read them all; it uses interference to make the right answer likely to be measured.
⑦ What can you experiment with?
Pause the quantum mode after each oracle. Why do probabilities not change at the oracle step?
📓 Record: my lab notebook