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:1704.04974 · Scientific Reports

Coherence as resource in scattering quantum walk search on complete graph

Yunlong Su, Siyuan Liu, Xiao-Hui Wang, Heng Fan, Wen‐Li Yang

Published Jul 17, 2018• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1038/s41598-018-29342-5

Related papers

Scattering quantum random-walk search with errors

A. Gábris, T. Kiss, Igor Jex

We analyze the realization of a quantum-walk search algorithm in a passive, linear optical network. The specific model enables us to consider the effect of realistic sources of noise and losses on the search efficiency. Photon loss uniform in all directions is shown to lead to the rescaling of search time. Deviation from directional uniformity leads to the enhancement of the search efficiency compared to uniform loss with the same average. In certain cases even increasing loss in some of the directions can improve search efficiency. We show that while we approach the classical limit of the general search algorithm by introducing random phase fluctuations, its utility for searching is lost. Using numerical methods, we found that for static phase errors the averaged search efficiency displays a damped oscillatory behavior that asymptotically tends to a nonzero value.

arXiv:quant-ph/0701150•Physical Review A•Dec 20, 2007•21 citations

Searching via walking: How to find a marked clique of a complete graph using quantum walks

Mark S. Hillery, Daniel Reitzner, Vladimír Bužek

We show how a quantum walk can be used to find a marked edge or a marked complete subgraph of a complete graph. We employ a version of a quantum walk, the scattering walk, which lends itself to experimental implementation. The edges are marked by adding elements to them that impart a specific phase shift to the particle as it enters or leaves the edge. If the complete graph has $N$ vertices and the subgraph has $K$ vertices, the particle becomes localized on the subgraph in $O(N/K)$ steps. This leads to a quantum search that is quadratically faster than a corresponding classical search. We show how to implement the quantum walk using a quantum circuit and a quantum oracle, which allows us to specify the resources needed for a quantitative comparison of the efficiency of classical and quantum searches---the number of oracle calls.

arXiv:0911.1102•Physical Review A•Jun 17, 2010•39 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.

arXiv:2310.00352•Results in Physics•Sep 29, 2023•2 citations

Search algorithm of abnormal structure on complete graph: Discussion of classical algorithm merged into the quantum computing thinking

H Chen, Wenbo Li, Zi-Fan Liu +1 more

© 2017, Editorial Department of Journal of Southeast University. All right reserved. Quantum computing thinking is used to explore new search methods for graph structures. A search algorithm for structural anomalies on complete graphs based on scattering quantum walk is proposed. Adding a pendant vertex to a complete graph, in which the number of vertices is N, breaks the symmetry of the complete graph and indicates the change of the topology of the complete graph. First, the precise definition of the evolutionary unitary operator U of scattering quantum walk in the complete graph is presented. The Hilbert space in which the walk occurs is projected to a lower-dimensional invariant subspace S, and the action of the evolutionary operator in the subspace US is given. Then, the equal superposition of all the basis states in the complete graph is chosen as the initial state. The eigenvalues and the eigenstates of US is calculated by using the perturbation theory, and the final state (pendants) of the algorithm is solved. Finally, the time complexity and the success probability of the algorithm are analyzed. The algorithm analysis and the Matlab simulation results show that the quantum search algorithm using scattering quantum walk can find the anomaly in O(N1/2) steps with the probability near to 1. However, the time complexity of the classical algorithm for searching the anomaly by the adjacency list is O(N). Therefore, the search algorithm based on scattering quantum walk can provide a quadric speed up over the classical algorithm for this specific problem.

•Sep 20, 2017•0 citations

Robust Quantum Walk Search on Complete Multipartite Graph With Multiple Marked Vertices

Nan-Yow Chen, Meng Li, Xiaoming Sun

Quantum walks are a potent technique for building quantum algorithms. This paper examines the quantum walk search algorithm on complete multipartite graphs with multiple marked vertices, which has not been explored before. We employ the coined quantum walk model and achieve quadratic speedup with a constant probability of finding a marked vertex in two specific cases of complete multipartite graphs. Furthermore, we investigate the robust quantum walk of two cases and demonstrate that even with an unknown number of marked vertices, it is still possible to achieve a quadratic speedup compared to classical algorithms and the success probability oscillates within a small range close to 1. To establish this conclusion, we employ approximation and reduction methods to conduct theoretical analysis and proofs, and provide an intuitive demonstration through numerical simulations. This work addresses the overcooking problem in quantum walk search algorithms on some complete multipartite graphs and may offer insights for robust quantum search on broader graph structures. Finally, we design a circuit for the algorithm that future researchers can use to conduct experiments.

arXiv:2410.04924•IEEE Transactions on Quantum Engineering•Jan 1, 2026•1 citation
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 analyze the realization of a quantum-walk search algorithm in a passive, linear optical network. The specific model enables us to consider the effect of realistic sources of noise and losses on the search efficiency. Photon loss uniform in all directions is shown to lead to the rescaling of search time. Deviation from directional uniformity leads to the enhancement of the search efficiency compared to uniform loss with the same average. In certain cases even increasing loss in some of the directions can improve search efficiency. We show that while we approach the classical limit of the general search algorithm by introducing random phase fluctuations, its utility for searching is lost. Using numerical methods, we found that for static phase errors the averaged search efficiency displays a damped oscillatory behavior that asymptotically tends to a nonzero value.
We show how a quantum walk can be used to find a marked edge or a marked complete subgraph of a complete graph. We employ a version of a quantum walk, the scattering walk, which lends itself to experimental implementation. The edges are marked by adding elements to them that impart a specific phase shift to the particle as it enters or leaves the edge. If the complete graph has NNN vertices and the subgraph has KKK vertices, the particle becomes localized on the subgraph in O(N/K)O(N/K)O(N/K) steps. This leads to a quantum search that is quadratically faster than a corresponding classical search. We show how to implement the quantum walk using a quantum circuit and a quantum oracle, which allows us to specify the resources needed for a quantitative comparison of the efficiency of classical and quantum searches---the number of oracle calls.
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.
© 2017, Editorial Department of Journal of Southeast University. All right reserved. Quantum computing thinking is used to explore new search methods for graph structures. A search algorithm for structural anomalies on complete graphs based on scattering quantum walk is proposed. Adding a pendant vertex to a complete graph, in which the number of vertices is N, breaks the symmetry of the complete graph and indicates the change of the topology of the complete graph. First, the precise definition of the evolutionary unitary operator U of scattering quantum walk in the complete graph is presented. The Hilbert space in which the walk occurs is projected to a lower-dimensional invariant subspace S, and the action of the evolutionary operator in the subspace US is given. Then, the equal superposition of all the basis states in the complete graph is chosen as the initial state. The eigenvalues and the eigenstates of US is calculated by using the perturbation theory, and the final state (pendants) of the algorithm is solved. Finally, the time complexity and the success probability of the algorithm are analyzed. The algorithm analysis and the Matlab simulation results show that the quantum search algorithm using scattering quantum walk can find the anomaly in O(N1/2) steps with the probability near to 1. However, the time complexity of the classical algorithm for searching the anomaly by the adjacency list is O(N). Therefore, the search algorithm based on scattering quantum walk can provide a quadric speed up over the classical algorithm for this specific problem.
Quantum walks are a potent technique for building quantum algorithms. This paper examines the quantum walk search algorithm on complete multipartite graphs with multiple marked vertices, which has not been explored before. We employ the coined quantum walk model and achieve quadratic speedup with a constant probability of finding a marked vertex in two specific cases of complete multipartite graphs. Furthermore, we investigate the robust quantum walk of two cases and demonstrate that even with an unknown number of marked vertices, it is still possible to achieve a quadratic speedup compared to classical algorithms and the success probability oscillates within a small range close to 1. To establish this conclusion, we employ approximation and reduction methods to conduct theoretical analysis and proofs, and provide an intuitive demonstration through numerical simulations. This work addresses the overcooking problem in quantum walk search algorithms on some complete multipartite graphs and may offer insights for robust quantum search on broader graph structures. Finally, we design a circuit for the algorithm that future researchers can use to conduct experiments.