Spatial search using the discrete time quantum walk

Details Spatial search using the discrete time quantum walk Spatial search using the discrete time quantum walk

2010-10-22

arxiv.org/abs/1010.4705v1

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-660176