Can a quantum walk reach the exit sooner?

Watch one run through the maze

Quantum circles show the state conditioned on no earlier exit detection; larger circles mean greater probability. Arrows show outgoing coin probability before the shift. Only the exit is measured. A seeded detector samples the first-exit distribution calculated by NexQus; detection collapses the display onto G. The classical dot follows a seeded random trajectory, including blocked moves that stay put. Playback pauses are illustrative.

A run may fail to exit within the simulated step limit. Use a larger --steps value (up to 128) or another seed. The animation stops at detection or the limit; it never invents a successful route.

What is happening?

1. State: amplitudes describe a maze cell and one of four directional ports: right, down, left, up. Start at S with equal port amplitudes.
2. Coin: at each cell, the four-port Grover coin maps amplitude a to 2 × the local port mean − a. This is a small mixing operation, not the earlier global Grover route search.
3. Shift: move each port amplitude across its open edge into the opposite port. A blocked port stays at its cell. Opposite amplitudes can reinforce or cancel in the next coin step.
4. Detector: after each shift, measure only “at G or elsewhere?” Detected probability is removed and accumulated. The remaining branch keeps its coherence. No intermediate full-position measurements are made.
5. Classical baseline: replace amplitudes by probabilities and remove phase coherence after every operation. Since every squared coin entry is ¼, choose each port with probability ¼; blocked choices stay put. Apply exactly the same exit detector.

This measures arrival probability, not a recovered route. A position measurement does not reveal the walk's history. BFS returns the actual shortest route. No plan enumeration or valid-route oracle is used here; both walks know the grid.

Playback delay is only for teaching; CPU timings below exclude animation. Click a cell to inspect its port amplitudes.

Inside the selected cell

Amplitude values retain the weight of the undetected branch. The SDK internally normalizes that branch for execution, then restores its probability weight. Detecting only the exit differs from measuring every cell each step.

Exit detection over all steps

Blue: quantum. Orange: classical walk. Fixed 0–100% vertical scale. The entire chosen horizon is shown, including reversals in which method leads. No best-step selection.

Work and measured time

Quantum walk steps, BFS queue visits and CPU milliseconds are different units. Each walk step uses two logical SDK operations: coin and shift. The shift is a grid-derived permutation, not a hardware-native gate decomposition. Initialization and exit projection are not included in that two-operation count. No end-to-end BFS speedup or QPU speedup is established.

Where quantum advantage can occur

There are proven quantum-walk speedups for specially constructed black-box graph problems. That result does not establish an advantage on an ordinary known grid. This report tests a particular four-port walk with reflecting walls and repeated exit detection; it is not a reproduction of a welded-tree algorithm or a stationary-state maze path-extraction algorithm.

References: Childs et al.: exponential algorithmic speedup by quantum walk; Matsuoka et al.: maze solving using quantum walks. The latter uses a different absorbing-hole/self-loop construction.