Skip to main content

Research Repository

Advanced Search

The quantum walk search algorithm: factors affecting efficiency

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

The quantum walk search algorithm: factors affecting efficiency Thumbnail


Authors

Neil B. Lovett

Matthew Everitt

Robert M. Heath



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.

Citation

Lovett, N. B., Everitt, M., Heath, R. M., & Kendon, V. (2019). The quantum walk search algorithm: factors affecting efficiency. Mathematical Structures in Computer Science, 29(3), 389-429. https://doi.org/10.1017/s0960129518000051

Journal Article Type Article
Online Publication Date May 16, 2018
Publication Date Mar 31, 2019
Deposit Date Mar 12, 2019
Publicly Available Date Mar 29, 2024
Journal Mathematical Structures in Computer Science
Print ISSN 0960-1295
Electronic ISSN 1469-8072
Publisher Cambridge University Press
Peer Reviewed Peer Reviewed
Volume 29
Issue 3
Pages 389-429
DOI https://doi.org/10.1017/s0960129518000051
Related Public URLs https://arxiv.org/abs/1110.4366

Files

Accepted Journal Article (620 Kb)
PDF

Copyright Statement
This article has been published in a revised form in Mathematical structures in computer science https://doi.org/10.1017/S0960129518000051. This version is free to view and download for private research and study only. Not for re-distribution, re-sale or use in derivative works. © Cambridge University Press 2018.




You might also like



Downloadable Citations