Spatial search using the discrete time quantum walk

Lovett, Neil B. and Everitt, Matthew and Trevers, Matthew and Mosby, Daniel and Stockton, Dan and Kendon, Viv (2012) Spatial search using the discrete time quantum walk. Natural Computing, 11 (1). pp. 23-35. ISSN 1572-9796 (https://doi.org/10.1007/s11047-011-9279-4)

[thumbnail of Lovett-etal-NC2012-Spatial-search-using-discrete-time-quantum-walk]
Preview
 Text. Filename: Lovett_etal_NC2012_Spatial_search_using_discrete_time_quantum_walk.pdf
Accepted Author Manuscript
Download (1MB)| Preview

Abstract

We study the quantum walk search algorithm of Shenvi et al. (Phys Rev A 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(√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.

ORCID iDs

Lovett, Neil B., Everitt, Matthew, Trevers, Matthew, Mosby, Daniel, Stockton, Dan and Kendon, Viv ORCID logoORCID: https://orcid.org/0000-0002-6551-3056;
  • Item type:Article
    ID code:78939
    Dates:
    Date
    Event
    31 March 2012
    Published
    1 October 2011
    Published Online
    Notes:© 2011 Springer Science+Business Media B.V.
    Subjects:Science > Physics
    Department:Faculty of Science > Physics
    Depositing user: Pure Administrator
    Date deposited:16 Dec 2021 14:26
    Last modified:11 Nov 2024 13:19
    URI:https://strathprints.strath.ac.uk/id/eprint/78939
CORE (COnnecting REpositories)