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

arXiv:1810.06295 · Physical Review A

Scattering quantum random walks on square grids and randomly generated mazes

Daniel Koch

Published Jan 18, 2019• 4 citations
arXivHTMLPDF

Abstract

The scattering-quantum-random-walk scheme has found success as a basis for search algorithms on highly symmetric graph structures. In this paper we examine its effectiveness at locating a specially marked vertex on square grid graphs, consisting of ${N}^{2}$ nodes. We simulate these quantum systems using classical computational methods and find that the probability distributions that arise are very favorable for a hybrid quantum-classical algorithm. We then examine how this hybrid algorithm handles varying types of randomness in both location of the special vertex and later random obstacles placed throughout the geometry, showing that the algorithm is resilient to both cases.

DOI
10.1103/physreva.99.012330

Related papers

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 on two-dimensional torus and grid

Mojtaba Komeili

Let χ be a function that maps the vertices of a graph to zero or one. We want to find a vertex m, called a marked vertex, such that χ(m) = 1. Random walk is an algorithm for finding such a vertex. The measure of complexity for random walk is hitting time. There is a quantum algorithm that finds a marked vertex, and runs in the square root of the extended hitting time. For some configurations of marked vertices on certain graphs, the extended hitting time is asymptotically larger than the hitting time. This might cause the quantum algorithm for finding to be less efficient than a random walk. Two-dimensional torus and grid are canonical examples of such graphs. This thesis is about efficient quantum algorithms for finding a marked vertex on a two-dimensional torus. We prove the convexity of the extended hitting time, and provide a new upper bound on it. We show that, with a probability that is more than a constant, random walk on a torus is localized, and it is restricted to a sub-graph of the torus. From these observations, we introduce two algorithms that find a marked vertex on a torus. The complexity of these algorithms is in the order of the square root of the hitting time, up to logarithmic factors. They both start by finding an estimate to the hitting time. Using that, they estimate the size of a sub-graph that contains a marked vertex with more than a constant probability, and sample such a sub-graph. Our first algorithm finds a marked vertex on this sub-graph by using a quantum algorithm that runs in extended hitting time, and finds a marked vertex with probability at least a constant. Our second algorithm recursively runs the detection algorithm on cuts of the sub-graph, until reaching a constant sized sub-graph that contains a marked vertex. These algorithms are the first quantum algorithms that achieve close-to-quadratic speed-up in quantum walk on a two-dimensional torus, for all configurations of marked vertices.

•May 28, 2018•1 citation

Quantum walks on two-dimensional grids with multiple marked locations

Nikolajs Nahimovs, Alexander Rivosh

The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration of marked locations. While the first dependence have been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. The original paper analyses one and two marked location cases only. We move beyond two marked locations and study the behaviour of the algorithm for an arbitrary configuration of marked locations. In this paper we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of $k$ marked locations for which the number of steps of the algorithm differs by $Ω(\sqrt{k})$ factor. Second, we present two configurations of $k$ and $\sqrt{k}$ marked locations having the same number of steps and probability to find a marked location.

arXiv:1507.03788•Jul 14, 2015•3 citations

Szegedy's quantum walk with queries

Raqueline A. M. Santos

When searching for a marked vertex in a graph, Szegedy's usual search operator is defined by using the transition probability matrix of the random walk with absorbing barriers at the marked vertices. Instead of using this operator, we analyze searching with Szegedy's quantum walk by using reflections around the marked vertices, that is, the standard form of quantum query. We show we can boost the probability to 1 of finding a marked vertex in the complete graph. Numerical simulations suggests that the success probability can be improved for other graphs, like the two-dimensional grid. We also prove that, for a certain class of graphs, we can express Szegedy's search operator, obtained from the absorbing walk, using the standard query model.

arXiv:1603.05473•Mar 17, 2016•1 citation

Quadratic speedup for finding marked vertices by Quantum walks

Andris Ambainis, András Gilyén, Stacey Jeffery +1 more

A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.

arXiv:1903.07493•ACM Symposium on Theory of Computing (STOC)•Jun 7, 2020•45 citations

Marked vertex search on disordered graphs with Rosenzweig-Porter phases

Sabyasachi Chakraborty, Tilen Cadez, Sonjoy Majumder +1 more

Quantum marked vertex search algorithms are known to outperform their classical counterparts, yet their behavior in the presence of disorder remains largely unexplored. Here, we address this gap by studying marked vertex search on disordered random graphs. To introduce disorder, we implement the Rosenzweig-Porter (RP) model, a random matrix ensemble with tunable ergodic, non-ergodic extended, and localized phases, on Erdős-Rényi (ER) graphs. This produces a doubly random system where ER graph connectivity randomizes which interactions exist, while RP disorder controls their strength and `on-site' potentials, providing a two-parameter framework to study quantum dynamics on disordered networks. First, we show that the characteristic Wigner-Dyson-to-Poisson spectral crossover of the RP ensemble survives under graph constraints across the sparse-to-dense range, and we derive an analytical estimate for the finite-size localization boundary that shifts systematically with the graph edge probability $p$, consistent with a resonant-hybridization argument. Thereafter, using this disordered graph ensemble, we study the marked vertex search problem and find that search performance tracks the underlying quantum phase directly. Counterintuitively, the ergodic phase, despite supporting fast transport, yields lower success probability than the localized phase, which achieves high success probability at the cost of significantly longer search times. These results establish a direct and quantitative link between random matrix disorder on graphs and the performance of continuous-time quantum walk search, and suggest that disorder, rather than being merely an obstacle, can be exploited as a tunable parameter in quantum search protocols.

quant-pharXiv:2608.00224•Aug 4, 2026•0 citations
The scattering-quantum-random-walk scheme has found success as a basis for search algorithms on highly symmetric graph structures. In this paper we examine its effectiveness at locating a specially marked vertex on square grid graphs, consisting of N2{N}^{2}N2 nodes. We simulate these quantum systems using classical computational methods and find that the probability distributions that arise are very favorable for a hybrid quantum-classical algorithm. We then examine how this hybrid algorithm handles varying types of randomness in both location of the special vertex and later random obstacles placed throughout the geometry, showing that the algorithm is resilient to both cases.
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.
Let χ be a function that maps the vertices of a graph to zero or one. We want to find a vertex m, called a marked vertex, such that χ(m) = 1. Random walk is an algorithm for finding such a vertex. The measure of complexity for random walk is hitting time. There is a quantum algorithm that finds a marked vertex, and runs in the square root of the extended hitting time. For some configurations of marked vertices on certain graphs, the extended hitting time is asymptotically larger than the hitting time. This might cause the quantum algorithm for finding to be less efficient than a random walk. Two-dimensional torus and grid are canonical examples of such graphs. This thesis is about efficient quantum algorithms for finding a marked vertex on a two-dimensional torus. We prove the convexity of the extended hitting time, and provide a new upper bound on it. We show that, with a probability that is more than a constant, random walk on a torus is localized, and it is restricted to a sub-graph of the torus. From these observations, we introduce two algorithms that find a marked vertex on a torus. The complexity of these algorithms is in the order of the square root of the hitting time, up to logarithmic factors. They both start by finding an estimate to the hitting time. Using that, they estimate the size of a sub-graph that contains a marked vertex with more than a constant probability, and sample such a sub-graph. Our first algorithm finds a marked vertex on this sub-graph by using a quantum algorithm that runs in extended hitting time, and finds a marked vertex with probability at least a constant. Our second algorithm recursively runs the detection algorithm on cuts of the sub-graph, until reaching a constant sized sub-graph that contains a marked vertex. These algorithms are the first quantum algorithms that achieve close-to-quadratic speed-up in quantum walk on a two-dimensional torus, for all configurations of marked vertices.
The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration of marked locations. While the first dependence have been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. The original paper analyses one and two marked location cases only. We move beyond two marked locations and study the behaviour of the algorithm for an arbitrary configuration of marked locations. In this paper we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of kkk marked locations for which the number of steps of the algorithm differs by Ω(k)Ω(\sqrt{k})Ω(k​) factor. Second, we present two configurations of kkk and k\sqrt{k}k​ marked locations having the same number of steps and probability to find a marked location.
When searching for a marked vertex in a graph, Szegedy's usual search operator is defined by using the transition probability matrix of the random walk with absorbing barriers at the marked vertices. Instead of using this operator, we analyze searching with Szegedy's quantum walk by using reflections around the marked vertices, that is, the standard form of quantum query. We show we can boost the probability to 1 of finding a marked vertex in the complete graph. Numerical simulations suggests that the success probability can be improved for other graphs, like the two-dimensional grid. We also prove that, for a certain class of graphs, we can express Szegedy's search operator, obtained from the absorbing walk, using the standard query model.
A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.
Quantum marked vertex search algorithms are known to outperform their classical counterparts, yet their behavior in the presence of disorder remains largely unexplored. Here, we address this gap by studying marked vertex search on disordered random graphs. To introduce disorder, we implement the Rosenzweig-Porter (RP) model, a random matrix ensemble with tunable ergodic, non-ergodic extended, and localized phases, on Erdős-Rényi (ER) graphs. This produces a doubly random system where ER graph connectivity randomizes which interactions exist, while RP disorder controls their strength and `on-site' potentials, providing a two-parameter framework to study quantum dynamics on disordered networks. First, we show that the characteristic Wigner-Dyson-to-Poisson spectral crossover of the RP ensemble survives under graph constraints across the sparse-to-dense range, and we derive an analytical estimate for the finite-size localization boundary that shifts systematically with the graph edge probability ppp, consistent with a resonant-hybridization argument. Thereafter, using this disordered graph ensemble, we study the marked vertex search problem and find that search performance tracks the underlying quantum phase directly. Counterintuitively, the ergodic phase, despite supporting fast transport, yields lower success probability than the localized phase, which achieves high success probability at the cost of significantly longer search times. These results establish a direct and quantitative link between random matrix disorder on graphs and the performance of continuous-time quantum walk search, and suggest that disorder, rather than being merely an obstacle, can be exploited as a tunable parameter in quantum search protocols.