Quantum Maze Solver with Scattering Quantum Walk

This script implements a discrete quantum walk on a maze represented as a grid of walls and paths. It uses a scattering walk model with Grover coins to explore all possible routes in superposition, then measures the probability of finding the walker at each cell after a number of steps. Here is how it works, in plain text:

1. Maze to Graph conversion

   • The maze is a 2D grid where 1 indicates an open path and 0 indicates a wall.

   • Each open cell is assigned a node index.

   • Any two open cells that share an edge become connected by an undirected graph edge.

   • We record mappings from grid coordinates to node indices and back so we can translate between maze positions and graph nodes.

2. Directed arcs and indexing

   • For every undirected edge (u, v) we create two directed arcs: one from u to v and one from v to u.

   • We give each directed arc a unique integer index.

   • The total number of arcs is twice the number of graph edges.

   • This allows us to work in the “arc space” where our quantum state lives, with dimension equal to the number of directed arcs.

3. Grover coin operator

   • At each graph node v with degree d, we apply a local unitary that mixes amplitudes evenly among all outgoing arcs from v.

   • In plain terms, the amplitude on each outgoing arc is reflected about the average: new amplitude = (2/d minus 1) times the old amplitude on the same arc, plus (2/d) times the amplitude on each different arc.

   • This local operation is assembled into a large sparse matrix C of size (num_arcs × num_arcs).

4. Shift operator

   • After the coin toss, the shift operation sends amplitude from each arc (u → v) to the reversed arc (v → u).

   • This is simply a permutation of the basis states in arc space, implemented as another sparse matrix S.

5. Evolution operator

   • A single time step consists of first applying the coin operator C, then the shift operator S.

   • The combined step operator U = S · C is unitary.

   • Repeated application of U evolves the quantum state through the maze in superposition.

6. Initial state

   • The walker starts at the designated START cell.

   • We find all outgoing arcs from the start node and assign equal amplitude 1/√d among them, where d is the start node’s degree.

   • All other arc amplitudes begin at zero.

7. Time evolution

   • We apply U repeatedly for a fixed number of steps (for example 30).

   • At each step we optionally record the state norm to verify unitarity (it should stay close to 1).

   • The state vector lives in arc space, but we’ll later project back to node space.

8. Position probabilities

   • To find the probability of the walker being at node v, we sum the squared magnitudes of amplitudes on all arcs that end at v.

   • This gives a nonnegative number at each graph node.

   • The total probability across all nodes remains 1 (up to numerical precision).

9. Exit probability

   • If the EXIT cell is reachable, we look up its node index and report the probability assigned to it after the final step.

   • A higher exit probability means the quantum walk better concentrates amplitude at the goal.

10. Visualization

11. Heatmap over the maze grid: walls are shown as a distinct low value, open cells are colored by their node probabilities.

12. Graph drawing: nodes placed at their grid coordinates, colored by probability, with a special highlight on the exit node.

13. Norm evolution plot: the norm of the state vector over time steps, with a reference line at 1 to check unitarity preservation.

Key points of this approach

• The Grover coin ensures equal mixing among outgoing directions, amplifying paths that revisit nodes constructively.

• The shift step propagates amplitude along edges of the maze.

• Unlike a classical random walk, the quantum walk can exploit interference, potentially achieving faster spreading or concentration at the exit.

• Final measurement yields a probability distribution that hints at the most promising routes through the maze.

You can experiment by changing the maze layout, the number of time steps, or the coin design. As you tweak parameters, watch how interference patterns shift and how the exit probability evolves. This simple framework scales to larger graphs and more sophisticated coins or initial states, offering a versatile playground for quantum walk algorithms.