Spatial search using the discrete time quantum walk

Abstract

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.

23 pages, 19 figures. Proceedings of Physics and Computation 2009, Ponta Delgada, Azores, 2009

References in corpus (11)

• Strengths and Weaknesses of Quantum Computing
• A Quantum Random Walk Search Algorithm
• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Controlling discrete quantum walks: coins and intitial states
• Faster quantum walk algorithm for the two dimensional spatial search
• Spatial search and the Dirac equation
• Hitting time for quantum walks on the hypercube
• Quantum walks on quotient graphs
• Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2
• Quantum walk based search algorithms