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

Comment on Nahimovs et al. `On the probability of finding marked connected components using quantum walks'

Adam Glos, Nikolay Nahimovs

Published Jul 29, 2019• 0 citations
arXivHTMLPDF

Abstract

In this comment paper we present two misconceptions found in paper of Nahimovs et al. \emph{On the probability of finding marked connected components using quantum walks}. First, we show that the Theorem 2 (sufficient and necessary condition for a state to be stationary) is incomplete -- it works only if unmarked vertices form a single connected component. Second, we correct derivation of \emph{a} coefficient in the Theorem 3 (lower bound on the probability) and show how to upper bound value of \emph{a}.

DOI
10.48550/arxiv.1907.12277

Related papers

On the probability of finding marked connected components using quantum walks

Nikolajs Nahimovs, Raqueline A. M. Santos, Kamil Ravilevich Khadiev

Finding a marked vertex in a graph can be a complicated task when using quantum walks. Recent results show that for two or more adjacent marked vertices search by quantum walk with Grover's coin may have no speed-up over classical exhaustive search. In this paper, we analyze the probability of finding a marked vertex for a set of connected components of marked vertices. We prove two upper bounds on the probability of finding a marked vertex and sketch further research directions.

arXiv:1710.04046•Oct 11, 2017•0 citations

On the Probability of Finding Marked Connected Components Using Quantum Walks

Kamil Ravilevich Khadiev, Nikolajs Nahimovs, Raqueline A. M. Santos

Finding a marked vertex in a graph can be a complicated task when using quantum walks. Recent results show that for two or more adjacent marked vertices search by quantum walk with Grover’s coin may have no speed-up over classical exhaustive search. In this paper, we analyze the probability of finding a marked vertex for a set of connected components of marked vertices. We prove two upper bounds on the probability of finding a marked vertex and sketch further research directions.

Lobachevskii Journal of Mathematics•Sep 1, 2018•5 citations

Stationary states in quantum walk search

Krišjānis Prūsis, Jevgēnijs Vihrovs, Thomas G. Wong

When classically searching a database, having additional correct answers makes the search easier. For a discrete-time quantum walk searching a graph for a marked vertex, however, additional marked vertices can make the search harder by causing the system to approximately begin in a stationary state, so the system fails to evolve. In this paper, we completely characterize the stationary states, or 1-eigenvectors, of the quantum walk search operator for general graphs and configurations of marked vertices by decomposing their amplitudes into uniform and flip states. This infinitely expands the number of known stationary states and gives an optimization procedure to find the stationary state closest to the initial uniform state of the walk. We further prove theorems on the existence of stationary states, with them conditionally existing if the marked vertices form a bipartite connected component and always existing if nonbipartite. These results utilize the standard oracle in Grover's algorithm, but we show that a different type of oracle prevents stationary states from interfering with the search algorithm.

arXiv:1608.00136•Physical Review A•Sep 29, 2016•14 citations

Search of clustered marked states with lackadaisical quantum walks

Amit Saha, Ritajit Majumdar, Debasri Saha +2 more

Nature of quantum walk in presence of multiple marked state has been studied by Nahimovs and Rivosh \cite{10.1007/978-3-662-49192-8_31}. They have shown that if the marked states are arranged in a $\sqrt{k} \times \sqrt{k}$ cluster in a $\sqrt{N} \times \sqrt{N}$ grid, then to find a single marked state among the multiple ones, quantum walk requires $Ω(\sqrt{N} - \sqrt{k})$ time. In this paper, we show that using lackadaisical quantum walk with the weight of the self-loop as $\frac{4}{N(k + \lfloor{\frac{\sqrt{k}}{2}}\rfloor)}$, where $k$ is odd, the probability of finding a marked state increases by $\sim 0.2$. Furthermore, we show that instead of applying the quantum walk $\mathcal{O}(k)$ times to find all the marked states, classical search in the vicinity of the marked state found after the first implementation of the quantum walk can find all the marked states in $\mathcal{O}(\sqrt{k})$ time on average.

arXiv:1804.01446•Apr 4, 2018•7 citations

Upperbounds on the probability of finding marked connected components using quantum walks

Adam Glos, Nikolajs Nahimovs, Konstantin Balakirev +1 more

arXiv:1903.01482•Quantum Information Processing•Jan 1, 2021•11 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
In this comment paper we present two misconceptions found in paper of Nahimovs et al. \emph{On the probability of finding marked connected components using quantum walks}. First, we show that the Theorem 2 (sufficient and necessary condition for a state to be stationary) is incomplete -- it works only if unmarked vertices form a single connected component. Second, we correct derivation of \emph{a} coefficient in the Theorem 3 (lower bound on the probability) and show how to upper bound value of \emph{a}.
When classically searching a database, having additional correct answers makes the search easier. For a discrete-time quantum walk searching a graph for a marked vertex, however, additional marked vertices can make the search harder by causing the system to approximately begin in a stationary state, so the system fails to evolve. In this paper, we completely characterize the stationary states, or 1-eigenvectors, of the quantum walk search operator for general graphs and configurations of marked vertices by decomposing their amplitudes into uniform and flip states. This infinitely expands the number of known stationary states and gives an optimization procedure to find the stationary state closest to the initial uniform state of the walk. We further prove theorems on the existence of stationary states, with them conditionally existing if the marked vertices form a bipartite connected component and always existing if nonbipartite. These results utilize the standard oracle in Grover's algorithm, but we show that a different type of oracle prevents stationary states from interfering with the search algorithm.
Nature of quantum walk in presence of multiple marked state has been studied by Nahimovs and Rivosh \cite{10.1007/978-3-662-49192-8_31}. They have shown that if the marked states are arranged in a k×k\sqrt{k} \times \sqrt{k}k​×k​ cluster in a N×N\sqrt{N} \times \sqrt{N}N​×N​ grid, then to find a single marked state among the multiple ones, quantum walk requires Ω(N−k)Ω(\sqrt{N} - \sqrt{k})Ω(N​−k​) time. In this paper, we show that using lackadaisical quantum walk with the weight of the self-loop as 4N(k+⌊k2⌋)\frac{4}{N(k + \lfloor{\frac{\sqrt{k}}{2}}\rfloor)}N(k+⌊2k​​⌋)4​, where kkk is odd, the probability of finding a marked state increases by ∼0.2\sim 0.2∼0.2. Furthermore, we show that instead of applying the quantum walk O(k)\mathcal{O}(k)O(k) times to find all the marked states, classical search in the vicinity of the marked state found after the first implementation of the quantum walk can find all the marked states in O(k)\mathcal{O}(\sqrt{k})O(k​) time on average.
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.