Physics – Quantum Physics
Scientific paper
2010-10-22
Physics
Quantum Physics
23 pages, 19 figures. Proceedings of Physics and Computation 2009, Ponta Delgada, Azores, 2009
Scientific paper
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.
Everitt Matthew
Kendon Viv
Lovett Neil B.
Mosby Daniel
Stockton Dan
No associations
LandOfFree
Spatial search using the discrete time quantum walk does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Spatial search using the discrete time quantum walk, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spatial search using the discrete time quantum walk will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-660176