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 (

[thumbnail of Lovett-etal-NC2012-Spatial-search-using-discrete-time-quantum-walk]
Text. Filename: Lovett_etal_NC2012_Spatial_search_using_discrete_time_quantum_walk.pdf
Accepted Author Manuscript

Download (1MB)| Preview


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.