Quantum Maze Explorer
Make a maze. Inspect the guesses. Watch interference change the odds.
1. Make your maze
How classical BFS works
Breadth-first search keeps a first-in, first-out queue. Remove the oldest cell, check its open neighbors in right/down/left/up order, and enqueue each unseen neighbor. Remember its parent. When G is removed, follow parents back to S: this guarantees a shortest path on this grid.
Coordinates start at (0, 0). Cyan cells are expanded; purple cells wait in the queue; the outlined cell is being processed. A visit is one queue removal, not one maze move.
What do the bits mean?
Each pair 00 / 01 / 10 / 11 picks an available, unvisited neighbor at a junction. Options are ordered right, down, left, up. A corridor follows automatically.
A plan can run out of choices, pick an unavailable option, or hit a dead end. After reaching G, unused pairs must be 00 so the same route is not counted repeatedly.
2. Explore the quantum search
Algorithm: Grover amplitude amplification. The qubits encode route instructions, not the maze position. This lesson uses gate-based search; it does not use quantum annealing or quantum walks.
- Encode: two bits per junction choice. Python checks every encoded plan and stores a valid/invalid truth table for the oracle.
- Superposition: Hadamard gates turn the all-zero register into equal amplitudes for all plans. Measuring now would give a uniformly random plan.
- Phase marking: the oracle negates valid-plan amplitudes. Squaring removes the sign, so this alone changes no probabilities.
- Interference: diffusion maps every signed amplitude a to 2 × mean − a. Marked amplitudes grow toward the optimal iteration count. Repeating too far reverses that gain.
- Measurement: one shot gives one bitstring with probability |a|². Decode it into a route; it can still fail. You cannot read all plans from a single measurement.
These circuits use real-valued gates. Negative amplitude means a relative phase of π; probability is amplitude squared. Each shot prepares the displayed stage again. The plots show its pre-measurement state, not a collapsed state.
| Plan | Oracle says | Moves | Probability |
|---|
3. Count the work honestly
These counts use different units. Python already checks every encoded plan to build the truth-table oracle. Corridor following is classical work. The oracle is one logical diagonal operation, not a reversible maze-checking gate decomposition. This project demonstrates amplitude amplification, not a laptop speedup over BFS.
BFS is complete on this grid and finds a shortest path. Grover searches only the encoded plans and does not minimize route length. More iterations can reduce success after the optimum.
Measured local time
This is laptop/server CPU simulation time, not quantum hardware time. The quantum total includes classical oracle construction. Both algorithms are warmed before measurement. Animated pauses and chart generation are excluded. One shot is probabilistic; BFS is deterministic. Fewer oracle calls do not mean fewer CPU operations or a faster maze solution.