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

The quantum walk search algorithm : factors affecting efficiency

Neil B. Lovett, Matthew Everitt, Robert M. Heath, Viv M. Kendon

Published May 16, 2018• 15 citations
OpenAlex

Abstract

We carry out a numerical study of the quantum walk search algorithm of Shenvi, Kempe and Whaley Shenvi et al. (2003) and the factors that affect its efficiency in finding an individual state from an unsorted set. Previous work has focused purely on the effects of the dimensionality of the dataset to be searched. In the current paper we consider the effects of interpolating between dimensions, the connectivity of the dataset and the possibility of disorder in the underlying substrate: all these factors affect the efficiency of the search algorithm. We show that in addition to the strong dependence on the spatial dimension of the structure to be searched, there are also secondary dependencies on the connectivity and symmetry of the lattice, with greater connectivity providing a more efficient algorithm. We also show that the algorithm can tolerate a non-trivial level of disorder in the underlying substrate.

Related papers

The quantum walk search algorithm: factors affecting efficiency

NEIL B. LOVETT, MATTHEW EVERITT, ROBERT M. HEATH +1 more

We carry out a numerical study of the quantum walk search algorithm of Shenvi, Kempe and Whaley Shenvi et al. (2003) and the factors that affect its efficiency in finding an individual state from an unsorted set. Previous work has focused purely on the effects of the dimensionality of the dataset to be searched. In the current paper we consider the effects of interpolating between dimensions, the connectivity of the dataset and the possibility of disorder in the underlying substrate: all these factors affect the efficiency of the search algorithm. We show that in addition to the strong dependence on the spatial dimension of the structure to be searched, there are also secondary dependencies on the connectivity and symmetry of the lattice, with greater connectivity providing a more efficient algorithm. We also show that the algorithm can tolerate a non-trivial level of disorder in the underlying substrate.

arXiv:1110.4366•Mathematical Structures in Computer Science•May 16, 2018•10 citations

Spatial search using the discrete time quantum walk

Neil B. Lovett, Matthew Everitt, Matt Trevers +3 more

We study the quantum walk search algorithm of Shenvi, Kempe and Whaley [PRA 67 052307 (2003)] on data structures of one to two spatial dimensions, on which the algorithm is thought to be less efficient than in three or more spatial dimensions. Our aim is to understand why the quantum algorithm is dimension dependent whereas the best classical algorithm is not, and to show in more detail how the efficiency of the quantum algorithm varies with spatial dimension or accessibility of the data. Our numerical results agree with the expected scaling in 2D of $O(\sqrt{N \log N})$, and show how the prefactors display significant dependence on both the degree and symmetry of the graph. Specifically, we see, as expected, the prefactor of the time complexity dropping as the degree (connectivity) of the structure is increased.

arXiv:1010.4705•Oct 22, 2010•1 citation

Connectivity effects in the coined quantum walk search algorithm

Neil B. Lovett, Viv M. Kendon

We show numerically how the quantum walk search algorithm depends on both the spatial dimension and connectivity of the structure being searched. We investigate this using a simple form of tunnelling to interpolate between lattices.

International Conference on Quantum Information•Jan 1, 2011•0 citations

Quantum walk search factors in the regime of weak measurement

Debabrata Ghoshal

Our previous work brought some interesting results of the discrete Quantum Walks in the regime of Weak Measurement (QWWM or QWWV). Using the knowledge of such results of QWWM, we are now exploring the search algorithms and investigating the factors associated with such walk. The study of such factors like dimensionality, connectivity of the dataset and the strength of disorder or percolation are already studied by others in the context of general quantum walks. It is our interest to show the similarities and/or differences of such factors of general quantum walks with QWWV. The subject of decoherence in quantum walks is another challenging research topic at present. We are also exploring the topic of decoherence in QWWM or QWWV.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Jun 11, 2014•0 citations

Lackadaisical quantum walk for spatial search

Pulak Ranjan Giri, V. E. Korepin

Lackadaisical quantum walk (LQW) has been an efficient technique in searching for a target state in a database which is distributed in a two-dimensional lattice. We numerically study the quantum search algorithm based on the lackadaisical quantum walk in one and two dimensions. It is observed that specific values of the self-loop weight at each vertex of the graph is responsible for such a speedup of the algorithm. Searching for a target state in one-dimensional lattice with periodic boundary conditions is possible using lackadaisical quantum walk, which can find a target state with [Formula: see text] success probability after [Formula: see text] time steps. In two dimensions, our numerical simulation up to [Formula: see text] for specific sets of target states suggests that the lackadaisical quantum walk can search one of the [Formula: see text] target states in [Formula: see text] time steps.

arXiv:1811.06169•Modern Physics Letters A•Dec 3, 2019•24 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 carry out a numerical study of the quantum walk search algorithm of Shenvi, Kempe and Whaley Shenvi et al. (2003) and the factors that affect its efficiency in finding an individual state from an unsorted set. Previous work has focused purely on the effects of the dimensionality of the dataset to be searched. In the current paper we consider the effects of interpolating between dimensions, the connectivity of the dataset and the possibility of disorder in the underlying substrate: all these factors affect the efficiency of the search algorithm. We show that in addition to the strong dependence on the spatial dimension of the structure to be searched, there are also secondary dependencies on the connectivity and symmetry of the lattice, with greater connectivity providing a more efficient algorithm. We also show that the algorithm can tolerate a non-trivial level of disorder in the underlying substrate.
We carry out a numerical study of the quantum walk search algorithm of Shenvi, Kempe and Whaley Shenvi et al. (2003) and the factors that affect its efficiency in finding an individual state from an unsorted set. Previous work has focused purely on the effects of the dimensionality of the dataset to be searched. In the current paper we consider the effects of interpolating between dimensions, the connectivity of the dataset and the possibility of disorder in the underlying substrate: all these factors affect the efficiency of the search algorithm. We show that in addition to the strong dependence on the spatial dimension of the structure to be searched, there are also secondary dependencies on the connectivity and symmetry of the lattice, with greater connectivity providing a more efficient algorithm. We also show that the algorithm can tolerate a non-trivial level of disorder in the underlying substrate.
We study the quantum walk search algorithm of Shenvi, Kempe and Whaley [PRA 67 052307 (2003)] on data structures of one to two spatial dimensions, on which the algorithm is thought to be less efficient than in three or more spatial dimensions. Our aim is to understand why the quantum algorithm is dimension dependent whereas the best classical algorithm is not, and to show in more detail how the efficiency of the quantum algorithm varies with spatial dimension or accessibility of the data. Our numerical results agree with the expected scaling in 2D of O(Nlog⁡N)O(\sqrt{N \log N})O(NlogN​), and show how the prefactors display significant dependence on both the degree and symmetry of the graph. Specifically, we see, as expected, the prefactor of the time complexity dropping as the degree (connectivity) of the structure is increased.
Our previous work brought some interesting results of the discrete Quantum Walks in the regime of Weak Measurement (QWWM or QWWV). Using the knowledge of such results of QWWM, we are now exploring the search algorithms and investigating the factors associated with such walk. The study of such factors like dimensionality, connectivity of the dataset and the strength of disorder or percolation are already studied by others in the context of general quantum walks. It is our interest to show the similarities and/or differences of such factors of general quantum walks with QWWV. The subject of decoherence in quantum walks is another challenging research topic at present. We are also exploring the topic of decoherence in QWWM or QWWV.
Lackadaisical quantum walk (LQW) has been an efficient technique in searching for a target state in a database which is distributed in a two-dimensional lattice. We numerically study the quantum search algorithm based on the lackadaisical quantum walk in one and two dimensions. It is observed that specific values of the self-loop weight at each vertex of the graph is responsible for such a speedup of the algorithm. Searching for a target state in one-dimensional lattice with periodic boundary conditions is possible using lackadaisical quantum walk, which can find a target state with [Formula: see text] success probability after [Formula: see text] time steps. In two dimensions, our numerical simulation up to [Formula: see text] for specific sets of target states suggests that the lackadaisical quantum walk can search one of the [Formula: see text] target states in [Formula: see text] time steps.
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.