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

Correcting for Potential Barriers in Quantum Walk Search

Andris Ambainis, Thomas G. Wong

Published May 8, 2015• 1 citation
arXivHTMLPDF

Abstract

A randomly walking quantum particle searches in Grover's $Θ(\sqrt{N})$ iterations for a marked vertex on the complete graph of $N$ vertices by repeatedly querying an oracle that flips the amplitude at the marked vertex, scattering by a "coin" flip, and hopping. Physically, however, potential energy barriers can hinder the hop and cause the search to fail, even when the amplitude of not hopping decreases with $N$. We correct for these errors by interpreting the quantum walk search as an amplitude amplification algorithm and modifying the phases applied by the coin flip and oracle such that the amplification recovers the $Θ(\sqrt{N})$ runtime.

DOI
10.48550/arxiv.1505.02035

Related papers

Correcting for potential barriers in quantum walk search

Andris Ambainis, Thomas G. Wong

A randomly walking quantum particle searches in Grover’s Θ(√ N) iterations for a marked vertex on the complete graph of N vertices by repeatedly querying an oracle that flips the amplitude at the marked vertex, scattering by a “coin” flip, and hopping. Physically, however, potential energy barriers can hinder the hop and cause the search to fail, even when the amplitude of not hopping decreases with N. We correct for these errors by interpreting the quantum walk search as an amplitude amplification algorithm and modifying the phases applied by the coin flip and oracle such that the amplification recovers the Θ(√ N) runtime.

Quantum Information and Computation•Nov 1, 2015•2 citations

Quantum walk search through potential barriers

Thomas G Wong

Abstract An ideal quantum walk transitions from one vertex to another with perfect fidelity, but in physical systems, the particle may be hindered by potential energy barriers. Then the particle has some amplitude of tunneling through the barriers, and some amplitude of staying put. We investigate the algorithmic consequence of such barriers for the quantum walk formulation of Grover’s algorithm. We prove that the failure amplitude must scale as O ( 1 / N ) for search to retain its quantum O ( N ) runtime; otherwise, it searches in classical O ( N ) time. Thus searching larger ‘databases’ requires increasingly reliable hop operations or error correction. This condition holds for both discrete- and continuous-time quantum walks.

arXiv:1503.06605•Journal of Physics A Mathematical and Theoretical•Nov 9, 2016•11 citations

Grover search with lackadaisical quantum walks

Thomas G. Wong

The lazy random walk, where the walker has some probability of staying put, is a useful tool in classical algorithms. We propose a quantum analogue, the lackadaisical quantum walk, where each vertex is given l self-loops, and we investigate its effects on Grover's algorithm when formulated as search for a marked vertex on the complete graph of N vertices. For the discrete-time quantum walk using the phase flip coin, adding a self-loop to each vertex boosts the success probability from 1/2 to 1. Additional self-loops, however, decrease the success probability. Using instead the Shenvi, Kempe, and Whaley (2003) coin, adding self-loops simply slows down the search. These coins also differ in that the first is faster than classical when l scales less than N , while the second requires that l scale less than N 2 . Finally, continuous-time quantum walks differ from both of these discrete-time examples—the self-loops make no difference at all. These behaviors generalize to multiple marked vertices.

arXiv:1502.04567•Journal of Physics A Mathematical and Theoretical•Oct 7, 2015•94 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

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 walk search algorithms and effective resistance

Stephen Piddock

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$.

arXiv:1912.04196•Dec 9, 2019•4 citations
A randomly walking quantum particle searches in Grover's Θ(N)Θ(\sqrt{N})Θ(N​) iterations for a marked vertex on the complete graph of NNN vertices by repeatedly querying an oracle that flips the amplitude at the marked vertex, scattering by a "coin" flip, and hopping. Physically, however, potential energy barriers can hinder the hop and cause the search to fail, even when the amplitude of not hopping decreases with NNN. We correct for these errors by interpreting the quantum walk search as an amplitude amplification algorithm and modifying the phases applied by the coin flip and oracle such that the amplification recovers the Θ(N)Θ(\sqrt{N})Θ(N​) runtime.
A randomly walking quantum particle searches in Grover’s Θ(√ N) iterations for a marked vertex on the complete graph of N vertices by repeatedly querying an oracle that flips the amplitude at the marked vertex, scattering by a “coin” flip, and hopping. Physically, however, potential energy barriers can hinder the hop and cause the search to fail, even when the amplitude of not hopping decreases with N. We correct for these errors by interpreting the quantum walk search as an amplitude amplification algorithm and modifying the phases applied by the coin flip and oracle such that the amplification recovers the Θ(√ N) runtime.
Abstract An ideal quantum walk transitions from one vertex to another with perfect fidelity, but in physical systems, the particle may be hindered by potential energy barriers. Then the particle has some amplitude of tunneling through the barriers, and some amplitude of staying put. We investigate the algorithmic consequence of such barriers for the quantum walk formulation of Grover’s algorithm. We prove that the failure amplitude must scale as O ( 1 / N ) for search to retain its quantum O ( N ) runtime; otherwise, it searches in classical O ( N ) time. Thus searching larger ‘databases’ requires increasingly reliable hop operations or error correction. This condition holds for both discrete- and continuous-time quantum walks.
The lazy random walk, where the walker has some probability of staying put, is a useful tool in classical algorithms. We propose a quantum analogue, the lackadaisical quantum walk, where each vertex is given l self-loops, and we investigate its effects on Grover's algorithm when formulated as search for a marked vertex on the complete graph of N vertices. For the discrete-time quantum walk using the phase flip coin, adding a self-loop to each vertex boosts the success probability from 1/2 to 1. Additional self-loops, however, decrease the success probability. Using instead the Shenvi, Kempe, and Whaley (2003) coin, adding self-loops simply slows down the search. These coins also differ in that the first is faster than classical when l scales less than N , while the second requires that l scale less than N 2 . Finally, continuous-time quantum walks differ from both of these discrete-time examples—the self-loops make no difference at all. These behaviors generalize to multiple marked vertices.
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.
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 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.