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

Coherence as resource in quantum walk search on highly symmetric graph

Yunlong Su, Siyuan Liu, Xiaohui Wang

Published Apr 17, 2017• 0 citations
OpenAlex

Abstract

Under the condition $N \gg v$, we study the behavior of coherence in scattering quantum walk search and show the connection between it and the probability of success. We find that the consumption of coherence is highly related to the increase of the probability of success. We also find that the consumption of coherence is related to the efficiency of this algorithm. The more efficient the algorithm is, the more coherence is consumed. If no coherence is consumed, the efficiency of the algorithm will be the same as classical one, which implies coherence may be respond for the speeding up over classical one in this quantum algorithm. Moreover, we study the probability of success in the case of an incoherent initial state and find that when $N$ is large enough it will not change with time. It could be concluded that this quantum search algorithm loses its power with an incoherent initial state. This further shows that coherence plays an essential role in this algorithm.

Related papers

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

Evolution of Quantum Resources in Quantum-walk-based Search Algorithm

Meng Li, Xian Shi

Quantum walk is fundamental to designing many quantum algorithms. Here we consider the effects of quantum coherence and quantum entanglement for the quantum walk search on the complete bipartite graph. First, we numerically show the complementary relationship between the success probability and the two quantum resources (quantum coherence and quantum entanglement). We also provide theoretical analysis in the asymptotic scenarios. At last, we discuss the role played by generalized depolarizing noises and find that it would influence the dynamics of success probability and quantum coherence sharply, which is demonstrated by theoretical derivation and numerical simulation.

arXiv:2310.00352•Sep 30, 2023•0 citations

Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks

Si-Qi Zhou, Jin-Min Liang, Ziheng Ding +3 more

Quantum algorithms have demonstrated provable speedups over classical counterparts, yet establishing a comprehensive theoretical framework to understand the quantum advantage remains a core challenge. In this work, we decode the quantum search advantage by investigating the critical role of quantum state properties in random-walk-based algorithms. We propose three distinct variants of quantum random-walk search algorithms and derive exact analytical expressions for their success probabilities. These probabilities are fundamentally determined by specific initial state properties: the coherence fraction governs the first algorithm's performance, while entanglement and coherence dominate the outcomes of the second and third algorithms, respectively. We show that increased coherence fraction enhances success probability, but greater entanglement and coherence reduce it in the latter two cases. These findings reveal fundamental insights into harnessing quantum properties for advantage and guide algorithm design. Our searches achieve Grover-like speedups and show significant potential for quantum-enhanced machine learning.

quant-pharXiv:2511.06867•Chinese Physics Letters•Nov 11, 2025•2 citations

Evolution of quantum resources in quantum-walk-based search algorithm

Meng Li, Xian Shi

Quantum walk is fundamental to designing many quantum algorithms. Here we consider the effects of quantum coherence and quantum entanglement for the quantum walk search on the complete bipartite graph. First, we numerically show the complementary relationship between the success probability and the two quantum resources (quantum coherence and quantum entanglement). We also provide theoretical analysis in the asymptotic scenarios. At last, we discuss the role played by generalized depolarizing noises and find that it would influence the dynamics of success probability and quantum coherence sharply, which is demonstrated by theoretical derivation and numerical simulation.

Results in Physics•Sep 29, 2023•2 citations

Operator coherence dynamics in Grover's quantum search algorithm

Minghua Pan, Daowen Qiu

Coherence is one of the most basic concepts and resources in quantum information. To clear the role coherence plays on the essential operator level in Grover's search algorithm, here we discuss the coherence dynamics of the state after each basic operator is applyied. As it is known, Grover's search algorithm repeats the application of Grover operator $G$, which can be decomposed into $G={H}^{\ensuremath{\bigotimes}n}P{H}^{\ensuremath{\bigotimes}n}O$, where $H$ is Hadamard operator, $P$ is the condition phase-shift operator, and $O$ is the oracle operator. First, we show that $O$ and $P$ are incoherent operators while ${H}^{\ensuremath{\bigotimes}n}$ is coherent. Second, we prove that the amount of the operator coherence of the first ${H}^{\ensuremath{\bigotimes}n}$ and the operator coherence produced or depleted by ${H}^{\ensuremath{\bigotimes}n}$ depends not only on the size of the database and the success probability, but also on target states. Moreover, the amount of operator coherence is larger when the superposition state of targets is entangled rather than product. Third, we show that the two ${H}^{\ensuremath{\bigotimes}n}$ have different effects on coherence that one produces coherence and the other depletes coherence, and the depletion plays a major role. Therefore, the coherence is vibrating during the search process and the overall effect is that coherence is in depletion.

Physical Review A•Jul 31, 2019•25 citations

Quantum walk search on the complete bipartite graph

Mason L. Rhodes, Thomas G. Wong

The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph of $N$ vertices for one of $k$ marked vertices with different initial states. We prove an intriguing dependence on the number of marked and unmarked vertices in each partite set. For example, when the graph is irregular and the initial state is the typical uniform superposition over the vertices, then the success probability can vary greatly from one time step to the next, even alternating between 0 and 1, so the precise time at which measurement occurs is crucial. When the initial state is a uniform superposition over the edges, however, the success probability evolves smoothly. As another example, if the complete bipartite graph is regular, then the two initial states are equivalent. Then if two marked vertices are in the same partite set, the success probability reaches $1/2$, but if they are in different partite sets, it instead reaches 1. This differs from the complete graph, which is the quantum walk formulation of Grover's algorithm, where the success probability with two marked vertices is $8/9$. This reveals a contrast to the continuous-time quantum walk, whose evolution is governed by Schr\"odinger's equation, which asymptotically searches the regular complete bipartite graph with any arrangement of marked vertices in the same manner as the complete graph.

arXiv:1812.06079•Physical Review A•Mar 1, 2019•31 citations
Under the condition N≫vN \gg vN≫v, we study the behavior of coherence in scattering quantum walk search and show the connection between it and the probability of success. We find that the consumption of coherence is highly related to the increase of the probability of success. We also find that the consumption of coherence is related to the efficiency of this algorithm. The more efficient the algorithm is, the more coherence is consumed. If no coherence is consumed, the efficiency of the algorithm will be the same as classical one, which implies coherence may be respond for the speeding up over classical one in this quantum algorithm. Moreover, we study the probability of success in the case of an incoherent initial state and find that when NNN is large enough it will not change with time. It could be concluded that this quantum search algorithm loses its power with an incoherent initial state. This further shows that coherence plays an essential role in this algorithm.
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.
Quantum walk is fundamental to designing many quantum algorithms. Here we consider the effects of quantum coherence and quantum entanglement for the quantum walk search on the complete bipartite graph. First, we numerically show the complementary relationship between the success probability and the two quantum resources (quantum coherence and quantum entanglement). We also provide theoretical analysis in the asymptotic scenarios. At last, we discuss the role played by generalized depolarizing noises and find that it would influence the dynamics of success probability and quantum coherence sharply, which is demonstrated by theoretical derivation and numerical simulation.
Quantum algorithms have demonstrated provable speedups over classical counterparts, yet establishing a comprehensive theoretical framework to understand the quantum advantage remains a core challenge. In this work, we decode the quantum search advantage by investigating the critical role of quantum state properties in random-walk-based algorithms. We propose three distinct variants of quantum random-walk search algorithms and derive exact analytical expressions for their success probabilities. These probabilities are fundamentally determined by specific initial state properties: the coherence fraction governs the first algorithm's performance, while entanglement and coherence dominate the outcomes of the second and third algorithms, respectively. We show that increased coherence fraction enhances success probability, but greater entanglement and coherence reduce it in the latter two cases. These findings reveal fundamental insights into harnessing quantum properties for advantage and guide algorithm design. Our searches achieve Grover-like speedups and show significant potential for quantum-enhanced machine learning.
Quantum walk is fundamental to designing many quantum algorithms. Here we consider the effects of quantum coherence and quantum entanglement for the quantum walk search on the complete bipartite graph. First, we numerically show the complementary relationship between the success probability and the two quantum resources (quantum coherence and quantum entanglement). We also provide theoretical analysis in the asymptotic scenarios. At last, we discuss the role played by generalized depolarizing noises and find that it would influence the dynamics of success probability and quantum coherence sharply, which is demonstrated by theoretical derivation and numerical simulation.
Coherence is one of the most basic concepts and resources in quantum information. To clear the role coherence plays on the essential operator level in Grover's search algorithm, here we discuss the coherence dynamics of the state after each basic operator is applyied. As it is known, Grover's search algorithm repeats the application of Grover operator GGG, which can be decomposed into $G={H}^{\ensuremath{\bigotimes}n}P{H}^{\ensuremath{\bigotimes}n}O$, where HHH is Hadamard operator, PPP is the condition phase-shift operator, and OOO is the oracle operator. First, we show that OOO and PPP are incoherent operators while ${H}^{\ensuremath{\bigotimes}n}$ is coherent. Second, we prove that the amount of the operator coherence of the first ${H}^{\ensuremath{\bigotimes}n}$ and the operator coherence produced or depleted by ${H}^{\ensuremath{\bigotimes}n}$ depends not only on the size of the database and the success probability, but also on target states. Moreover, the amount of operator coherence is larger when the superposition state of targets is entangled rather than product. Third, we show that the two ${H}^{\ensuremath{\bigotimes}n}$ have different effects on coherence that one produces coherence and the other depletes coherence, and the depletion plays a major role. Therefore, the coherence is vibrating during the search process and the overall effect is that coherence is in depletion.
The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph of NNN vertices for one of kkk marked vertices with different initial states. We prove an intriguing dependence on the number of marked and unmarked vertices in each partite set. For example, when the graph is irregular and the initial state is the typical uniform superposition over the vertices, then the success probability can vary greatly from one time step to the next, even alternating between 0 and 1, so the precise time at which measurement occurs is crucial. When the initial state is a uniform superposition over the edges, however, the success probability evolves smoothly. As another example, if the complete bipartite graph is regular, then the two initial states are equivalent. Then if two marked vertices are in the same partite set, the success probability reaches 1/21/21/2, but if they are in different partite sets, it instead reaches 1. This differs from the complete graph, which is the quantum walk formulation of Grover's algorithm, where the success probability with two marked vertices is 8/98/98/9. This reveals a contrast to the continuous-time quantum walk, whose evolution is governed by Schr\"odinger's equation, which asymptotically searches the regular complete bipartite graph with any arrangement of marked vertices in the same manner as the complete graph.