Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Symmetry

Maze Solving by a Quantum Walk with Sinks and Self-Loops: Numerical Analysis

Leo Matsuoka, Kenta Yuki, Hynek Lavička, Etsuo Segawa

Published Nov 28, 2021• 3 citations
Publisher

Abstract

Maze-solving by natural phenomena is a symbolic result of the autonomous optimization induced by a natural system. We present a method for finding the shortest path on a maze consisting of a bipartite graph using a discrete-time quantum walk, which is a toy model of many kinds of quantum systems. By evolving the amplitude distribution according to the quantum walk on a kind of network with sinks, which is the exit of the amplitude, the amplitude distribution remains eternally on the paths between two self-loops indicating the start and the goal of the maze. We performed a numerical analysis of some simple cases and found that the shortest paths were detected by the chain of the maximum trapped densities in most cases of bipartite graphs. The counterintuitive dependence of the convergence steps on the size of the structure of the network was observed in some cases, implying that the asymmetry of the network accelerates or decelerates the convergence process. The relation between the amplitude remaining and distance of the path is also discussed briefly.

DOI
10.3390/sym13122263

Related papers

A mathematical framework for maze solving using quantum walks

Leo Matsuoka, Hiromichi Ohno, Etsuo Segawa

Abstract 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 truncated 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.

arXiv:2411.12191•Quantum Information Processing•Mar 17, 2025•2 citations

Finding more than one path through a simple maze with a quantum walk

Mark S. Hillery

Abstract We study quantum walks through chains consisting of two and three star graphs. The first star has a distinguished vertex labelled START and the last has one labelled END. There are multiple paths between these two vertices, and the object is to find these paths. We show that a quantum walk can do this with a quantum speedup.

arXiv:2007.07340•Journal of Physics A Mathematical and Theoretical•Jan 21, 2021•3 citations

Finding paths with quantum walks or quantum walking through a maze

Daniel Reitzner, Mark S. Hillery, Daniel Koch

We show that it is possible to use a quantum walk to find a path from one marked vertex to another. In the specific case of $M$ stars connected in a chain, one can find the path from the first star to the last one in $O(M\sqrt{N})$ steps, where $N$ is the number of spokes of each star. First we provide an analytical result showing that by starting in a phase-modulated highly superposed initial state we can find the path in $O(M\sqrt{N}logM)$ steps. Next, we improve this efficiency by showing that the recovery of the path can also be performed by a series of successive searches when we start at the last known position and search for the next connection in $O(\sqrt{N})$ steps leading to the overall efficiency of $O(M\sqrt{N})$. For this result we use the analytical solution that can be obtained for a ring of stars of double the length of the chain.

arXiv:1707.01581•Physical Review A•Sep 13, 2017•13 citations

Quantum-accelerated shortest path search on a graph in unsorted space

Паскаль Мишелевич Хури, Алина Дмитриевна Клишева, Petr Demchenko +3 more

Algorithms and data structures are important in information technology (particularly in 6G terahertz wireless communications), logistics, transportation, and route planning in medicine. One of the fundamental algorithms that find application in many practical problems is the shortest path algorithm. The shortest path algorithm is used to find the optimal route between two vertices while minimizing the length or number of intermediate nodes. This problem is one of the 21 NP-hard problems formulated by Richard Karp in 1972. It still poses a serious challenge to science, since there is no polynomial algorithm that can provide an exact solution to this problem. The article considers approaches to solving the problem of finding the shortest path on a graph, and discusses their advantages and disadvantages. Various algorithms, such as the Bellman-Ford algorithm, Dijkstra, and the A* algorithm, are considered; their efficiency and applicability in various situations are analyzed. Issues of optimization of shortest path algorithms are discussed, such as the use of heuristics, graph preprocessing, and other methods that can improve the performance and accuracy of algorithms. The article proposes an optimization of Dijkstra’s algorithm with quantum acceleration. The stability of the quantum algorithm and the magnitude of distortions in a circuit with a different number of qubits are estimated. It is shown that with an increase in the intensity of distortions, the probability of detecting the desired element decreases, and the time spent on its search increases. When using Grover’s algorithm to optimize a path in a quantum network, these interferences cause an increase in the time it takes to find the optimal path and an increase in the probability of choosing an incorrect route. It is shown that an increase in the number of qubits and, accordingly, the number of iterations makes the algorithm more stable. It is demonstrated that the stability of Grover’s algorithm for circuits with a large number of qubits has a similar nature. The work of quantum circuits on 9, 10 and 11 qubits, the difference in the probabilities of correct operation differs by less than 10–3. Thus, from the obtained dependencies, it is possible to predict the nature of such an influence on circuits with an even larger number of qubits, the stability of which cannot be studied due to the insufficient computing power of classical computers. The most efficient way to modify Dijkstra’s algorithm is to replace the priority queue in the classical version of the algorithm with some quantum data structure that finds the minimum element for the next iteration of the algorithm. Despite the fact that quantum search does not provide a potential gain in asymptotics, another quantum modification of Dijkstra’s algorithm can be used. Namely, instead of maintaining and searching for a minimum in the priority queue, use the quantum algorithm immediately to search for a vertex that needs to be added to the shortest path tree, which will additionally acceleration the graph traversal by Dijkstra’s algorithm.

Scientific and technical journal of information technologies mechanics and optics•Jul 9, 2026•0 citations

Finding paths in tree graphs with a quantum walk

Daniel Koch, Mark S. Hillery

We analyze the potential for different types of searches using the formalism of scattering random walks on quantum computers. Given a particular type of graph consisting of nodes and connections, a ``tree maze,'' we would like to find a selected final node as quickly as possible, faster than any classical search algorithm. We show that this can be done using a quantum random walk, both through numerical calculations as well as by using the eigenvectors and eigenvalues of the quantum system.

arXiv:1710.05084•Physical Review A•Jan 12, 2018•22 citations

Quantum Walk-Based Routing Protocols for Wireless Networks

Jincheng Zhang

This paper investigates the application of quantum walks to routing protocols within wireless networks. Traditional routing algorithms often struggle with efficiency and convergence speed, particularly in dynamic and complex network topologies. We propose a novel approach utilizing quantum walk principles to explore network connectivity and identify optimal routes. Our methodology employs a quantum walk algorithm to simulate network traversal, leveraging quantum superposition and interference to potentially achieve faster convergence and reduced latency compared to classical approaches. The core of the system relies on a discrete-time quantum walk on a graph representing the wireless network, where nodes are the walkers and edges represent communication links. The algorithm aims to minimize the walk length, effectively finding the shortest path between source and destination nodes. We present a theoretical framework and outline the key components of a quantum walk-based routing protocol. While this research focuses on the theoretical aspects and does not include experimental validation, it lays the foundation for future work exploring the practical feasibility and performance benefits of quantum walk routing in real-world wireless network scenarios.

•Aug 31, 2026•0 citations
Maze-solving by natural phenomena is a symbolic result of the autonomous optimization induced by a natural system. We present a method for finding the shortest path on a maze consisting of a bipartite graph using a discrete-time quantum walk, which is a toy model of many kinds of quantum systems. By evolving the amplitude distribution according to the quantum walk on a kind of network with sinks, which is the exit of the amplitude, the amplitude distribution remains eternally on the paths between two self-loops indicating the start and the goal of the maze. We performed a numerical analysis of some simple cases and found that the shortest paths were detected by the chain of the maximum trapped densities in most cases of bipartite graphs. The counterintuitive dependence of the convergence steps on the size of the structure of the network was observed in some cases, implying that the asymmetry of the network accelerates or decelerates the convergence process. The relation between the amplitude remaining and distance of the path is also discussed briefly.
Abstract 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 truncated 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.
We show that it is possible to use a quantum walk to find a path from one marked vertex to another. In the specific case of MMM stars connected in a chain, one can find the path from the first star to the last one in O(MN)O(M\sqrt{N})O(MN​) steps, where NNN is the number of spokes of each star. First we provide an analytical result showing that by starting in a phase-modulated highly superposed initial state we can find the path in O(MNlogM)O(M\sqrt{N}logM)O(MN​logM) steps. Next, we improve this efficiency by showing that the recovery of the path can also be performed by a series of successive searches when we start at the last known position and search for the next connection in O(N)O(\sqrt{N})O(N​) steps leading to the overall efficiency of O(MN)O(M\sqrt{N})O(MN​). For this result we use the analytical solution that can be obtained for a ring of stars of double the length of the chain.
Algorithms and data structures are important in information technology (particularly in 6G terahertz wireless communications), logistics, transportation, and route planning in medicine. One of the fundamental algorithms that find application in many practical problems is the shortest path algorithm. The shortest path algorithm is used to find the optimal route between two vertices while minimizing the length or number of intermediate nodes. This problem is one of the 21 NP-hard problems formulated by Richard Karp in 1972. It still poses a serious challenge to science, since there is no polynomial algorithm that can provide an exact solution to this problem. The article considers approaches to solving the problem of finding the shortest path on a graph, and discusses their advantages and disadvantages. Various algorithms, such as the Bellman-Ford algorithm, Dijkstra, and the A* algorithm, are considered; their efficiency and applicability in various situations are analyzed. Issues of optimization of shortest path algorithms are discussed, such as the use of heuristics, graph preprocessing, and other methods that can improve the performance and accuracy of algorithms. The article proposes an optimization of Dijkstra’s algorithm with quantum acceleration. The stability of the quantum algorithm and the magnitude of distortions in a circuit with a different number of qubits are estimated. It is shown that with an increase in the intensity of distortions, the probability of detecting the desired element decreases, and the time spent on its search increases. When using Grover’s algorithm to optimize a path in a quantum network, these interferences cause an increase in the time it takes to find the optimal path and an increase in the probability of choosing an incorrect route. It is shown that an increase in the number of qubits and, accordingly, the number of iterations makes the algorithm more stable. It is demonstrated that the stability of Grover’s algorithm for circuits with a large number of qubits has a similar nature. The work of quantum circuits on 9, 10 and 11 qubits, the difference in the probabilities of correct operation differs by less than 10–3. Thus, from the obtained dependencies, it is possible to predict the nature of such an influence on circuits with an even larger number of qubits, the stability of which cannot be studied due to the insufficient computing power of classical computers. The most efficient way to modify Dijkstra’s algorithm is to replace the priority queue in the classical version of the algorithm with some quantum data structure that finds the minimum element for the next iteration of the algorithm. Despite the fact that quantum search does not provide a potential gain in asymptotics, another quantum modification of Dijkstra’s algorithm can be used. Namely, instead of maintaining and searching for a minimum in the priority queue, use the quantum algorithm immediately to search for a vertex that needs to be added to the shortest path tree, which will additionally acceleration the graph traversal by Dijkstra’s algorithm.
We analyze the potential for different types of searches using the formalism of scattering random walks on quantum computers. Given a particular type of graph consisting of nodes and connections, a ``tree maze,'' we would like to find a selected final node as quickly as possible, faster than any classical search algorithm. We show that this can be done using a quantum random walk, both through numerical calculations as well as by using the eigenvectors and eigenvalues of the quantum system.
This paper investigates the application of quantum walks to routing protocols within wireless networks. Traditional routing algorithms often struggle with efficiency and convergence speed, particularly in dynamic and complex network topologies. We propose a novel approach utilizing quantum walk principles to explore network connectivity and identify optimal routes. Our methodology employs a quantum walk algorithm to simulate network traversal, leveraging quantum superposition and interference to potentially achieve faster convergence and reduced latency compared to classical approaches. The core of the system relies on a discrete-time quantum walk on a graph representing the wireless network, where nodes are the walkers and edges represent communication links. The algorithm aims to minimize the walk length, effectively finding the shortest path between source and destination nodes. We present a theoretical framework and outline the key components of a quantum walk-based routing protocol. While this research focuses on the theoretical aspects and does not include experimental validation, it lays the foundation for future work exploring the practical feasibility and performance benefits of quantum walk routing in real-world wireless network scenarios.