A mathematical framework for maze solving using quantum walks
| Autor: | Matsuoka, Leo, Ohno, Hiromichi, Segawa, Etsuo |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We provide a mathematical framework for identifying the shortest path in a maze using a Grover walk, which becomes non-unitary by introducing absorbing holes. In this study, we define the maze as a network with vertices connected by unweighted edges. Our analysis of the stationary state of the Grover walk on finite graphs, where we strategically place absorbing holes and self-loops on specific vertices, demonstrates that this approach can effectively solve mazes. By setting arbitrary start and goal vertices in the underlying graph, we obtain the following long-time results: (i) in tree structures, the probability amplitude is concentrated exclusively along the shortest path between start and goal; (ii) in ladder-like structures with additional paths, the probability amplitude is maximized near the shortest path. Comment: 19 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|