Spatial search by quantum walk with a randomized local start state

In this thesis, we present a quantum walk algorithm for spatial search of a periodic lattice. Our algorithm is a variation of the Childs and Goldstone algorithm for spatial search, but begins in a randomly selected local initial state rather than a uniformly delocalized one. We analytically calculate the running time of our algorithm on the complete graph and find it to be O([square root]N). We reduce the analysis of our algorithm to that of the Childs and Goldstone algorithm by comparing the eigenvalue conditions of the Hamiltonians used in the two algorithms. We numerically show that the two Hamiltonians have similar eigenvalue conditions when the starting state is a certain extremal vertex of the lattice. We also study the behavior of the algorithm when we move the start state away from this extremal vertex. Finally, we numerically analyze the behavior of our algorithm on 5 and 4 dimensional lattices. In the 5 dimensional case, we appear to be able to achieve a O([square root]N) running time. In the 4 dimensional case, previous analysis indicates there may be additional factors of logc N in the running time of our algorithm. Numerically, we are not able to determine whether this logarithmic factor exists. However, the numerical evidence does indicate that the running time of our algorithm is O([square root]N), up to some factor of logc N.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Physics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2004

Author dc:creator

• Zhao, Fen, 1982-

Advisor dc:contributor.advisor

• Edward Farhi.

• Physics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/32750

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/32750