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

AIP Advances

Speed-up and suppression effect of side chain in quantum searching on a graph

Jinhui Zhu, Li-Hua Lü

Published Jun 1, 2023• 0 citations
Publisher

Abstract

Searching efficiency, which biologists and roboticists are ever concerned about, has become important in physics and information science nowadays. In classical probability-based searching problems, as stigmergy, the increase in graph complexity will decrease the searching efficiency. Here we study the searching efficiency based on the first-passage probability and find a counterintuitive phenomenon in quantum walk on a graph with floating vertices. Connecting one vertex in the floating layer to that in the base layer will speed up the searching rapidity, but such a speed-up effect will be suppressed at once if one more vertex is connected to the already connected vertex in the floating layer. This is a counterintuitive phenomenon in comparison to its classical counterpart, where additional vertices at the side chain will retard the searching rapidity. We also propose an ancillary model that bridges the measurement of the probability and the first-passage probability, which is expected to provide new ideas for quantum simulation by means of qubit chips.

DOI
10.1063/5.0149835

Related papers

Quantum Severalty: Speed-up and Suppress Effect in Searching Problem

Jinhui Zhu, Li-Hua Lü, You‐Quan Li

The idea that the search efficiency can be increased with the help of a number of autonomous agents is often relevant in many situations, which is known among biologists and roboticists as a stigmergy. This is due to the fact that, in any probability-based search problem, adding information provides values for conditional prpbabilities. We report new findings of speed-up and suppression effects occuring in the quantum search problem through the study of quantum walk on a graph with floating vertices. This effect is a completely counterintuitive phenomenon in comparison to the classical counterpert, and may faciliate new insight in the future information search mechanisms that were never been perceived in classical picture. In order to understand the first passage probability, we also propose a method via ancillary model to bridge the measurement of the time dependence of the total probability of the complementary part and the first passage probability of the original model. This is expected to provide new ideas for quantum simulation by means of qubit chips.

arXiv:1909.06798•Sep 15, 2019•0 citations

Coherence as resource in scattering quantum walk search on complete graph

Yunlong Su, Siyuan Liu, Xiao-Hui Wang +2 more

We investigate the behavior of coherence in scattering quantum walk search on complete graph under the condition that the total number of vertices of the graph is significantly larger than the marked number of vertices we are searching, N ≫ v. We find that the consumption of coherence represents the increase of the success probability for the searching, also it is related to the efficiency of the algorithm in oracle queries. If no coherence is consumed or an incoherent state is utilized, the algorithm will behave as the classical blind search, implying that coherence is responsible for the speed-up in this quantum algorithm over its classical counterpart. The effect of noises, in particular of photon loss and random phase shifts, on the performance of algorithm is studied. Two types of noise are considered because they arise in the optical network used for experimental realization of scattering quantum walk. It is found that photon loss will reduce the coherence and random phase shifts will hinder the interference between the edge states, both leading to lower success probability compared with the noise-free case. We then conclude that coherence plays an essential role and is responsible for the speed-up in this quantum algorithm.

arXiv:1704.04974•Scientific Reports•Jul 17, 2018•3 citations

Quantum-walk-based search and centrality

Scott M. Berry, Jingbo B. Wang

We study the discrete-time quantum-walk-based search for a marked vertex on a graph. By considering various structures in which not all vertices are equivalent, we investigate the relationship between the successful search probability and the position of the marked vertex, in particular, its centrality. We find that the maximum value of the search probability does not necessarily increase as the marked vertex becomes more central, and we investigate an interesting relationship between the frequency of the successful search probability and the centrality of the marked vertex.

arXiv:1010.0764•Physical Review A•Oct 26, 2010•80 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

Improvement of quantum walks search algorithm in single-marked vertex graph

Xinying Li, Yun Shang

Abstract Quantum walks are powerful tools for building quantum search algorithms. However, these success probabilities are far below 1. Amplitude amplification is usually used to amplify success probability, but the soufflé problem follows. Only stop at the right step can we achieve a maximum success probability. Otherwise, as the number of steps increases, the success probability may decrease, which will cause troubles in the practical application of the algorithm when the optimal number of steps is unknown. In this work, we define generalized interpolated quantum walks instead of amplitude amplification, which can not only improve the success probability but also avoid the soufflé problem. We choose a special case of generalized interpolated quantum walks and construct a series of new search algorithms based on phase estimation and quantum fast-forwarding, respectively. Especially, by combining our interpolated quantum walks with quantum fast-forwarding, we both reduce the time complexity of the search algorithm from Θ ( ( ε − 1 ) H T ) to Θ ( log ( ε − 1 ) HT ) and reduce the number of ancilla qubits required from Θ ( log ( ε − 1 ) + log H T ) to Θ ( log log ( ε − 1 ) + log H T ) , where ɛ denotes the precision and H T denotes the classical hitting time. In addition, we show that our generalized interpolated quantum walks can improve the construction of quantum stationary states corresponding to reversible Markov chains. Finally, we give an application to construct a slowly evolving Markov chain sequence by applying generalized interpolated quantum walks, which is the necessary premise in adiabatic stationary state preparation.

Journal of Physics A Mathematical and Theoretical•Aug 17, 2023•1 citation

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
Searching efficiency, which biologists and roboticists are ever concerned about, has become important in physics and information science nowadays. In classical probability-based searching problems, as stigmergy, the increase in graph complexity will decrease the searching efficiency. Here we study the searching efficiency based on the first-passage probability and find a counterintuitive phenomenon in quantum walk on a graph with floating vertices. Connecting one vertex in the floating layer to that in the base layer will speed up the searching rapidity, but such a speed-up effect will be suppressed at once if one more vertex is connected to the already connected vertex in the floating layer. This is a counterintuitive phenomenon in comparison to its classical counterpart, where additional vertices at the side chain will retard the searching rapidity. We also propose an ancillary model that bridges the measurement of the probability and the first-passage probability, which is expected to provide new ideas for quantum simulation by means of qubit chips.
The idea that the search efficiency can be increased with the help of a number of autonomous agents is often relevant in many situations, which is known among biologists and roboticists as a stigmergy. This is due to the fact that, in any probability-based search problem, adding information provides values for conditional prpbabilities. We report new findings of speed-up and suppression effects occuring in the quantum search problem through the study of quantum walk on a graph with floating vertices. This effect is a completely counterintuitive phenomenon in comparison to the classical counterpert, and may faciliate new insight in the future information search mechanisms that were never been perceived in classical picture. In order to understand the first passage probability, we also propose a method via ancillary model to bridge the measurement of the time dependence of the total probability of the complementary part and the first passage probability of the original model. This is expected to provide new ideas for quantum simulation by means of qubit chips.
We investigate the behavior of coherence in scattering quantum walk search on complete graph under the condition that the total number of vertices of the graph is significantly larger than the marked number of vertices we are searching, N ≫ v. We find that the consumption of coherence represents the increase of the success probability for the searching, also it is related to the efficiency of the algorithm in oracle queries. If no coherence is consumed or an incoherent state is utilized, the algorithm will behave as the classical blind search, implying that coherence is responsible for the speed-up in this quantum algorithm over its classical counterpart. The effect of noises, in particular of photon loss and random phase shifts, on the performance of algorithm is studied. Two types of noise are considered because they arise in the optical network used for experimental realization of scattering quantum walk. It is found that photon loss will reduce the coherence and random phase shifts will hinder the interference between the edge states, both leading to lower success probability compared with the noise-free case. We then conclude that coherence plays an essential role and is responsible for the speed-up in this quantum algorithm.
We study the discrete-time quantum-walk-based search for a marked vertex on a graph. By considering various structures in which not all vertices are equivalent, we investigate the relationship between the successful search probability and the position of the marked vertex, in particular, its centrality. We find that the maximum value of the search probability does not necessarily increase as the marked vertex becomes more central, and we investigate an interesting relationship between the frequency of the successful search probability and the centrality of the marked vertex.
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.
Abstract Quantum walks are powerful tools for building quantum search algorithms. However, these success probabilities are far below 1. Amplitude amplification is usually used to amplify success probability, but the soufflé problem follows. Only stop at the right step can we achieve a maximum success probability. Otherwise, as the number of steps increases, the success probability may decrease, which will cause troubles in the practical application of the algorithm when the optimal number of steps is unknown. In this work, we define generalized interpolated quantum walks instead of amplitude amplification, which can not only improve the success probability but also avoid the soufflé problem. We choose a special case of generalized interpolated quantum walks and construct a series of new search algorithms based on phase estimation and quantum fast-forwarding, respectively. Especially, by combining our interpolated quantum walks with quantum fast-forwarding, we both reduce the time complexity of the search algorithm from Θ ( ( ε − 1 ) H T ) to Θ ( log ( ε − 1 ) HT ) and reduce the number of ancilla qubits required from Θ ( log ( ε − 1 ) + log H T ) to Θ ( log log ( ε − 1 ) + log H T ) , where ɛ denotes the precision and H T denotes the classical hitting time. In addition, we show that our generalized interpolated quantum walks can improve the construction of quantum stationary states corresponding to reversible Markov chains. Finally, we give an application to construct a slowly evolving Markov chain sequence by applying generalized interpolated quantum walks, which is the necessary premise in adiabatic stationary state preparation.