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:quant-ph/0701150 · Physical Review A

Scattering quantum random-walk search with errors

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

Published Dec 20, 2007• 24 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.76.062315

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

Gate imperfection in the quantum random-walk search algorithm

Yun Li, Lei Ma, Jie Zhou

We study how imperfect quantum gates affect the quantum random-walk search algorithm. We find that systematic errors in phase inversions result in the reduction of the maximum probability of the marked state and lower the algorithm efficiency with an increasing degree of inaccuracy. The size of the database should be limited due to the inevitable errors. Finally, we compare the phase noise caused by such errors in the random-walk search algorithm with that in the Grover search algorithm.

Journal of Physics A Mathematical and General•Jul 5, 2006•7 citations

Noise-resilient spatial search with lackadaisical quantum walks

Gabriel Mauricio Oswald Vieira, Nelson Maculan, Franklin de Lima Marquezino

Abstract Quantum walks are a powerful framework for the development of quantum algorithms, with lackadaisical quantum walks (LQWs) standing out as an efficient model for spatial search. In this work, we investigate how broken-link decoherence affects the performance of LQW-based search on a two-dimensional toroidal grid. We show through numerical simulations that while decoherence drives the loopless walk toward a uniform distribution and eliminates its search capability, the inclusion of self-loops significantly mitigates this effect. In particular, even under noise, the marked vertex remains identifiable with probability well above uniform, demonstrating that self-loops enhance the robustness of LQWs in realistic scenarios. These findings extend the known advantages of LQWs from the noiseless setting to noisy environments, consolidating self-loops as a valuable resource for designing resilient quantum search algorithms.

arXiv:2508.13462•Quantum Information Processing•May 20, 2026•0 citations

Data Search Algorithms based on Quantum Walk

Masataka Fujisaki, Hiromi Miyajima, Noritaka Shigei

For searching any item in an unsorted database with N items, a classical computer takes O(N) steps but Grover’s quantum searching algorithm takes only O( √ N) steps. However, it is also known that Grover’s algorithm is effective only in the case where the initial amplitude distribution of dataset is uniform, but is not always effective in the nonuniform case. In this paper, we propose some quantum search algorithms. First, we propose an algorithm in analog time based on quantum walk by solving the schrodinger equation. The proposed algorithm shows best performance in optimum time. Next, we will apply the result to Grover search algorithm. It is shown that the proposed algorithm shows better performance than the conventional one. Further, we propose the improved algorithm by introducing the idea of the phase rotation. The algorithm shows best performance compared with the conventional ones.

Lecture notes in computer science•Jan 1, 2012•2 citations

Effects of systematic phase errors on optimized quantum random-walk search algorithm

Yuchao Zhang, Wan‐Su Bao, Xiang Wang +1 more

This study investigates the effects of systematic errors in phase inversions on the success rate and number of iterations in the optimized quantum random-walk search algorithm. Using the geometric description of this algorithm, a model of the algorithm with phase errors is established, and the relationship between the success rate of the algorithm, the database size, the number of iterations, and the phase error is determined. For a given database size, we obtain both the maximum success rate of the algorithm and the required number of iterations when phase errors are present in the algorithm. Analyses and numerical simulations show that the optimized quantum random-walk search algorithm is more robust against phase errors than Grover’s algorithm.

arXiv:1501.02098•Chinese Physics B•Jun 1, 2015•6 citations

White Noise in Quantum Random Walk Search Algorithm

Лей Ма, Du Jiang-Feng, Yun Li +3 more

The quantum random walk is a possible approach to construct new quantum search algorithms. It has been shown by Shenvi et al. [Phys. Rev. A 67 (2003) 52307 that a kind of algorithm can perform an oracle search on a database of N items with O ( N 1/2 ) calling to the oracle, yielding a speedup similar to other quantum search algorithms. We study the effect of white or Gaussian noise on this algorithm. The algorithm loses efficiency when noise is added. We also show that noise on the target state plays a more important role than that on other states. Finally we compare the effects of similar types of noise in the quantum random walk search algorithm and Grover's search algorithm.

Chinese Physics Letters•Mar 30, 2006•4 citations
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 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.
Abstract Quantum walks are a powerful framework for the development of quantum algorithms, with lackadaisical quantum walks (LQWs) standing out as an efficient model for spatial search. In this work, we investigate how broken-link decoherence affects the performance of LQW-based search on a two-dimensional toroidal grid. We show through numerical simulations that while decoherence drives the loopless walk toward a uniform distribution and eliminates its search capability, the inclusion of self-loops significantly mitigates this effect. In particular, even under noise, the marked vertex remains identifiable with probability well above uniform, demonstrating that self-loops enhance the robustness of LQWs in realistic scenarios. These findings extend the known advantages of LQWs from the noiseless setting to noisy environments, consolidating self-loops as a valuable resource for designing resilient quantum search algorithms.
For searching any item in an unsorted database with N items, a classical computer takes O(N) steps but Grover’s quantum searching algorithm takes only O( √ N) steps. However, it is also known that Grover’s algorithm is effective only in the case where the initial amplitude distribution of dataset is uniform, but is not always effective in the nonuniform case. In this paper, we propose some quantum search algorithms. First, we propose an algorithm in analog time based on quantum walk by solving the schrodinger equation. The proposed algorithm shows best performance in optimum time. Next, we will apply the result to Grover search algorithm. It is shown that the proposed algorithm shows better performance than the conventional one. Further, we propose the improved algorithm by introducing the idea of the phase rotation. The algorithm shows best performance compared with the conventional ones.
This study investigates the effects of systematic errors in phase inversions on the success rate and number of iterations in the optimized quantum random-walk search algorithm. Using the geometric description of this algorithm, a model of the algorithm with phase errors is established, and the relationship between the success rate of the algorithm, the database size, the number of iterations, and the phase error is determined. For a given database size, we obtain both the maximum success rate of the algorithm and the required number of iterations when phase errors are present in the algorithm. Analyses and numerical simulations show that the optimized quantum random-walk search algorithm is more robust against phase errors than Grover’s algorithm.
The quantum random walk is a possible approach to construct new quantum search algorithms. It has been shown by Shenvi et al. [Phys. Rev. A 67 (2003) 52307 that a kind of algorithm can perform an oracle search on a database of N items with O ( N 1/2 ) calling to the oracle, yielding a speedup similar to other quantum search algorithms. We study the effect of white or Gaussian noise on this algorithm. The algorithm loses efficiency when noise is added. We also show that noise on the target state plays a more important role than that on other states. Finally we compare the effects of similar types of noise in the quantum random walk search algorithm and Grover's search algorithm.