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:1912.04196

Quantum walk search algorithms and effective resistance

Stephen Piddock

Published Dec 9, 2019• 4 citations
arXivHTMLPDF

Abstract

We consider the problem of finding a marked vertex in a graph from an arbitrary starting distribution, using a quantum walk based algorithm. We work in the framework introduced by Belovs which showed how to detect the existence of a marked vertex in $O(\sqrt{RW})$ quantum walk steps, where $R$ is the effective resistance and $W$ is the total weight of the graph. Our algorithm outputs a marked vertex in the same runtime up to a logarithmic factor in the number of marked vertices. When starting in the stationary distribution, this recovers the recent results of Ambainis et al. We also describe a new algorithm to estimate the effective resistance $R$.

DOI
10.48550/arxiv.1912.04196

Related papers

Fixed-point Quantum Walk Search.

Lvzhou Li, Yongzhen Xu, Zhang Delong

n this paper, we consider the problem of searching a marked vertex in a graph based on quantum walks. A very large body of research exists on this issue, from both theoretical and experimental studies, yet the existing quantum walk-based search algorithms require knowing exactly how many marked vertices there are before starting the search process. In addition, even if the precise knowledge of the number of marked vertices is known, the success probability of these algorithms could shrink dramatically when the number of search steps is greater than the right one. For avoiding these defects, in this paper we present a new quantum walk-based search algorithm which need not know any prior information about the marked vertices, but still keeps a quadratic speedup over classical ones and ensures that the error is bounded by a tunable parameter $\epsilon$. More specifically, for an $N$-vertex complete bipartite graph with marked vertices but without knowing the number of marked vertices, if the number of search steps $h$ satisfies $h \geq \ln(\frac{2}{\sqrt{\epsilon}})\sqrt{N}$, then the algorithm will output a marked vertex with probability at least $ 1-\epsilon$ for any given $\epsilon\in (0,1]$. This feature leads to quantum search algorithms with stronger robustness and a wider scope of application.

•Nov 17, 2021•0 citations

Quantum Walks and Electric Networks

Aleksandrs Belovs

We prove that a quantum walk can detect the presence of a marked element in a graph in $O(\sqrt{WR})$ steps for any initial probability distribution on vertices. Here, $W$ is the total weight of the graph, and $R$ is the effective resistance. This generalizes the result by Szegedy that is only applicable if the initial distribution is stationary. We describe a time-efficient quantum algorithm for 3-distinctness based on these ideas.

arXiv:1302.3143•Feb 13, 2013•23 citations

Robust quantum walk search without knowing the number of marked vertices

Yongzhen Xu, Delong Zhang, Lvzhou Li

There has been a very large body of research on searching a marked vertex on a graph based on quantum walks, and Grover's algorithm can be regarded as a quantum walk-based search algorithm on a special graph. However, the existing quantum walk-based search algorithms suffer severely from the souffl\'e problem, which mainly means that the success probability of finding a marked vertex could shrink dramatically, even to zero, when the number of search steps is greater than the right one, thus heavily reducing the robustness and practicability of the algorithm. Surprisingly, while the souffl\'e problem of Grover's algorithm has attracted enough attention, how to address this problem for general quantum walk-based search algorithms is missing in the literature. Here we initiate the study of overcoming the souffl\'e problem for quantum walk-based search algorithms by presenting a quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup. In this framework, for any adjustable parameter $\ensuremath{\epsilon}$, the quantum algorithm can find a marked vertex on an $N$-vertex complete bipartite graph with probability at least $1\ensuremath{-}\ensuremath{\epsilon}$, whenever the number of search steps $h$ satisfies $h\ensuremath{\ge}ln(\frac{2}{\sqrt{\ensuremath{\epsilon}}})\sqrt{N}+1$. Note that the algorithm need not know the exact number of marked vertices. Consequently, we obtain quantum search algorithms with stronger robustness and practicability.

arXiv:2111.09012•Physical Review A•Nov 14, 2022•16 citations

A Unified Framework of Quantum Walk Search

Simon Apers, András Gilyén, Stacey Jeffery

Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.

arXiv:1912.04233•Leibniz international proceedings in informatics•Dec 9, 2019•18 citations

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

Improved quantum backtracking algorithms using effective resistance estimates

Michael Jarret, Kianna Wan

We investigate quantum backtracking algorithms of the type introduced by Montanaro (Montanaro, arXiv:1509.02374). These algorithms explore trees of unknown structure and in certain settings exponentially outperform their classical counterparts. Some of the previous work focused on obtaining a quantum advantage for trees in which a unique marked vertex is promised to exist. We remove this restriction by recharacterizing the problem in terms of the effective resistance of the search space. In this paper, we present a generalization of one of Montanaro's algorithms to trees containing $k$ marked vertices, where $k$ is not necessarily known a priori. Our approach involves using amplitude estimation to determine a near-optimal weighting of a diffusion operator, which can then be applied to prepare a superposition state with support only on marked vertices and ancestors thereof. By repeatedly sampling this state and updating the input vertex, a marked vertex is reached in a logarithmic number of steps. The algorithm thereby achieves the conjectured bound of $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{\mathcal{O}}(\sqrt{T{R}_{\mathrm{max}}})$ for finding a single marked vertex and $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{\mathcal{O}}(k\sqrt{T{R}_{\mathrm{max}}})$ for finding all $k$ marked vertices, where $T$ is an upper bound on the tree size and ${R}_{\mathrm{max}}$ is the maximum effective resistance encountered by the algorithm. This constitutes a speedup over Montanaro's original procedure in both the case of finding one and the case of finding multiple marked vertices in an arbitrary tree.

arXiv:1711.05295•Physical Review A•Feb 27, 2018•9 citations
We consider the problem of finding a marked vertex in a graph from an arbitrary starting distribution, using a quantum walk based algorithm. We work in the framework introduced by Belovs which showed how to detect the existence of a marked vertex in O(RW)O(\sqrt{RW})O(RW​) quantum walk steps, where RRR is the effective resistance and WWW is the total weight of the graph. Our algorithm outputs a marked vertex in the same runtime up to a logarithmic factor in the number of marked vertices. When starting in the stationary distribution, this recovers the recent results of Ambainis et al. We also describe a new algorithm to estimate the effective resistance RRR.
n this paper, we consider the problem of searching a marked vertex in a graph based on quantum walks. A very large body of research exists on this issue, from both theoretical and experimental studies, yet the existing quantum walk-based search algorithms require knowing exactly how many marked vertices there are before starting the search process. In addition, even if the precise knowledge of the number of marked vertices is known, the success probability of these algorithms could shrink dramatically when the number of search steps is greater than the right one. For avoiding these defects, in this paper we present a new quantum walk-based search algorithm which need not know any prior information about the marked vertices, but still keeps a quadratic speedup over classical ones and ensures that the error is bounded by a tunable parameter ϵ\epsilonϵ. More specifically, for an NNN-vertex complete bipartite graph with marked vertices but without knowing the number of marked vertices, if the number of search steps hhh satisfies h≥ln⁡(2ϵ)Nh \geq \ln(\frac{2}{\sqrt{\epsilon}})\sqrt{N}h≥ln(ϵ​2​)N​, then the algorithm will output a marked vertex with probability at least $ 1-\epsilon$ for any given ϵ∈(0,1]\epsilon\in (0,1]ϵ∈(0,1]. This feature leads to quantum search algorithms with stronger robustness and a wider scope of application.
We prove that a quantum walk can detect the presence of a marked element in a graph in O(WR)O(\sqrt{WR})O(WR​) steps for any initial probability distribution on vertices. Here, WWW is the total weight of the graph, and RRR is the effective resistance. This generalizes the result by Szegedy that is only applicable if the initial distribution is stationary. We describe a time-efficient quantum algorithm for 3-distinctness based on these ideas.
There has been a very large body of research on searching a marked vertex on a graph based on quantum walks, and Grover's algorithm can be regarded as a quantum walk-based search algorithm on a special graph. However, the existing quantum walk-based search algorithms suffer severely from the souffl\'e problem, which mainly means that the success probability of finding a marked vertex could shrink dramatically, even to zero, when the number of search steps is greater than the right one, thus heavily reducing the robustness and practicability of the algorithm. Surprisingly, while the souffl\'e problem of Grover's algorithm has attracted enough attention, how to address this problem for general quantum walk-based search algorithms is missing in the literature. Here we initiate the study of overcoming the souffl\'e problem for quantum walk-based search algorithms by presenting a quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup. In this framework, for any adjustable parameter $\ensuremath{\epsilon}$, the quantum algorithm can find a marked vertex on an NNN-vertex complete bipartite graph with probability at least $1\ensuremath{-}\ensuremath{\epsilon}$, whenever the number of search steps hhh satisfies $h\ensuremath{\ge}ln(\frac{2}{\sqrt{\ensuremath{\epsilon}}})\sqrt{N}+1$. Note that the algorithm need not know the exact number of marked vertices. Consequently, we obtain quantum search algorithms with stronger robustness and practicability.
Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.
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.
We investigate quantum backtracking algorithms of the type introduced by Montanaro (Montanaro, arXiv:1509.02374). These algorithms explore trees of unknown structure and in certain settings exponentially outperform their classical counterparts. Some of the previous work focused on obtaining a quantum advantage for trees in which a unique marked vertex is promised to exist. We remove this restriction by recharacterizing the problem in terms of the effective resistance of the search space. In this paper, we present a generalization of one of Montanaro's algorithms to trees containing kkk marked vertices, where kkk is not necessarily known a priori. Our approach involves using amplitude estimation to determine a near-optimal weighting of a diffusion operator, which can then be applied to prepare a superposition state with support only on marked vertices and ancestors thereof. By repeatedly sampling this state and updating the input vertex, a marked vertex is reached in a logarithmic number of steps. The algorithm thereby achieves the conjectured bound of $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{\mathcal{O}}(\sqrt{T{R}_{\mathrm{max}}})$ for finding a single marked vertex and $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{\mathcal{O}}(k\sqrt{T{R}_{\mathrm{max}}})$ for finding all kkk marked vertices, where TTT is an upper bound on the tree size and Rmax{R}_{\mathrm{max}}Rmax​ is the maximum effective resistance encountered by the algorithm. This constitutes a speedup over Montanaro's original procedure in both the case of finding one and the case of finding multiple marked vertices in an arbitrary tree.